Efficient algorithms for discrete geometry problems

Autor: Savić Marko
Jazyk: angličtina
Rok vydání: 2018
Předmět:
Druh dokumentu: Diplomová práce
Popis: The first class of problem we study deals with geometric matchings. Given a setof points in the plane, we study perfect matchings of those points by straight linesegments 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 2 )-time algorithm for finding a bottleneck matching, improving upon previously best known algorithm of O(n 3 ) 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 convexposition. Combining that set of tools with a geometric analysis enable us to solve theproblem of finding a bottleneck matching in O(n 2 ) time. We also design an O(n)-timealgorithm 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.The second class of problems we study deals with dilation of geometric networks.Given a polygon representing a network, and a point p in the same plane, we aim toextend the network by inserting a line segment, called a feed-link, which connectsp to the boundary of the polygon. Once a feed link is fixed, the geometric dilationof some point q on the boundary is the ratio between the length of the shortest pathfrom p to q through the extended network, and their Euclidean distance. The utility ofa feed-link is inversely proportional to the maximal dilation over all boundary points.We give a linear time algorithm for computing the feed-link with the minimum overalldilation, thus improving upon the previously known algorithm of complexity that isroughly O(n log n).
Prva klasa problema koju proučavamo tičee se geometrijskih mečinga. Za dat skup tačaaka u ravni, posmatramo savršene mečinge tih tačaka spajajućii ih  dužima koje   se ne smeju sećui. Bottleneck mečing je takav mečing koji minimizuje dužinu najduže duži. Naš 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 2) za nalaženje bottleneck mečinga. Ovo  je bolje od prethodno najbolji poznatog algoritam, čiija je složenost O(n 3 ). Takođe proučavamo bihromatsku verziju ovog problema, u kojoj je svaka tačka  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šimo problem nalaženja bottleneck mečinga u O(n 2 ) vremenu. Takođe, konstruišemo algoritam vremenske složenosti O(n) za slučaj kada  sve date tačkke leže na krugu. Prethodno najbolji poznati algoritmi su imali složenosti  O(n 3 ) za tačkeke u konveksnom položaju i O(n log n) za tačke na krugu.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širiti mrežu  dodavanjem duži zvane feed-link koja povezuje p sa obodom poligona. Kada je feed- link fiksiran, definišemo geometrijsku dilaciju neke tačke q na obodu kao odnos izme  đu  dužine najkraćeg puta od p do q kroz proširenu mrežu i njihovog Euklidskog rastojanja. Korisnost feed-linka je obrnuto proporcionalna najvećoj dilaciji od svih ta čaka na obodu poligona. Konstruiš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).
Databáze: Networked Digital Library of Theses & Dissertations
Externí odkaz: