Konveksni skup

Ilustracija konveksnog skupa koji izgleda donekle poput deformisanog kruga. Crni linijski segment koji povezuje tačke x i kompletno leži unutar (zelenog) skupa. Budući da je to tačno za bilo koje tačke x i y unutar skupa koje se mogu izabrati, skup je konveksan.
Ilustracija nekonveksnog skupa. Kako (crveni) deo (crngo i crvenog) linijskog-segmenta koji povezuje tačke x i y leži izvan (zelenog) skupa, skup je nekonveksan.

U geometriji, podskup Euklidovog prostora, ili specifičnije afini prostor nad realnim brojevima, je konveksan ako, sa bilo koje dve tačke, on povezuje ceo linijski segment koji ih povezuje. Ekvivalentno, konveksni skup ili konveksni region je podskup koji preseca svaku liniju u jednom linijskom segmentu (verovatno praznom).[1][2] Na primer, čvrsta kocka je konveksni skup, dok sve što je šuplje ili ima udubljenje, na primer, oblik polumeseca, nije konveksno.

Granica konveksnog skupa je uvek konveksna kriva. Presek svih konveksnih skupova koji sadrže dati podskup A Euklidovog prostora naziva se konveksni omotač A. To je najmanji konveksni skup koji sadrži A.

Konveksna funkcija je realno vrednosna funkcija definisana na intervalu sa svojstvom da je njegov epigraf (skup tačaka na ili iznad grafikona funkcije) konveksni skup. Konveksna minimizacija je potpolje optimizacije koje izučava problem minimizacije konveksnih funkcija nad konveksnim skupovima. Prva grana matemakia posvećena izučavanju svojstava konveksnih skupova i konveksnih funkcija se naziva konveksna analiza.

Pojam konveksnog skupa može se generalizovati, kao što je opisano u daljem tekstu.

Definicije

Funkcija je konveksna, ako i samo ako njen epigraf, region (obojen zeleno) iznad njenog grafikona (prikazan plavom linijuom), je konveksan set.

Neka je S vektorski prostor ili afini prostor nad realnim brojevima, ili, generalnije, nad nekim uređenim poljem. Ovim su obuhvaćeni Euklidovi prostori, koji su afini prostori. podskup C od S je konveksan ako je za svako x i y u C, linijski segment koji povezuje x i y uključen u C. To znači da afina kombinacija (1 − t)x + ty pripada C, za svako x i y u C, i t na intervalu [0, 1]. To podrazumeva da je konveksnost (svojstvo da je konveksan) invarijantna pod afinim trasformacijama. Time se isto tako podrazumeva da je konveksni skup u realnom ili kompleksnom topološkom vektorskom prostoru povezan putanjom, i stoga povezan.

Skup C je striktno konveksan ako je svaka tačka na linijskom segmentu koji povezuje x i y izuzev krajnjih tačaka u unutrašnjosti C.

Skup C je apsolutno konveksan ako je konveksan i balansiran.

Konveksni podskupovi iz R (skupa realnih brojeva) su intervali i tačke iz R. Neki primeri konveksnih podskupova Euklidske ravni su čvrsti pravilni mnogouglovi, čvrsti trouglovi i preseci čvrstih trouglova. Neki primeri konveksnih podskupova Euklidskog trodimenzionalnog prostora su Arhimedova tela i pravilni poliedri. Poliedri Kepler-Puansoa su primeri nekonveksnih skupova.

Nekonveksni skup

Skup koji nije koveksan se naziva nekonveksni skup. Mnogougao koji nije konveksni poligon se ponekad naziva konkavni poligon,[3] a neki izvori generalnije koriste termin konkavni skup sa značenjem nekonveksni skup,[4] mada ta upotreba većinom nije dozvoljena.[5][6]

Komplement konveksnog skupa, kao što je epigraf konkavne funkcije, se ponekad naziva reverzni konveksni skup, posebno u kontekstu matematičke optimizacije.[7]

Reference

  1. ^ Morris, Carla C.; Stark, Robert M. Finite Mathematics: Models and Applications (на језику: енглески). John Wiley & Sons. стр. 121. ISBN 9781119015383. Приступљено 5. 4. 2017. 
  2. ^ Kjeldsen, Tinne Hoff. „History of Convexity and Mathematical Programming” (PDF). Proceedings of the International Congress of Mathematicians (ICM 2010): 3233—3257. doi:10.1142/9789814324359_0187. Архивирано из оригинала (PDF) 11. 8. 2017. г. Приступљено 5. 4. 2017. 
  3. ^ McConnell, Jeffrey J. (2006), Computer Graphics: Theory Into Practice, стр. 130, ISBN 0-7637-2250-2 .
  4. ^ Weisstein, Eric W. „Concave”. MathWorld. 
  5. ^ Takayama, Akira (1994), Analytical Methods in Economics, University of Michigan Press, стр. 54, ISBN 9780472081356, „An often seen confusion is a "concave set". Concave and convex functions designate certain classes of functions, not of sets, whereas a convex set designates a certain class of sets, and not a class of functions. A "concave set" confuses sets with functions.” 
  6. ^ Corbae, Dean; Stinchcombe, Maxwell B.; Zeman, Juraj (2009), An Introduction to Mathematical Analysis for Economic Theory and Econometrics, Princeton University Press, стр. 347, ISBN 9781400833085, „There is no such thing as a concave set.” 
  7. ^ Meyer, Robert (1970), „The validity of a family of optimization methods” (PDF), SIAM Journal on Control and Optimization, 8: 41—54, MR 0312915 .

Literatura

  • 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, стр. 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 Geometry, 7 (5-6): 265—301, MR 1447243, doi:10.1016/S0925-7721(96)00023-5 
  • Bárány, Imre; Katchalski, Meir; Pach, János (1982), „Quantitative Helly-type theorems”, Proceedings of the American Mathematical Society, 86 (1): 109—114, MR 663877, doi:10.2307/2044407 
  • 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 Слободан приступ, MR 1670903, doi:10.1006/jagm.1998.0988 
  • Birkhoff, Garrett (1935), „Integration of functions with values in a Banach space”, Transactions of the American Mathematical Society, 38 (2): 357—378, MR 1501815, doi:10.2307/1989687 
  • 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 Geometry: Algorithms and Applications (3rd изд.), Springer 
  • Chan, Timothy M. (2012), „Three problems about dynamic convex hulls”, International Journal of Computational Geometry and Applications, 22 (4): 341—364, MR 2994585, doi:10.1142/S0218195912600096 
  • Chang, J. S.; Yap, C.-K. (1986), „A polynomial solution for the potato-peeling problem”, Discrete & Computational Geometry, 1 (2): 155—182, MR 834056, doi:10.1007/BF02187692 
  • Chazelle, Bernard (1985), „On the convex layers of a planar set”, IEEE Transactions on Information Theory, 31 (4): 509—517, MR 798557, doi:10.1109/TIT.1985.1057060 
  • Chazelle, Bernard (1993), „An optimal convex hull algorithm in any fixed dimension” (PDF), Discrete & Computational Geometry, 10 (1): 377—409, CiteSeerX 10.1.1.113.8709 Слободан приступ, doi:10.1007/BF02573985 
  • Chen, Qinyu; Wang, Guozhao (mart 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 972777 
  • Demaine, Erik D.; Gassend, Blaise; O'Rourke, Joseph; Toussaint, Godfried T. (2008), „All polygons flip finitely ... right?”, Surveys on Discrete and Computational Geometry, Contemporary Mathematics, 453, Providence, Rhode Island: American Mathematical Society, стр. 231—255, MR 2405683, doi:10.1090/conm/453/08801 
  • Dirnböck, Hans; Stachel, Hellmuth (1997), „The development of the oloid” (PDF), Journal for Geometry 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 
  • Gardner, L. Terrell (1984), „An elementary proof of the Russo-Dye theorem”, Proceedings of the American Mathematical Society, 90 (1): 171, MR 722439, doi:10.2307/2044692 
  • 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, стр. 193—213, ISBN 0-8176-3660-9, MR 1264417, doi:10.1007/978-0-8176-4771-1 
  • 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, MR 729228, doi:10.1016/0196-6774(83)90013-5 
  • Grünbaum, Branko (2003), Convex Polytopes, Graduate Texts in Mathematics (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, MR 20800, doi:10.1090/S0002-9904-1947-08787-5 

Spoljašnje veze

Konveksni skup на Викимедијиној остави.
  • Hazewinkel Michiel, ур. (2001). „Convex subset”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104. 
  • Lectures on Convex Sets, notes by Niels Lauritzen, at Aarhus University, March 2010.
Normativna kontrola: Državne Уреди на Википодацима
  • Francuska
  • BnF podaci
  • Nemačka
  • Izrael
  • Sjedinjene Države
  • Japan
  • Češka