Anvelopă convexă: Diferență între versiuni

Conținut șters Conținut adăugat

Aliniat

Versiunea de la 7 ianuarie 2021 20:11

În geometrie, anvelopa convexă sau închiderea convexă a unei forme este cea mai mică mulțime convexă care o conține. Anvelopa convexă poate fi definită fie ca intersecția tuturor mulțimilor convexe care conțin o submulțime dată a spațiului euclidian, fie ca mulțimea tuturor combinațiilor convexe^⁠(d) ale punctelor din submulțimea dată. Pentru o porțiune dintr-un plan, anvelopa convexă poate fi vizualizată printr-un fir de cauciuc întins în jurul porțiunii.

Anvelopa convexă a unei mulțimi deschise este una deschisă, iar anvelopa convexă a unei mulțimi compacte este una compactă. Orice mulțime convexă compactă este anvelopa convexă a punctelor sale extreme^⁠(d). Operatorul „anvelopă convexă” este un exemplu de operator de închidere^⁠(d), iar orice antimatroid^⁠(d) poate fi reprezentat prin aplicarea acestui operator de închidere la o mulțime finită de puncte. Problema algoritmilor de trasare a anvelopei convexe a unei mulțimi finite de puncte din plan sau alte spații euclidiene cu dimensiuni inferioare, precum și problema duală a intersectării semispațiilor, sunt probleme fundamentale ale geometriei algoritmice^⁠(d). Pentru mulțimi situate în plan sau în spațiul tridimensional, acestea pot fi rezolvate cu resurse de calcul de complexitatea $O(n\log n)$ , iar pentru dimensiuni superioare, în cel mai rău caz cu resurse de calcul de complexitatea dată de teorema limitei superioare^⁠(d).

La fel ca pentru mulțimi de puncte, anvelopa convexă a fost studiată pentru poligoane simple, mișcare browniană, curbe în spațiu și epigrafele funcțiilor^⁠(d). Anvelopa convexă are numeroase aplicații în matematică, statistică, optimizare combinatorială, economie, modelare geometrică și etologie. Structurile conexe includ anvelopa convexă ortogonală^⁠(d), straturile convexe^⁠(d), triangulația Delaunay și placarea Voronoi^⁠(d).

Definiții

Anvelopa convexă a unei mulțimi mărginite din plan: analogia firului de cauciuc

O mulțime de puncte din spațiul euclidian este definită drept convexă dacă conține toate segmentele care unesc oricare pereche de puncte ale sale. Anvelopa convexă a unei mulțimi $X$ date poate fi definită prin:^[1]

Mulțimea convexă minima (unică) conținând $X$
Intersecția tuturor mulțimilor convexe conținând $X$
Mulțimea tuturor combinațiilor convexe de puncte din $X$
Reuniunea tuturor simplexurilor cu vârfuri în $X$

Pentru o mulțime cu frontieră din planul euclidian, cu elemente necoliniare, frontiera anvelopei convexe este linia închisă cu perimetrul minim conținând pe $X$ . Se poate imagina întinderea unui fir de cauciuc în jurul întregii mulțimi $S$ , iar apoi, eliberându-l, el se strânge; când se oprește, el închide anvelopa convexă a $S$ .^[2] Această formulare nu se poate generaliza imediat pentru dimensiuni superioare: pentru o mulțime finită de puncte din spațiul tridimensional, o vecinătate a arborelui de acoperire^⁠(d) al punctelor le include cu o suprafață arbitrar de mică, mai mică decât suprafața anvelopei convexe.^[3] Cu toate acestea, în dimensiuni superioare, variante ale problemei obstacolelor^⁠(d) de a găsi o suprafață cu energie minimă pe deasupra unei forme date poate avea drept soluție anvelopa convexă.^[4]

Pentru obiectele tridimensionale, prima definiție afirmă că anvelopa convexă este cel mai mic posibil volum de delimitare^⁠(d) convex al obiectelor. Definiția pe baza intersecției mulțimilor convexe poate fi extinsă la geometriile neeuclidiene, iar definiția pe baza combinațiilor convexe poate fi extinsă la un spațiu vectorial real sau la un spațiu afin oarecare; anvelopa convexă poate fi generalizată abstract în cadrul matroizilor orientați^⁠(d).^[5]

Note

^ Rockafellar (1970), p. 12.
^ de Berg et al. (2008), p. 3.
^ Williams & Rossignac (2005). Vezi și Douglas Zare, answer to "the perimeter of a non-convex set", MathOverflow, May 16, 2014.
^ Oberman (2007).
^ Knuth (1992).

Bibliografie

Andrew, A. M. (1979), „Another efficient algorithm for convex hulls in two dimensions”, Information Processing Letters, 9 (5): 216–219, doi:10.1016/0020-0190(79)90072-3
Artin, Emil (1967), „2.5. Newton's Polygon”, Algebraic Numbers and Algebraic Functions, Gordon and Breach, pp. 37–43, MR 0237460
Auel, Asher (2019), „The mathematics of Grace Murray Hopper” (PDF), Notices of the American Mathematical Society, 66 (3): 330–340, MR 3889348
Avis, David; Bremner, David; Seidel, Raimund (1997), „How good are convex hull algorithms?”, Computational Geometrie, 7 (5-6): 265–301, doi:10.1016/S0925-7721(96)00023-5, MR 1447243
Bárány, Imre; Katchalski, Meir; Pach, János (1982), „Quantitative Helly-type theorems”, Proceedings of the American Mathematical Society, 86 (1): 109–114, doi:10.2307/2044407, MR 0663877
Basch, Julien; Guibas, Leonidas J.; Hershberger, John (1999), „Data structures for mobile data”, Journal of Algorithms, 31 (1): 1–28, CiteSeerX 10.1.1.134.6921 , doi:10.1006/jagm.1998.0988, MR 1670903
Birkhoff, Garrett (1935), „Integration of functions with values in a Banach space”, Transactions of the American Mathematical Society, 38 (2): 357–378, doi:10.2307/1989687, MR 1501815
Brown, K. Q. (1979), „Voronoi diagrams from convex hulls”, Information Processing Letters, 9 (5): 223–228, doi:10.1016/0020-0190(79)90074-7
de Berg, M.; van Kreveld, M.; Overmars, Mark; Schwarzkopf, O. (2008), Computational Geometrie: Algorithms and Applications (ed. 3rd), Springer
Chan, Timothy M. (2012), „Three problems about dynamic convex hulls”, International Journal of Computational Geometrie and Applications, 22 (4): 341–364, doi:10.1142/S0218195912600096, MR 2994585
Chang, J. S.; Yap, C.-K. (1986), „A polynomial solution for the potato-peeling problem”, Discrete & Computational Geometrie, 1 (2): 155–182, doi:10.1007/BF02187692 , MR 0834056
Chazelle, Bernard (1985), „On the convex layers of a planar set”, IEEE Transactions on Information Theory, 31 (4): 509–517, doi:10.1109/TIT.1985.1057060, MR 0798557
Chazelle, Bernard (1993), „An optimal convex hull algorithm in any fixed dimension” (PDF), Discrete & Computational Geometrie, 10 (1): 377–409, CiteSeerX 10.1.1.113.8709 , doi:10.1007/BF02573985
Chen, Qinyu; Wang, Guozhao (martie 2003), „A class of Bézier-like curves”, Computer Aided Geometric Design, 20 (1): 29–39, doi:10.1016/s0167-8396(03)00003-7
Cranston, M.; Hsu, P.; March, P. (1989), „Smoothness of the convex hull of planar Brownian motion”, Annals of Probability, 17 (1): 144–150, JSTOR 2244202, MR 0972777
Demaine, Erik D.; Gassend, Blaise; O'Rourke, Joseph; Toussaint, Godfried T. (2008), „All polygons flip finitely ... right?”, Surveys on Discrete and Computational Geometrie, Contemporary Mathematics, 453, Providence, Rhode Island: American Mathematical Society, pp. 231–255, doi:10.1090/conm/453/08801, MR 2405683
Dines, L. L. (1938), „On convexity”, American Mathematical Monthly, 45 (4): 199–209, doi:10.2307/2302604, JSTOR 2302604, MR 1524247
Dirnböck, Hans; Stachel, Hellmuth (1997), „The development of the oloid” (PDF), Journal for Geometrie and Graphics, 1 (2): 105–118, MR 1622664
Edelsbrunner, Herbert; Kirkpatrick, David G.; Seidel, Raimund (1983), „On the shape of a set of points in the plane”, IEEE Transactions on Information Theory, 29 (4): 551–559, doi:10.1109/TIT.1983.1056714
Epstein, D. B. A.; Marden, A. (1987), „Convex hulls in hyperbolic space, a theorem of Sullivan, and measured pleated surfaces”, În Epstein, D. B. A., Analytical and geometric aspects of hyperbolic space (Coventry/Durham, 1984), London Mathematical Society Lecture Note Series, 111, Cambridge: Cambridge University Press, pp. 113–253, MR 0903852
Escobar, Laura; Kaveh, Kiumars (septembrie 2020), „Convex polytopes, algebraic geometrie, and combinatorics” (PDF), Notices of the American Mathematical Society, 67 (8): 1116–1123
Gardner, L. Terrell (1984), „An elementary proof of the Russo-Dye theorem”, Proceedings of the American Mathematical Society, 90 (1): 171, doi:10.2307/2044692, MR 0722439
Gel'fand, I. M.; Kapranov, M. M.; Zelevinsky, A. V. (1994), „6. Newton Polytopes and Chow Polytopes”, Discriminants, Resultants, and Multidimensional Determinants, Mathematics: Theory & Applications, Birkhäuser, pp. 193–213, doi:10.1007/978-0-8176-4771-1, ISBN 0-8176-3660-9, MR 1264417
Getz, Wayne M.; Wilmers, Christopher C. (2004), „A local nearest-neighbor convex-hull construction of home ranges and utilization distributions” (PDF), Ecography, Wiley, 27 (4): 489–505, doi:10.1111/j.0906-7590.2004.03835.x
Graham, Ronald L.; Yao, F. Frances (1983), „Finding the convex hull of a simple polygon”, Journal of Algorithms, 4 (4): 324–331, doi:10.1016/0196-6774(83)90013-5, MR 0729228
Grünbaum, Branko (2003), Convex Polytopes, Graduate Texts in Mathematics, 221 (ed. 2nd), Springer, ISBN 9780387004242
Gustin, William (1947), „On the interior of the convex hull of a Euclidean set”, Bulletin of the American Mathematical Society, 53: 299–301, doi:10.1090/S0002-9904-1947-08787-5 , MR 0020800
Harris, Bernard (1971), „Mathematical models for statistical decision theory” (PDF), Optimizing methods in statistics (Proc. Sympos., Ohio State Univ., Columbus, Ohio, 1971), pp. 369–389, MR 0356305
Herrlich, Horst (1992), „Hyperconvex hulls of metric spaces”, Proceedings of the Symposium on General Topology and Applications (Oxford, 1989), Topology and its Applications, 44 (1-3): 181–187, doi:10.1016/0166-8641(92)90092-E, MR 1173256
Johnson, Charles R. (1976), „Normality and the numerical range”, Linear Algebra and its Applications, 15 (1): 89–94, doi:10.1016/0024-3795(76)90080-x , MR 0460358
Kashiwabara, Kenji; Nakamura, Masataka; Okamoto, Yoshio (2005), „The affine representation theorem for abstract convex geometries”, Computational Geometrie, 30 (2): 129–144, CiteSeerX 10.1.1.14.4965 , doi:10.1016/j.comgeo.2004.05.001, MR 2107032
Katoh, Naoki (1992), „Bicriteria network optimization problems”, IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences, E75-A: 321–329
Kernohan, Brian J.; Gitzen, Robert A.; Millspaugh, Joshua J. (2001), „Analysis of animal space use and movements”, În Millspaugh, Joshua; Marzluff, John M., Radio Tracking and Animal Populations, Academic Press, ISBN 9780080540221
Kirkpatrick, K. A. (2006), „The Schrödinger–HJW theorem”, Foundations of Physics Letters, 19 (1): 95–102, arXiv:quant-ph/0305068 , doi:10.1007/s10702-006-1852-1
Kiselman, Christer O. (2002), „A semigroup of operators in convexity theory”, Transactions of the American Mathematical Society, 354 (5): 2035–2053, doi:10.1090/S0002-9947-02-02915-X , MR 1881029
Knuth, Donald E. (1992), Axioms and Hulls, Lecture Notes in Computer Science, 606, Heidelberg: Springer-Verlag, doi:10.1007/3-540-55611-7, ISBN 3-540-55611-7, MR 1226891
Kőnig, Dénes (decembrie 1922), „Über konvexe Körper”, Mathematische Zeitschrift, 14 (1): 208–210, doi:10.1007/bf01215899 ; see also review by Hans Rademacher (1922), Format:JFM
Krein, Mark; Milman, David (1940), „On extreme points of regular convex sets”, Studia Mathematica, 9: 133–138
Krein, M.; Šmulian, V. (1940), „On regularly convex sets in the space conjugate to a Banach space”, Annals of Mathematics, Second Series, 41: 556–583, doi:10.2307/1968735, hdl:10338.dmlcz/100106 , JSTOR 1968735, MR 0002009
Laurentini, A. (1994), „The visual hull concept for silhouette-based image understanding”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 16 (2): 150–162, doi:10.1109/34.273735
Lay, Steven R. (1982), Convex Sets and their Applications, John Wiley & Sons, ISBN 0-471-09584-2, MR 0655598
Lee, D. T. (1983), „On finding the convex hull of a simple polygon”, International Journal of Computer and Information Sciences, 12 (2): 87–98, doi:10.1007/BF00993195, MR 0724699
Mason, Herbert B. (1908), Encyclopaedia of Ships and Shipping, p. 698
McCallum, Duncan; Avis, David (1979), „A linear algorithm for finding the convex hull of a simple polygon”, Information Processing Letters, 9 (5): 201–206, doi:10.1016/0020-0190(79)90069-3, MR 0552534
Newton, Isaac (24 octombrie 1676), „Letter to Henry Oldenburg”, The Newton Project, University of Oxford
Nicola, Piercarlo (2000), „General Competitive Equilibrium”, Mainstream Mathematical Economics in the 20th Century, Springer, pp. 197–215, doi:10.1007/978-3-662-04238-0_16
Nilsen, Erlend B.; Pedersen, Simen; Linnell, John D. C. (2008), „Can minimum convex polygon home ranges be used to draw biologically meaningful conclusions?”, Ecological Research, 23 (3): 635–639, doi:10.1007/s11284-007-0421-9
Oberman, Adam M. (2007), „The convex envelope is the solution of a nonlinear obstacle problem”, Proceedings of the American Mathematical Society, 135 (6): 1689–1694, doi:10.1090/S0002-9939-07-08887-9 , MR 2286077
Okon, T. (2000), „Choquet theory in metric spaces”, Zeitschrift für Analysis und ihre Anwendungen, 19 (2): 303–314, doi:10.4171/ZAA/952, MR 1768994
Ottmann, T.; Soisalon-Soininen, E.; Wood, Derick (1984), „On the definition and computation of rectilinear convex hulls”, Information Sciences, 33 (3): 157–171, doi:10.1016/0020-0255(84)90025-2
Prasolov, Victor V. (2004), „1.2.1 The Gauss–Lucas theorem”, Polynomials, Algorithms and Computation in Mathematics, 11, Springer, pp. 12–13, doi:10.1007/978-3-642-03980-5, ISBN 3-540-40714-6, MR 2082772
Pulleyblank, W. R. (1983), „Polyhedral combinatorics”, În Bachem, Achim; Korte, Bernhard; Grötschel, Martin, Mathematical Programming: The State of the Art (XIth International Symposium on Mathematical Programming, Bonn 1982), Springer, pp. 312–345, doi:10.1007/978-3-642-68874-4_13
Rappoport, Ari (1992), „An efficient adaptive algorithm for constructing the convex differences tree of a simple polygon”, Computer Graphics Forum, 11 (4): 235–240, doi:10.1111/1467-8659.1140235
Reay, John R. (1979), „Several generalizations of Tverberg's theorem”, Israel Journal of Mathematics, 34 (3): 238–244 (1980), doi:10.1007/BF02760885, MR 0570883
Rieffel, Eleanor G.; Polak, Wolfgang H. (2011), Quantum Computing: A Gentle Introduction, MIT Press, pp. 215–216, ISBN 978-0-262-01506-6
Rockafellar, R. Tyrrell (1970), Convex Analysis, Princeton Mathematical Series, 28, Princeton, N.J.: Princeton University Press, MR 0274683
Rossi, Hugo (1961), „Holomorphically convex sets in several complex variables”, Annals of Mathematics, Second Series, 74: 470–493, doi:10.2307/1970292, JSTOR 1970292, MR 0133479
Rousseeuw, Peter J.; Ruts, Ida; Tukey, John W. (1999), „The bagplot: A bivariate boxplot”, The American Statistician, 53 (4): 382–387, doi:10.1080/00031305.1999.10474494
Sakuma, Itsuo (1977), „Closedness of convex hulls”, Journal of Economic Theory, 14 (1): 223–227, doi:10.1016/0022-0531(77)90095-3
Schneider, Rolf (1993), Convex Bodies: The Brunn–Minkowski Theory, Encyclopedia of Mathematics and its Applications, 44, Cambridge: Cambridge University Press, doi:10.1017/CBO9780511526282, ISBN 0-521-35220-7, MR 1216521
Seaton, Katherine A. (2017), „Sphericons and D-forms: a crocheted connection”, Journal of Mathematics and the Arts, 11 (4): 187–202, arXiv:1603.08409 , doi:10.1080/17513472.2017.1318512, MR 3765242
Sedykh, V. D. (1981), „Structure of the convex hull of a space curve”, Trudy Seminara imeni I. G. Petrovskogo (6): 239–256, MR 0630708 , translated in Journal of Soviet Mathematics 33 (4): 1140–1153, 1986, doi:10.1007/BF01086114
Sontag, Eduardo D. (1982), „Remarks on piecewise-linear algebra”, Pacific Journal of Mathematics, 98 (1): 183–201, MR 0644949
Steinitz, E. (1914), „Bedingt konvergente Reihen und konvexe Systeme. (Fortsetzung)”, Journal für die Reine und Angewandte Mathematik, 144: 1–40, doi:10.1515/crll.1914.144.1, MR 1580890
Talman, Louis A. (1977), „Fixed points for condensing multifunctions in metric spaces with convex structure”, Kōdai Mathematical Seminar Reports, 29 (1-2): 62–70, MR 0463985
Toussaint, Godfried (1983), „Solving geometric problems with the rotating calipers”, Proceedings of IEEE MELECON '83, Athens, CiteSeerX 10.1.1.155.5671 
Toussaint, Godfried (1986), „An optimal algorithm for computing the relative convex hull of a set of points in a polygon”, Proceedings of EURASIP, Signal Processing III: Theories and Applications, Part 2, North-Holland, pp. 853–856
Weeks, Jeffrey R. (1993), „Convex hulls and isometries of cusped hyperbolic 3-manifolds”, Topology and Its Applications, 52 (2): 127–149, doi:10.1016/0166-8641(93)90032-9, MR 1241189
Westermann, L. R. J. (1976), „On the hull operator”, Indagationes Mathematicae, 38 (2): 179–184, doi:10.1016/1385-7258(76)90065-2 , MR 0404097
White, F. Puryer (aprilie 1923), „Pure mathematics”, Science Progress in the Twentieth Century, 17 (68): 517–526, JSTOR 43432008
Whitley, Robert (1986), „The Kreĭn-Šmulian theorem”, Proceedings of the American Mathematical Society, 97 (2): 376–377, doi:10.2307/2046536, MR 0835903
Williams, Jason; Rossignac, Jarek (2005), „Tightening: curvature-limiting morphological simplification”, În Kobbelt, Leif; Shapiro, Vadim, Proceedings of the Tenth ACM Symposium on Solid and Physical Modeling 2005, Cambridge, Massachusetts, USA, June 13-15, 2005, ACM, pp. 107–112, doi:10.1145/1060244.1060257, hdl:1853/3736
Worton, Bruce J. (1995), „A convex hull-based estimator of home-range size”, Biometrics, 51 (4): 1206–1215, doi:10.2307/2533254, JSTOR 2533254

Legături externe

en Convex hull (română Anvelopa convexă) la Encyclopedia of Mathematics, EMS Press, Springer, 2001
en Convex Hull, (română Anvelopa convexă) la Mathworld

[FOOTNOTERockafellar197012-1] Rockafellar (1970), p. 12.

[FOOTNOTEde_Bergvan_KreveldOvermarsSchwarzkopf20083-2] Berg et al. (2008), p. 3.

[3] Williams & Rossignac (2005). Vezi și Douglas Zare, answer to "the perimeter of a non-convex set", MathOverflow, May 16, 2014.

[FOOTNOTEOberman2007-4] Oberman (2007).

[FOOTNOTEKnuth1992-5] Knuth (1992).

[1]

[2]

[3]

[4]

[5]