Return to search

Efficient algorithms for discrete geometry problems / Efikasni algoritmi za probleme iz diskretne geometrije

<p>The first class of problem we study deals with geometric matchings. Given a set<br />of points in the plane, we study perfect matchings of those points by straight line<br />segments so that the segments do not cross. Bottleneck matching is such a matching that minimizes the length of the longest segment. We are interested in finding a bottleneck matching of points in convex position. In the monochromatic case, where any two points are allowed to be matched, we give an O(n <sup>2 </sup>)-time algorithm for finding a bottleneck matching, improving upon previously best known algorithm of O(n <sup>3 </sup>) time complexity. We also study a bichromatic version of this problem, where each point is colored either red or blue, and only points of different color can be matched. We develop a range of tools, for dealing with bichromatic non-crossing matchings of points in convex<br />position. Combining that set of tools with a geometric analysis enable us to solve the<br />problem of finding a bottleneck matching in O(n <sup>2 </sup>) time. We also design an O(n)-time<br />algorithm for the case where the given points lie on a circle. Previously best known results were O(n 3 ) for points in convex position, and O(n log n) for points on a circle.<br />The second class of problems we study deals with dilation of geometric networks.<br />Given a polygon representing a network, and a point p in the same plane, we aim to<br />extend the network by inserting a line segment, called a feed-link, which connects<br />p to the boundary of the polygon. Once a feed link is fixed, the geometric dilation<br />of some point q on the boundary is the ratio between the length of the shortest path<br />from p to q through the extended network, and their Euclidean distance. The utility of<br />a feed-link is inversely proportional to the maximal dilation over all boundary points.<br />We give a linear time algorithm for computing the feed-link with the minimum overall<br />dilation, thus improving upon the previously known algorithm of complexity that is<br />roughly O(n log n).</p> / <p>Prva klasa problema koju proučavamo tičee se geometrijskih mečinga. Za dat skup tačaaka u ravni, posmatramo savr&scaron;ene mečinge tih tačaka spajajućii ih&nbsp; dužima koje &nbsp; se ne smeju sećui. Bottleneck mečing je takav mečing koji minimizuje dužinu najduže duži. Na&scaron; cilj je da nađemo bottleneck mečiing tačaka u konveksnom položaju.Za monohromatski slučaj, u kom je dozvoljeno upariti svaki par tačaka, dajemo algoritam vremenske složenosti O(n <sup>2</sup>) za nalaženje bottleneck mečinga. Ovo&nbsp; je bolje od prethodno najbolji poznatog algoritam, čiija je složenost O(n <sup>3 </sup>). Takođe proučavamo bihromatsku verziju ovog problema, u kojoj je svaka tačka&nbsp; obojena ili u crveno ili u plavo, i dozvoljeno je upariti samo tačke različite boje. Razvijamo niz alata za rad sa bihromatskim nepresecajućim mečinzima tačaka u konveksnom položaju. Kombinovanje ovih alata sa geometrijskom analizom omogućava nam da re&scaron;imo problem nalaženja bottleneck mečinga u O(n <sup>2</sup> ) vremenu. Takođe, konstrui&scaron;emo algoritam vremenske složenosti O(n) za slučaj kada&nbsp; sve date tačkke leže na krugu. Prethodno najbolji poznati algoritmi su imali složenosti&nbsp; O(n <sup>3</sup> ) za tačkeke u konveksnom položaju i O(n log n) za tačke na krugu.<br />Druga klasa problema koju proučaavamo tiče se dilacije u geometrijskim mrežama. Za datu mrežu predstavljenu poligonom, i tačku p u istoj ravni, želimo pro&scaron;iriti mrežu&nbsp; dodavanjem duži zvane feed-link koja povezuje p sa obodom poligona. Kada je feed- link fiksiran, defini&scaron;emo geometrijsku dilaciju neke tačke q na obodu kao odnos izme&nbsp; đu&nbsp; dužine najkraćeg puta od p do q kroz pro&scaron;irenu mrežu i njihovog Euklidskog rastojanja. Korisnost feed-linka je obrnuto proporcionalna najvećoj dilaciji od svih ta čaka na obodu poligona. Konstrui&scaron;emo algoritam linearne vremenske složenosti koji nalazi feed-link sa najmanom sveukupnom dilacijom. Ovim postižemo bolji rezultat od prethodno najboljeg poznatog algoritma složenosti približno O(n log n).</p>

Identiferoai:union.ndltd.org:uns.ac.rs/oai:CRISUNS:(BISIS)107293
Date25 October 2018
CreatorsSavić Marko
ContributorsStojaković Miloš, Mašulović Dragan, Vukobratović Dejan
PublisherUniverzitet u Novom Sadu, Prirodno-matematički fakultet u Novom Sadu, University of Novi Sad, Faculty of Sciences at Novi Sad
Source SetsUniversity of Novi Sad
LanguageEnglish
Detected LanguageEnglish
TypePhD thesis

Page generated in 0.0075 seconds