Název: Konvexní mnohoúhelníky v hustotně omezených bodových množinách
Překlad názvu: Convex polygons in density-restricted point sets
Autoři: Zálešák, Ondřej ; Valtr, Pavel (vedoucí práce) ; Balko, Martin (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2022
Jazyk: cze
Abstrakt: [cze] [eng]
Pro A, konečnou množinu bodů v Rd , nechť ∆(A) značí rozpětí A a je rovno poměru mezi maximální a minimální vzdáleností mezi dvěma body z A. Valtr (1992) dokázal, že pro množiny bodů v rovině a rozpětím rovným Θ(n 1 2 ) je veli- kost jejich největší podmnožiny v konvexní pozici Θ(n 1 3 ) v nejhorším případě. Ve stejném článku také uvádí rozšířený horní odhad na zaručenou velikost podmno- žiny v konvexní pozici pro množiny s asymptoticky vyšším rozpětím než n 1 2 , a stručnou konstrukci důkazu. Tato práce se věnuje konstrukci této detailně. Dále navazuje na nedávné výsledky pro množiny ve vyšších dimenzích, specificky pro- bírá, jestli by bylo možné rozšířit horní odhad v trojrozměrném prostoru pro vyšší rozpětí podobnou technikou, jako v rovinném případě. 1 Seznam použité literatury Valtr, P. (1992). Convex independent sets and 7-holes in restricted planar point sets. Discrete & Computational Geometry, 7(2), 135-152. 2 For A, a finite set of points in Rd , let ∆(A) denote the spread of A and be equal to the ratio of the maximum and the minimum distance of two points from A. Valtr (1992) proved that for sets of points in the plane with spread equal to Θ(n 1 2 ), the cardinality of the largest subset in convex position is Θ(n 1 3 ) in the worst case. The same article also contains an expanded upper bound on the guaranteed cardinality of subsets in convex position for sets with spread asymptotically higher than n 1 2 , and a brief construction for the proof. This thesis looks at this construction in detail. Furthermore it builds on the recent results for sets in higher dimensions, specifically discusses, whether it is possible to expand the upper bound in three-dimensional space for higher spreads with a similar technique as in the planar case. 1 Seznam použité literatury Valtr, P. (1992). Convex independent sets and 7-holes in restricted planar point sets. Discrete & Computational Geometry, 7(2), 135-152. 2
Klíčová slova: konvexní mnohoúhelník|rovina|množina bodů|vzdálenosti|odhady|geometrie; convex polygon|plane|point set|distances|bounds|geometry

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/176096

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-510323


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce