Approximation of Convex Sets by Polytopes

E. M. Bronshtein

Contemporary Mathematics. Fundamental Directions, Geometry, Tome 22 (2007), pp. 5-37.

Bibliographie

[1] Arnold V. I., “Statistika tselochislennykh vypuklykh mnogougolnikov”, Funkts. anal. prilozh., 14 (1980), 1–3 | MR

[2] Babenko I. K., “Asimptoticheskii ob'em torov i geometriya vypuklykh tel”, Mat. zametki, 44 (1988), 177–190 | MR

[3] Blyashke V., Krug i shar, Nauka, M., 1967 | MR

[4] Bronshtein E. M., “Ekstremalnye vypuklye funktsii”, Sib. mat. zh., 19 (1978), 10–18

[5] Bronshtein E. M., Ivanov L. D., “Priblizhenie vypuklykh mnozhestv mnogogrannikami”, Sib. mat. zh., 16 (1975), 1110–1112 | MR

[6] Burmistrova L. V., Issledovanie novogo metoda approksimatsii vypuklykh kompaktnykh tel mnogogrannikami, Soobsch. po prikl. mat., VTs RAN, 1999

[7] Burmistrova L. V., “Issledovanie novogo metoda approksimatsii vypuklykh kompaktnykh tel mnogogrannikami”, Zh. vychisl. mat. mat. fiz., 40 (2000), 1475–1490 | MR

[8] Bushenkov V. A., “Iteratsionnyi metod postroeniya optimalnykh proektsii vypuklykh mnogogrannykh mnozhestv”, Zh. vychisl. mat. mat. fiz., 25 (1985), 1285–1292 | MR | Zbl

[9] Bushenkov V. A., Lotov A. V., Metody postroeniya i ispolzovaniya obobschennykh mnozhestv dostizhimosti, VTs AN SSSR, 1982

[10] Vershik A. M., “Predelnaya forma vypuklykh tselochislennykh mnogougolnikov i smezhnye voprosy”, Funkts. anal. prilozh., 28 (1994), 16–25 | MR | Zbl

[11] Vershik A. M., “Predelnye formy tipichnykh geometricheskikh konfiguratsii i ikh prilozheniya”, Zap. nauch. semin. POMI, 280, 2001, 73–100 | MR | Zbl

[12] Georgiev P., “Aproksimirane na izn'knali $n$-'g'lnitsi s $n-1$-'g'lnitsi”, Mat. i mat. obrazov, Dokl. 13 prolet. konf. Soyuza mat. B'lg., 1984, 289–303 | MR | Zbl

[13] Dzholdybaeva S. M., Kamenev G. K., “Chislennoe issledovanie effektivnosti algoritma approksimatsii vypuklykh tel mnogogrannikami”, Zh. vychisl. mat. mat. fiz., 32 (1992), 857–866 | MR | Zbl

[14] Gryunbaum B., Etyudy po kombinatornoi geometrii i teorii vypuklykh tel, Nauka, M., 1971 | MR | Zbl

[15] Efremov R. V., “Otsenka effektivnosti adaptivnogo algoritma approksimatsii vypuklykh gladkikh tel v dvumernom sluchae”, Vestn. MGU. Ser. 15, 2000, no. 2, 29–32 | MR | Zbl

[16] Efremov R. V., Kamenev G. K., “Apriornaya otsenka asimptoticheskoi effektivnosti odnogo klassa algoritmov poliedralnoi approksimatsii vypuklykh tel”, Zh. vychisl. mat. mat. fiz., 42 (2002), 23–32 | MR | Zbl

[17] Efremov R. V., Kamenev G. K., Lotov A. V., “Postroenie ekonomichnogo opisaniya mnogogrannika na osnove teorii dvoistvennosti vypuklykh mnozhestv”, Dokl. RAN, 399 (2004), 594–596 | MR

[18] Kamenev G. K., “Ob odnom klasse adaptivnykh algoritmov approksimatsii vypuklykh tel mnogogrannikami”, Zh. vychisl. mat. mat. fiz., 32 (1992), 136–152 | MR

[19] Kamenev G. K., “Ob effektivnosti khausdorfovykh algoritmov poliedralnoi approksimatsii vypuklykh tel”, Zh. vychisl. mat. mat. fiz., 33 (1993), 796–805 | MR | Zbl

[20] Kamenev G. K., “Issledovanie odnogo algoritma approksimatsii vypuklykh tel”, Zh. vychisl. mat. mat. fiz., 34:4 (1994), 608–616 | MR | Zbl

[21] Kamenev G. K., “Algoritm sblizhayuschikhsya mnogogrannikov”, Zh. vychisl. mat. mat. fiz., 36:4 (1996), 134–147 | MR | Zbl

[22] Kamenev G. K., “Effektivnye algoritmy vnutrennei poliedralnoi approksimatsii negladkikh vypuklykh tel”, Zh. vychisl. mat. mat. fiz., 39:3 (1999), 446–450 | MR | Zbl

[23] Kamenev G. K., “Ob approksimatsionnykh svoistvakh negladkikh vypuklykh diskov”, Zh. vychisl. mat. mat. fiz., 40:10 (2000), 1464–1474 | MR | Zbl

[24] Kamenev G. K., “Metod poliedralnoi approksimatsii vypuklykh tel,optimalnyi po poryadku chisla raschetov opornoi i distantsionnoi funktsii”, Dokl. RAN, 388 (2003), 309–311 | MR

[25] Kamenev G. K., “Samodvoistvennye adaptivnye algoritmy poliedralnoi approksimatsii vypuklykh tel”, Zh. vychisl. mat. mat. fiz., 43 (2003), 1123–1137 | MR | Zbl

[26] Kashin B. S., “O parallelepipedakh minimalnogo ob'ema, soderzhaschikh vypukloe telo”, Mat. zametki, 45 (1989), 134–135 | MR | Zbl

[27] Makeev V. V., “Vpisannye i opisannye mnogogranniki vypuklogo tela i svyazannye s nimi zadachi”, Mat. zametki, 51 (1992), 67–71 | MR | Zbl

[28] Makeev V. V., “Vpisannye i opisannye mnogogranniki vypuklogo tela”, Mat. zametki, 55 (1994), 128–130 | MR | Zbl

[29] Makeev V. V., “Ob approksimatsii ploskikh sechenii vypuklogo tela”, Zap. nauch. semin. POMI, 246, 1997, 174–183 | MR | Zbl

[30] Makeev V. V., “Trekhmernye mnogogranniki, vpisannye i opisannye vokrug vypuklogo kompakta”, Algebra analiz, 12:4 (2000), 1–15 | MR

[31] Makeev V. V., “Trekhmernye mnogogranniki, vpisannye i opisannye vokrug vypuklogo kompakta, II”, Algebra analiz, 13 (2001), 110–133 | MR | Zbl

[32] Makeev V. V., “O nekotorykh kombinatorno-geometricheskikh zadachakh dlya vektornykh rassloenii”, Algebra analiz, 14 (2002), 169–191 | MR | Zbl

[33] Makeev V. V., Mukhin A. S., “O suschestvovanii obschego secheniya dlya neskolkikh vypuklykh kompaktov, imeyuschego zadannye svoistva”, Zap. nauch. semin. POMI, 261, 1999, 198–203 | MR | Zbl

[34] Popov V. A., “Aproksimirane na izn'knali mnozhestv”, Izv. Mat. in-t B'lg. AN, 11 (1970), 67–80 | MR | Zbl

[35] Sinai Ya. G., “Veroyatnostnyi podkhod k analizu statistiki vypuklykh lomanykh”, Funkts. anal. prilozh., 28 (1994), 16–25 | MR

[36] Feiesh Tot L., Raspolozheniya na ploskosti, na sfere i v prostranstve, Fizmatgiz, M., 1958

[37] Khadviger G., Lektsii ob ob'eme, ploschadi poverkhnosti i izoperimetrii, Nauka, M., 1966

[38] Chernykh O. L., “O postroenii vypukloi obolochki konechnogo mnozhestva tochek pri priblizhennykh vychisleniyakh”, Zh. vychisl. mat. mat. fiz., 28 (1988), 1386–1396 | MR | Zbl

[39] Shevchenko V. N., Kachestvennye voprosy tselochislennogo lineinogo programmirovaniya, Fizmatlit, M., 1995 | MR | Zbl

[40] Affentranger F., Schneider R., “Random projections of regular simplices”, Discr. Comput. Geom., 7 (1992), 219–226 | DOI | MR | Zbl

[41] Affentranger F., Wieaker J., “On the convex hull of uniform random points in a simple $d$-polytope”, Discr. Comput. Geom., 6 (1991), 291–305 | DOI | MR | Zbl

[42] Ahn H.-K., Brass P., Cheong O., Na H.-S., Shin C.-S., Vigneron A., “Approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon”, Computing and Combinatorics, Proc. 10th Annual Int. Conference. COCOON 2004 (Jeju Island, Korea, August 17–20, 2004), Lect. Notes Computer Sci., 3106, Springer-Verlag, Berlin, 259–267 | MR | Zbl

[43] Andrews G. E., “Alower bound for the volume of strictly convex bodies with many boundary lattice points”, Trans. Amer. Math. Soc., 106 (1963), 270–279 | DOI | MR | Zbl

[44] Asplund E., “Comparision of plane symmetric convex bodies and parallelograms”, Math. Scand., 8 (1960), 171–180 | MR | Zbl

[45] Atallah M. J., “A linear time algorithm for the Hausdorff distance between convex polygons”, Inf. Process. Lett., 17 (1983), 207–209 | DOI | MR | Zbl

[46] Atallah M. J., Ribeiro C. C., Lifschitz S., “A linear time algorithm for the computation of some distance functions between convex polygons”, RAIRO, Rech. Oper., 25 (1991), 413–424 | MR | Zbl

[47] Balog A., Bárány I., “On the convex hull of the integer points in a disc”, Discr. Comput. Geom., 6 (1991), 39–44 | MR | Zbl

[48] Balog A., Bárány I., “On the convex hull of the integer points in a disk”, Discr. Comput. Geom., 6 (1992), 39–44 | MR

[49] Balog A., Deshorlies J.-M., “On some convex lattice polytopes”, Number Theory in Progress, de Gruyter, 1999, 591–606 | MR | Zbl

[50] Baryshnikov Yu. M., Vitale R. A., “Regular simplices and Gaussian samples”, Discr. Comput. Geom., 11 (1994), 141–147 | DOI | MR | Zbl

[51] Bárány I., “Random polytopes in smooth convex bodies”, Mathematica, 39 (1992), 81–92 | MR | Zbl

[52] Bárány I., “The limit shape of convex lattice polygons”, Discr. Comput. Geom., 13 (1995), 270–295 | MR

[53] Bárány I., “Affine perimeter and limit shape”, J. Reine Angew. Math., 484 (1997), 71–84 | DOI | MR | Zbl

[54] Bárány I., “Sylvester's question: the probability that $n$ points are in convex position”, Ann. Probab., 27 (1999), 2020–2034 | DOI | MR | Zbl

[55] Bárány I., “A note on Sylvester's four-point problem”, Stud. Sci. Math. Hung., 38 (2001), 73–77 | MR | Zbl

[56] Bárány I., “Random points, convex bodies, lattices”, Proc. Int. Conf. Math., 3, 2002, 527–535 | MR | Zbl

[57] Bárány I., Böröczky K. Jr., “Lattice points on the boundary of the integer hull”, Discrete Geometry, In honor of W. Kuperberg's 60th birthday, Pure Appl. Math., 253, Marcel Dekker, NY, 2003, 33–47 | MR | Zbl

[58] Bárány I., Buchta C., “Random polytopes in a convex polytope, independence of shape, and concentration of vertices”, Math. Ann., 297 (1993), 467–497 | DOI | MR | Zbl

[59] Bárány I., Dalla L., “Few points to generate a random polytope”, Mathematika, 44 (1997), 325–331 | DOI | MR | Zbl

[60] Bárány I., Füredi Z., “Approximation of the sphere by polytopes having few vertices”, Proc. Amer. Math. Soc., 102 (1988), 651–659 | DOI | MR | Zbl

[61] Bárány I., Füredi Z., “On the shape of the convex hull of random points”, Probab. Theory Rel. Fields, 77 (1988), 231–240 | DOI | MR | Zbl

[62] Bárány I., Howe R., Lovász L., “On integer points in polyhedra: A lower bound”, Combinatorica, 12 (1992), 135–142 | DOI | MR | Zbl

[63] Bárány I., Larman D. G., “The convex hull of the integer points in the large ball”, Math. Ann., 312 (1998), 167–181 | DOI | MR | Zbl

[64] Bárány I., Larman D. G., “Convex bodies, economic cap coverings, random polytopes”, Mathematika, 35 (1988), 274–291 | DOI | MR | Zbl

[65] Bárány I., Matousek J., “The randomized integer convex hull”, Discr. Comput. Geom., 33 (2005), 3–25 | DOI | MR | Zbl

[66] Bárány I., Pór A., “On $0$-$1$ polytopes with many faces”, Adv. Math., 161:2 (2001), 209–228 | DOI | MR | Zbl

[67] Bárány I., Rote G., Steiger W., Zhang C.-H., “A central limit theorem for convex chains in the square”, Discr. Comput. Geom., 23 (2000), 35–50 | DOI | MR | Zbl

[68] Bárány I., Tokushige N., “The minimum area of convex lattice $n$-gons”, Combinatorica, 24 (2004), 171–185 | DOI | MR | Zbl

[69] Bárány I., Vershik A. M., “On the number of convex lattice polytopes”, GAFA J., 2:4 (1992), 381–393 | DOI | MR | Zbl

[70] Bielecki A., Radziszewski K., “Sur les parallélépipèdes inscrits dans les corps convexes”, Ann. Univ. Mariae Curie-Sclodowska, Sec. A, 7 (1954), 97–100 | MR

[71] Blaschke W., “Über affine Geometrie, III”, Ber. Verh. Sächs. Ges. Wiss. Leipzig, Math.-Phys., 69 (1917), 3–12 | Zbl

[72] Blaschke W., “Über affine Geometrie, IX”, Ber. Verh. Sächs. Ges. Wiss. Leipzig, Math.-Phys., 69 (1917), 412–420 | Zbl

[73] Blaschke W., Affine Differenzialgeometrie, Springer-Verlag, 1923 | Zbl

[74] Bokowski J., “Konvexe Körper approximierande Polytopclassen”, Elemente Math., 32 (1977), 88–90 | MR | Zbl

[75] Bokowski J., Schulz C., “Dichte Klassen konvexer Polytope”, Math. Z., 160 (1978), 173–182 | DOI | MR | Zbl

[76] Bokowski J., Mani-Levinska P., “Approximation of convex bodies by polytopes with uniformly bounded valences”, Monatsh. Math., 104 (1987), 261–264 | DOI | MR | Zbl

[77] Boratyǹski W., “Approximation of convex bodies by parallelotopes”, Proc. 7th Int. Conf. on Engeneering Computer Graphics and Descriptive Geometry, Cracow, Poland, 1996, 259–260 | Zbl

[78] Böröczky K. Jr., “Approximation of general smooth convex bodies”, Adv. Math., 153 (2000), 325–341 | DOI | MR | Zbl

[79] Böröczky K. Jr., “Polytopal approximation bounding the number of $k$-faces”, J. Approx. Theory, 102 (2000), 263–285. | DOI | MR | Zbl

[80] Böröczky K. Jr., “The error of polytopal approximation with respect to the symmetric difference metric and the $L_p$ metric”, Isr. J. Math., 117 (2000), 1–28 | DOI | MR | Zbl

[81] Böröczky K. Jr., “About the error term for best approximation with respect to the Hausdorf related metrics”, Discr. Comput. Geom., 25 (2001), 293–309 | DOI | MR | Zbl

[82] Böröczky K. Jr., Ludwig M., “Approximation of convex bodies and a momentum lemma for power diagram”, Monatsh. Math., 127 (1999), 101–110 | DOI | MR | Zbl

[83] Böröczky K. Jr., Reitzner M., “Approximation of smooth convex bodies by random circumscribed polytopes”, Ann. Appl. Probab., 14 (2004), 239–273 | DOI | MR | Zbl

[84] Bourgain J., Lindenstrauss J., “Distribution of points on sphere and approximation by zonotopes”, Isr. J. Math., 64 (1988.), 25–31 | DOI | MR | Zbl

[85] Bourgain J., Lindenstrauss J, Milman V. D., “Approximation of zonoids by zonotopes”, Acta Math., 162 (1989), 73–141 | DOI | MR | Zbl

[86] Buchta C., “Über die konvexe Hölle von Zufallspunkten in Eibereichen”, Elem. Math., 38 (1983), 153–156 | MR | Zbl

[87] Buchta C., “Stochastische Approximation konvexer Polygone”, Z. Wahrscheinlichkeitstheor. Verw. Geb., 67 (1984), 283–304 | DOI | MR | Zbl

[88] Buchta C., “A note on the volume of a random polytope in a tetrahedron”, Ill. J. Math., 30 (1986), 653–659 | MR | Zbl

[89] Buchta C., “A remark on random approximation of simple polytopes”, Anz. Österr. Akad. Wiss., Math.-Naturwiss., 2 (1989), 17–20 | MR | Zbl

[90] Buchta C., Reitzner M., “What is the expected volume of a tetrahedron whose vertices are chosen at random from a given tetrahedron?”, Anz. Österr. Akad. Wiss., Math.-Naturwiss., 8 (1992), 63–68 | MR | Zbl

[91] Buchta C., Reitzner M., “Equiaffine inner parallel curves of a plane convex body and the convex hulls of randomly chosen points”, Probab. Theory Relat. Fields, 108 (1997), 385–415 | DOI | MR | Zbl

[92] Burkard R. E., Hamacher H. W., Rote G., “Sandwich approximation of univariate convex functions with its application to separable convex programming”, Naval Res. Logist, 38 (1991), 911–924 | MR | Zbl

[93] Cabo A. J., Groeneboom P., “Limit theorems for functionals of convex hulls”, Probab. Theory Relat. Fields, 100 (1994), 31–55 | DOI | MR | Zbl

[94] Cheang G. H. L., Barron A. R., “A better approximation for balls”, J. Approx. Theory, 104 (2000), 183–203 | DOI | MR | Zbl

[95] Chen L., “New analysis of the sphere covering problems and optimal polytope approximation of convex bodies”, J. Approx. Theory, 133 (2005), 134–145 | DOI | MR | Zbl

[96] Clarkson K. L., “Algorithms for polytope covering and approximation”, Proc. 3rd Workshop on Algorithms and Data Structures, Lect. Notes Computer Sci., 709, 1993, 246–252 | MR

[97] Cook W., Hartmann M., Kannan R., McDiarmid C., “On integer points in polyhedra”, Combinatorica, 12 (1992), 27–37 | DOI | MR | Zbl

[98] Dalla L., Larman D. G., “Volumes of a random polytope in a convex set”, Applied Geometry and Discrete Mathematics., Festschr. 65th Birthday Victor Klee, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 4, Amer. Math. Soc., Providence, RI, 1991, 175–180 | MR

[99] Devroye L., “On the oscilation of the exprcted number of extreme points of a random set”, Statist. Probab. Lett., 11 (1991), 281–286 | DOI | MR | Zbl

[100] Doyle P. C., Lagarian J. C., Randall D., “Self-parking of centrally simmetric convex bodies in $R^2$”, Discr. Comput. Geom., 8 (1992), 171–189 | DOI | MR | Zbl

[101] Dvoretzky A., “Some results on convex bodies and Banach spaces”, Proc. Int. Symp. Linear Spaces (Jerusalem, 1960), Pergamon, Oxford, 1961, 123–160 | MR

[102] Dvoretzky A., Rogers C. A., “Absolute and unconditional convergence in normed linear spaces”, Proc. Nac. Acad. Sci. USA, 36 (1950), 192–197 | DOI | MR | Zbl

[103] Dudley R. M., “Metric entropy of some classes of sets with differentiable boundaries”, J. Approx. Theory, 10 (1974), 227–236 | DOI | MR | Zbl

[104] Dwyer R., “On the convex hull of random points in a polytope”, J. Appl. Probab., 25 (1988), 688–699 | DOI | MR | Zbl

[105] Dwyer R., Kannan R., “Convex hull of randomly chosen points from a polytope”, Parallel Algorithms and Architectures, Proc. Int. Workshop (Suhl/GDR, 1987), Math. Res., 38, 1987, 16–24 | Zbl

[106] Dyer M. E., Frieze A. M., “On the complexity of computing the volume of a polyhedron”, SIAM J. Comput., 17 (1988), 967–974 | DOI | MR | Zbl

[107] Dyer M., Frieze A., “Computing the volume of convex bodies: a case where randomness provably helps”, Probabilistic combinatorics and its applications (San Francisco, CA, 1991), Proc. Sympos. Appl. Math., 44, Amer. Math. Soc., Providence, RI, 1991, 123–169 | MR

[108] Dyer M. E., Frieze A., Kannan R., “A random polynomial-time algorithm for approximating the volume of convex bodies”, J. Assoc. Comput. Mach., 38 (1991), 1–17 | MR | Zbl

[109] Dyer M. E., Fúredi Z., McDiarmid C., “Random volumes in the $n$-cube”, Polyhedral Combinatorics, Proc. Workshop (Morristown/NJ, USA, 1989), DIMACS Ser. Discrete Math. Theor. Comput. Sci., 1, 1990, 33–38 | MR | Zbl

[110] Dyer M. E., Fúredi Z., McDiarmid C., “Volumes spanned by random points in the hypercube”, Random Struct. Algorithms, 3 (1992), 91–106 | DOI | MR | Zbl

[111] Dyer M., Gritzmann P, Hufnagel A., “On the complexity of computing mixed volumes”, SIAM J. Comput., 27 (1998), 356–400 | DOI | MR | Zbl

[112] Eggleston H. G., “Approximation of plane convex curves. I: Dowker-tipe theorems”, Proc. London Math. Soc., 1957, 351–377 | DOI | MR | Zbl

[113] Eggleston H. G., Convexity, Cambrige, 1958 | MR

[114] Esterman T., “Über der Vektorenbereich eines konvexen Körpers”, Math. Z., 28 (1928), 471–475 | DOI | MR | Zbl

[115] Fabińska E., Lassak M., “Large equilateral triangles inscribed in the unit disk of a Minkowski plane”, Contrib. Algebra Geom., 45 (2004), 517–525 | MR | Zbl

[116] Faigle U., Gademann N., Kern W., “A random polynomial time algorithm for well-routing convex bodies”, Discr. Appl. Math., 58 (1995), 117–144 | DOI | MR | Zbl

[117] Fejes Tóth L., “Approximation by polygons and polyhedra”, Bull. Amer. Math. Soc., 54 (1948), 431–438 | DOI | MR | Zbl

[118] Fejes Tóth L., “Approximation of convex domains by polygons”, Stud. Sci. Math. Hung., 15 (1980), 133–138 | MR | Zbl

[119] Fischer P., “Sequential and parallel algorithms for finding a maximum convex polygon”, Comput. Geom., 7 (1997), 187–200 | DOI | MR | Zbl

[120] Finch S., Hueter I., “Random convex hulls: a variance revisited”, Adv. Appl. Probab., 36 (2004), 981–986 | DOI | MR | Zbl

[121] Fleiner T., Kaibel V., Rote G., “Upper bounds on the maximal number of facets of $0/1$-polytopes”, Eur. J. Combinat., 21 (2000), 121–130 | DOI | MR | Zbl

[122] Florian A., “On the perimetr deviation of a convex disk from a polygon”, Rend. Ist. Mat. Univ. Trieste, 24 (1992), 177–191 | MR | Zbl

[123] Florian A., “Approximation of convex discs by polygons: The perimeter deviation”, Stud. Sci. Math. Hung., 27 (1992), 97–118 | MR | Zbl

[124] Floyd E., “Real-valued mappings of spheres”, Proc. Amer. Math. Soc., 6 (1955), 957–959 | DOI | MR | Zbl

[125] Fruhwirth B., Burkard R. E., Rote G., “Approximation of convex curves with applications to the minimum cost flow problem”, Eur. J. Oper. Res., 42 (1989), 326–338 | DOI | MR | Zbl

[126] Fulton C. M., Stein S. K., “Parallelograms inscribed in convex curves”, Amer. Math. Monthely, 67 (1960), 257–258 | DOI | MR | Zbl

[127] Glasauer S., Gruber P. M., “Asimptotic estimates for best and stepwise approximation of convex bodies, III”, Forum Math., 9 (1997), 383–404 | DOI | MR | Zbl

[128] Glasauer S., Schneider R., “Asymptotic approximation of smooth convex bodies by polytopes”, Forum Math., 8 (1996), 363–377 | DOI | MR | Zbl

[129] Gleason A. M., “A curvature formula”, Amer. J. Math., 101 (1979), 86–93 | DOI | MR | Zbl

[130] Gluskin E. D., “On the sum of intervals”, Geometric aspects of functional analysis, Proc. Israel Semin. (GAFA) 2001–2002, Lect. Notes Math., 1807, 2003, 122–130 | MR | Zbl

[131] Gordon Y., Meyer M., Reisner S., “Volume approximation of convex bodies by polytopes. A constructive method”, Stud. Math., 111 (1994), 81–95 | MR | Zbl

[132] Gordon Y., Meyer M., Reisner S., “Constructing a polytope to approximate a convex body”, Geom. Dedic., 57 (1995), 217–222 | DOI | MR | Zbl

[133] Gordon Y., Reisner S., Schütt C., “Umbrellas and polytopal approximation of the Euclidean ball”, J. Approx. Theory, 90 (1997), 9–22 | DOI | MR | Zbl

[134] Gritzmann P., Klee V., Larman D., “Largest $j$-simplices in $d$-polytopes”, Discr. Comput. Geom., 13 (1995), 477–515 | DOI | MR | Zbl

[135] Gritzman P., Lassak M., “Estimates for the minimal wight of polytopes inscribed in convex bodies”, Discr. Comput. Geom., 4 (1989), 627–635 | DOI | MR | Zbl

[136] Groeneboom P., “Limit theorems for convex hulls”, Probab. Theory Relat. Fields, 79 (1988), 327–368 | DOI | MR | Zbl

[137] Gross W., “Über affine Geometrie”, XIII, Ber. Verh. Sächs. Acad. Wis. Leipzig. Math.-Nat., 70 (1918), 38–54 | Zbl

[138] Gruber P. M., “In most cases approximation is irregular”, Rend. Sem. Mat. Univers. Torino, 41 (1983), 19–33 | MR | Zbl

[139] Gruber P. M., “Volume approximation of convex bodies by inscribed polytopes”, Math. Ann., 281 (1988), 229–245 | DOI | MR | Zbl

[140] Gruber P. M., “Volume approximation of convex bodies by circumscribed polytopes”, Applied Geometry and Discrette Mathematics, DIMACS Ser., 4, Amer. Math. Soc., 1991, 309–317 | MR

[141] Gruber P. M., “The space of convex bodies”, Handbook of Convex Geometry, Elsevier, 1993, 301–317 | MR

[142] Gruber P. M., “Aspects of approximation of convex bodies”, Handbook of Convex Geometry, Elsevier, 1993, 319–345 | MR

[143] Gruber P. M., “Asimptotic estimates for best and stepwise approximation of convex bodies, I”, Forum Math., 5 (1993), 281–297 | DOI | MR | Zbl

[144] Gruber P. M., “Asimptotic estimates for best and stepwise approximation of convex bodies, II”, Forum Math., 5 (1993), 521–537 | DOI | MR | Zbl

[145] Gruber P. M., “Approximation by convex polytopes”, Polytopes: Abstract, Convex and Computational, Proc. NATO Adv. Study Inst. (Scarborough, Ontario, Canada, Aug. 20—Sept. 3, 1993), 440, Kluwer Academic Publishers, Math. Phys. Sci., Dordrecht, 1994, 173–203 | MR | Zbl

[146] Gruber P. M., “Comparision of best and random approximation of convex bodies by polytopes”, Rend. Circ. Math. Palermo (2), 50 (1997), 189–216 | MR | Zbl

[147] Gruber P. M., “A short analytic proof of Fejes Tóth's theorem on sums of moments”, Aequationes Math., 58 (1999), 291–295 | DOI | MR | Zbl

[148] Gruber P. M., “Error of asymptotic formulae for volume approximation of convex bodies in $E^3$”, Tr. mat. in-ta im. V. A. Steklova, 239, 2002, 106–117 | MR | Zbl

[149] Gruber P. M., “Error of asymptotic formulae for volume approximation of convex bodies in $E^3$”, Monatsh. Math., 135 (2002), 271–304 | MR

[150] Gruber P. M., Kenderov P., “Approximation of convex bodies by polytopes”, Rend. Circ. Mat. Palermo (2), 31 (1982), 195–225 | DOI | MR | Zbl

[151] Guo Q., Kajiser S., “Approximation of convex bodies by convex bodies”, Northeast Math. J., 19 (2003), 323–332 | MR | Zbl

[152] Hadwiger H., “Volumschätzung für die eine Eikörper überdeckenden und unterdeckenden Parallelotope”, Elem. Math., 10 (1955), 122–124 | MR | Zbl

[153] Hayes A. C., Larman D. G., “The verticies of the knapsak polytope”, Discr. Appl. Math., 6 (1983), 135–138 | DOI | MR | Zbl

[154] Hueter I., “The convex hull of a normal sample”, Adv. Appl. Probab., 26 (1994), 855–875 | DOI | MR | Zbl

[155] Hueter I., “Limit theorems for the convex hull of random points in higher dimensions”, Trans. Amer. Math. Soc., 351 (1999), 4337–4363 | DOI | MR | Zbl

[156] Hug D., Munsonius G. O., Reitzner M., “Asymptotic mean values of Gaussian polytopes”, Beitr. Algebra Geom., 45 (2004), 531–548 | MR | Zbl

[157] Hug D., Reitzner M., “Gaussian polytopes: variances and limit theorems”, Adv. Appl. Probab., 37 (2005), 297–320 | DOI | MR | Zbl

[158] Johansen S., “The extremal convex functions”, Math. Scand., 34 (1974), 61–68 | MR | Zbl

[159] Kakutani S., “A proof that there exists a circumscribing cube around any bounded closed convex sets in $R^3$”, Ann. Math., 43 (1942), 739–741 | DOI | MR | Zbl

[160] Kannan R., Lovcsz L., Simonovits M., “Random walks and an $O^*(n^5)$ volume algorithm for convex bodies”, Random Struct. Algorithms, 11 (1997), 1–50 | 3.0.CO;2-X class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[161] Kenderov P., “Approximation of plane convex compacta by polygons”, Dokl. B'lg. AN, 33 (1980), 889–891 | MR | Zbl

[162] Kenderov P., “Polygonal approximation of plane convex compacta”, J. Approx. Theory, 38 (1983), 221–239 | DOI | MR | Zbl

[163] Küfer K.-H., “On the approximation of a ball by random polytopes”, Adv. Appl. Probab., 26 (1994), 876–892 | DOI | MR | Zbl

[164] Klee V., “Facet-centroids and volume minimization”, Stud. Sci. Math. Hungar., 21 (1986), 143–147 | MR | Zbl

[165] Klee V., Laskowski M. C., “Finding the smallest triangle containing a given convex polygon”, J. Algorithms, 6 (1985), 359–366 | DOI | MR

[166] Kochol M., “A note on approximation of a ball by polytopes”, Discr. Optim., 1 (2004), 229–231 | DOI | MR | Zbl

[167] Kosinński A., “A proof of an Auerbach–Banach–Mazur–Ulam theorem on convex bodies”, Colloq. Math., 4 (1957), 216–218 | MR | Zbl

[168] Kylzow D., Kuba A., Volcic A., “An algorithm for reconstructing convex bodies from their projections”, Discr. Comput. Geom., 4 (1989), 205–237 | DOI | MR

[169] Lángi Z., “On seven points on the boundary of a plane convex body in large relative distances”, Contrib. Algebra Geom., 45 (2004), 275–281 | MR | Zbl

[170] Lassak M., “Approximation of convex bodies by parallelotopes”, Bull. Pol. Acad. Sci., Ser. Math., 39 (1991), 219–233 | MR

[171] Lassak M., “On five points in a plane convex body pairwise in at least unit relative distances”, Intuitive geometry (Szeged, 1991), Colloq. Math. Soc. János Bolyai, 63, North-Holland, Amsterdam, 1994, 245–247 | MR | Zbl

[172] Lassak M., “Approximation of convex bodies by triangles”, Proc. Amer. Math. Soc., 115 (1992), 207–210 | DOI | MR | Zbl

[173] Lassak M., “Approximation of convex bodies by rectangles”, Geom. Dedic., 47 (1993), 111–117 | DOI | MR | Zbl

[174] Lassak M., “Relationship between widths of a convex body and of inscribed parallelotope”, Bull. Austr. Math. Soc., 63 (2001), 133–140 | DOI | MR | Zbl

[175] Lassak M., “Affine-regular hexagons of extreme areas inscribed in a centrally symmetric convex body”, Adv. Geom., 3 (2003), 45–51 | DOI | MR | Zbl

[176] Lassak M., “On relatively equilateral polygons inscribed in a convex body”, Publ. Math. Debrecen, 65 (2004), 133–148 | MR | Zbl

[177] Levi F. W., “Über zwei Sätze von Herrn Besicovitch”, Arch. Math., 3 (1952), 125–129 | DOI | MR | Zbl

[178] Lopez M. A., Reisner S., “Efficient approximation of convex polygons”, Int. J. Comput. Geom. Appl., 10 (2000), 445–452 | DOI | MR | Zbl

[179] Lopez M. Reisner S., “Linear time approximation of 3D convex polytopes”, Comput. Geom., 23 (2002), 291–301 | DOI | MR | Zbl

[180] Lovász L., Simonovits M., “Random walks in a convex body and an improved volume algorithm”, Random Struct. Algorithms, 4 (1993), 359–412 | DOI | MR | Zbl

[181] Ludwig M., Asymptotische Approximation Konvexer Körper, Ph. D. Thesis, Techn. Univ. Vienna, 1992

[182] Ludwig M., “Asymptotic Approximation of convexe curves”, Arch. Math., 63 (1994), 377–384 | DOI | MR | Zbl

[183] Ludwig M., “Asymptotic approximation of convex curves: the Hausdorf metric case”, Arch. Math., 70 (1998), 331–336 | DOI | MR | Zbl

[184] Ludwig M., “A characterization of affine length and asymptotic approximation of convex discs”, Abh. Math. Semin. Univ. Hamb., 69 (1999), 75–88 | DOI | MR | Zbl

[185] Ludwig M., “Asymptotic approximation of smooth convex bodies by general polytopes”, Mathematica, 46 (1999), 103–125 | MR | Zbl

[186] Macbeath A. M., “An extremal property of the hypersphere”, Proc. Cambrige Philos. Soc., 47 (1951), 245–247 | DOI | MR | Zbl

[187] Macbeath A. M., “Compactness theorem for affine equivalence classes of convex regions”, Can. J. Math., 3 (1951), 54–61 | DOI | MR | Zbl

[188] Massü B., “On the LLN for the number of vertices of a random convex hull”, Adv. Appl. Probab., 32 (2000), 675–681 | DOI | MR

[189] McClure D. E., Vitalie R. A., “Polygonal approximation of plane convex bodies”, J. Math. Anal. Appl., 51 (1975), 326–358 | DOI | MR | Zbl

[190] Müller J. S., “Approximation of a ball by random polytopes”, J. Approx. Theory, 63 (1990), 198–209 | DOI | MR | Zbl

[191] Niederreiter H., “On a measure of denseness for sequences”, Topics in Classical Number Theory, Colloq. Math. Soc. Janós Bolyai, 34, 1984, 1163–1208 | MR | Zbl

[192] Novotný P., “Approximation of convex sets by simplexes”, Geom. Dedic., 50 (1994), 53–55 | DOI | MR | Zbl

[193] O'Rourke J., “Finding minimal enclosing boxes”, Int. J. Comput. Inform Sci., 14 (1985), 183–199 | DOI | MR

[194] O'Rourke J., Aggarwal A., Meddila S., Baldwin M., “An optimal algorithm for finding minimal enclosing triangle”, J. Algorithms, 7 (1986), 258–269 | DOI | MR

[195] Packer A., “Polynomial-time approximation of largest simplices in $V$-polytopes”, Discr. Appl.Math., 134 (2004), 213–237 | DOI | MR | Zbl

[196] Palmon O., “The only convex body with extremal distance from the ball is the simplex”, Isr. J. Math., 80 (1992), 337–349 | DOI | MR | Zbl

[197] Pelczynski A., Szarek S. J., “On parallelepiped of minimal volume containing a convex symmetric body in $R^n$”, Math. Proc. Cambridge Phil. Soc., 109 (1991), 125–148 | DOI | MR | Zbl

[198] Petty C. M., “On the geometry of the Minkowski plane”, Riv. Mat. Univ. Parma, 6 (1955), 269–292 | MR | Zbl

[199] Radziszewski K., “Sur un problème extremal relatif aux figures inscrites et circonscrite aux figures convexes”, Ann. Univ. Mariae Curie-Sclodowska, Sec. A, 6 (1952), 5–18 | MR

[200] Reitzner M., “Inequalities for convex hulls of random points”, Monatsh. Math., 131 (2000), 71–78 | DOI | MR | Zbl

[201] Reitzner M., “Stochastical approximation of smooth convex bodies”, Proc. Conf. “Konvexgeometrie” (Oberwolfach, Apr. 22–28, 2001), 18, Tagungsber. Math. Forcshungsist, Oberwolfach, 2001, 14

[202] Reitzner M., “Random points on the boundary of smooth convex bodies”, Trans. Amer. Math. Soc., 354 (2002), 2243–2278 | DOI | MR | Zbl

[203] Reitzner M., “Random polytopes and the Efron–Stein jackknife inequality”, Ann. Probab., 31 (2003), 2136–2166 | DOI | MR | Zbl

[204] Reitzner M., “The combinatorial structure of random polytopes”, Adv. Math., 191 (2005), 178–208 | DOI | MR | Zbl

[205] Reisner S., Schütt C., Werner E., “Dropping a vertex or a facet from a convex polytope”, Forum Math., 13 (2002), 359–378 | DOI | MR

[206] Rényi A., Sulanke R., “Über die konvexe Hülle von $n$ zufällig gewählten Punkten”, Z. Wahrscheinlichkeitsth, 2 (1963), 75–84 | DOI | MR | Zbl

[207] Rote G., “The convergence rate for the Sandwich algorithm for approximating convex figures in the plane”, Proc. 2nd Canad. Conf. on Comput. Geometry, Ottava, 1990, 287–290

[208] Rote G., “The convergence rate of the Sandwich algorithm for approximating convex functions”, Computing, 48 (1992), 337–361 | DOI | MR | Zbl

[209] Ryabchenko V. V., Lyashko S. I., Grushets'ki O. N., Rublyov B. V., “A new algorithm of linear complexity for finding triangles of maximal area inscribed in convex polygon”, Visn., Kyiv. Univ. Ser. Fiz.-Mat., 2 (2003), 210–214 | MR | Zbl

[210] Sas E., “Ber eine Extremaleigenschalf der Ellipsen”, Compos. Math., 6 (1939), 468–470 | MR | Zbl

[211] Shephard G. C., “Decomposable convex polyhedra”, Mathematica, 10 (1963), 89–95 | MR | Zbl

[212] Schneider R., “Zwei Extremalaufgaben für konvexer Bereiche”, Acta Math. Acad. Sci. Hung., 22 (1971), 379–383 | DOI | MR

[213] Schneider R., “Zur optimalen Approximation konvexer Hyperflachen durch Polyeder”, Math. Ann., 256 (1981), 289–301 | DOI | MR | Zbl

[214] Schneider R., “Affinne-invariant approximation by convex polytopes”, Stud. Sci. Math. Hung., 21 (1986), 401–408 | MR | Zbl

[215] Schneider R., “Polyhedral approximation of smooth convex bodies”, J. Math. Anal. Appl., 128 (1987), 470–474 | DOI | MR | Zbl

[216] Schneider R., “Random approximation of convex sets”, J. Microscopy, 151 (1988), 211–227.

[217] Schneider R., Wieacker J. A., “Approximation of convex bodies by polytopes”, Bull. London Math. Soc., 13 (1981), 149–156 | DOI | MR | Zbl

[218] Schütt C., “The convex floating body and polyhedral approximation”, Isr. J. Math., 73 (1991), 65–77 | DOI | MR | Zbl

[219] Schwarzkopf O., Futchs U., Rote G., Welzl E., “Approximation of convex figures by pairs of rectangulars”, Comput. Geom., 10 (1998), 77–87 | DOI | MR | Zbl

[220] Sonnevand G., “An optimal sequential algorithm for the uniform approximation of convex functions on $[0,1]^2$”, Appl. Math. Optim., 10 (1983), 127–142 | DOI | MR

[221] Süss W., “Über Parallelogramme und Rechtecke, die sich ebenen Eibereichen einschreben lassen”, Rend. Math. Appl., 14 (1955), 338–341 | MR | Zbl

[222] Tabachnikov S., “On the dual billiard problem”, Adv. Math., 115 (1995), 221–249 | DOI | MR | Zbl

[223] Valtr P., “Probability that $n$ random points are in convex position”, Discr. Comput. Geom., 13 (1995), 637–643 | DOI | MR | Zbl

[224] Valtr P., “The probability that $n$ random points in a triangle are in convex position”, Combinatorica, 16 (1996), 567–573 | DOI | MR | Zbl

[225] Vershik A. M., Sporyshev P. V., “Asymptotic behavior of the number of faces of random polyhedra and the neighborliness problem”, Sel. Math. Sov., 11 (1992), 181–201 | MR | Zbl

[226] Vershik A. M., Zeitouni O., “Large deviations in the geometry of complex lattice polygons”, Isr. J. Math., 109 (1999), 13–27 | DOI | MR | Zbl

[227] Wieaker J. A., Eintre Probleme der polyedrishen Approximation, Diplomarbeit, Univ. Freiburg, 1978

[228] Zhivkov N. V., “Plane polygonal approximation of bounded convex sets”, Dokl. B'lg. AN, 35 (1982), 1631–1634 | MR

[229] Zhou Y., Suri S., “Algoritms for minimum volume enclosing simplex in three dimensions”, SIAM J. Comput., 31 (2002), 1339–1357 | DOI | MR | Zbl

[230] Ziegler G. M., “Lectures on $0/1$-polytopes”, Polytopes—combinatorics and computation (Oberwolfach, 1997), DMV Sem., 29, Birkhäuser, Basel, 2000, 1–41 | MR | Zbl