Original title: Konvexní mnohoúhelníky v hustotně omezených bodových množinách
Translated title: Convex polygons in density-restricted point sets
Authors: Zálešák, Ondřej ; Valtr, Pavel (advisor) ; Balko, Martin (referee)
Document type: Bachelor's theses
Year: 2022
Language: cze
Abstract: [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
Keywords: convex polygon|plane|point set|distances|bounds|geometry; konvexní mnohoúhelník|rovina|množina bodů|vzdálenosti|odhady|geometrie

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/176096

Permalink: http://www.nusl.cz/ntk/nusl-510323


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses