Computational Geometry: Algorithms and Methods in Geometric Problem Solving
Explore the realm of computational geometry encompassing line segment crossing, convex hulls, Voronoi diagrams, and element distinctness reduction. Delve into techniques like line crossing checks, enumeration of cross points, and the sweep method, which are crucial for solving geometric problems efficiently using memory and numerical values.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Computational Geometry Line Segment Crossing Enumeration Convex Hull Arrangement Voronoi Diagram
Computational Geometry Algorithms for solving geometric problems For human, the tools are ruler and compass, with writing the figures on a paper For computers, we can only use memory and values, that are not geometric, and we can not grasp the global view like looking the figures by eyes Everything has to be dealt as numbers, and that is the point
Line Crossing Check For example, consider the problem of checking whether two line segments cross or not For human, write a figure and enough For the computers, the line segments are given by coordinates of their end points We have to compute something to check, in algebraic ways Obtain the linear equation representing red line and blue line check in which side of the lines, the endpoints are When red endpoints are in the different sides of the blue line, and blue end points are also so, the lines cross
Line Segment Crossing Enumeration For given n line segments, enumerate all cross points by two of these line segments for human, draw a figure and that s enough the previous checking algorithm attains O(n2) time If many are crossing, O(n2) is acceptable How about if not so many crosses are there? Check the cross points from left to right, as human does
Reducing Element Distinctness Element distinctness problem is redusable to line segment crossing enumeration Element distinctness problem is known to need n log n time line segment crossing enumeration must take n log n time Element Distinctness Problem: Are there any two same numbers in the given numbers a1, , an? For each ai, prepare a vertical but bit tilt line segment passing the point (ai, 0) a cross point exists there are same numbers a5 a4a3 a2 a1
Sweep Method We consider a vertical line L at the most left endpoints of the segments, and move it to right, continuously (virtually); with updating the following sets S: set of segments crossing with L (sorted in the y-coordinates of cross points) R: set of segments not crossing with L and on the right to L H: heap of events sorted in x-coordinates that are (a) left ends of segments in R, (b) right ends of segments S, and (c) cross points by two segments neighboring in S (if it exists on the right of L)
Update the Data We extract the leftmost event from H, and move L to its x-coordinate Between an event and the next event, there is no change of the sets, and no cross point comes When the extract event is (c) cross point: output it, swap order in R of the crossing segments (b) right end: delete the segment from R (a) left end: insert the segment to R For each, if newly neighboring segments cross in right, insert to H An operation takes O (log n) time, thus O((n+K)logn) time in total #cross points
Convex Hull Jarvis s March Graham Scan Merge Hull Quick Hull
Convex Hull Problem Convex hull is the minimum convex area that include the given n points locating on the plane (no hollow) The convex hull of n points is always a convex polygon Convex hull problem is to compute the convex hull represented by the sequence of the vertices in the polygon that is corresponding to the convex hull
Difficulty We can sort n numbers by solving convex hull n log n time is a lower bound + sort a1, ,an + compute convex hull of (a1, a12), (a2, a22), , (an, an2) + all they are vertices of the convex hull, and is sorted in the increasing order
Jarviss March Compute the convex hull like wrapping an item 1. find the point v with the smallest x-coordinate; choose the smallest y-coordinate if there are several 2. find v' that is the first vertex from v in the clockwise order 3. make an edge between v and v if v is not the first vertex, set v v , and go to 2 An operation takes O(n) time, thus O(K n) time in total #edges of the convex hull
Graham Scan Graham Scan is an improved version of Jarvis s march so that finding the next vertex is efficient 1. find a point o that is inside the convex hull 2. sort all the points in clockwise order from o 3. scan all points in the order, and make an edge between new point and just before; if the angle of the edge and the previous is below 180, delete the point from the hull O(nlog n) time for sorting a point takes O(1) time to insert/delete o
Relation to Sorting Convex hull has an essence of sorting, as sorting is reducible to convex hull So, frameworks of several sorting algorithms can be applied Jarvis s march is insertion sort Graham scan is heap sort (heap sort by clockwise) Merge sort and quick sort can also be applied + merge sort merge hull + quick sort quick hull, divide-and-conquer
Divide and Conquer Partition the point set P by a vertical line, and compute the convex hull of each side Compute the convex hull of all by merging the two 1. sort P in increasing order of x coordinates 2. partition P into P0and P1of almost equal sizes by a vertical line 3. compute the convex hull of each P0and P1by recursive calls 4. compute two tangents of convex hulls to make the convex hull of the all Note that there are just two tangent lines
Time Complexity 1. sorting P O(nlog n) 2. partition P into P0and P1 O(1) 3. compute the tangent lines of the convex hulls of P1and P0 + as Jarvis s march, it can be done in O(n) time + re-connecting points and lists is done in O(1) time An iteration takes O(n), thus O(nlog n) time in total In summary, both the body and the preprocess (sorting) are O(nlog n) time
Merge Hull Same as divide and conquer, but it does not sort the points, so the points are arbitrary partitioned into two 2. partition P into P0and P1of almost equal sizes 3. compute the convex hull of each P0and P1by recursive calls 4. compute tangents of two convex hulls to make that of all Instead of reducing sorting, we need to find many tangent lines
Finding Tangent Lines A sophisticated way enables us to find tangent line in O(log n) time, but in the worst case there are n tangent lines O(nlog n) time is required, roughly It can be linear time by another way 1. find a point o included in convex hulls of both P0 and P1 2. if there is no such point, the convex hulls are disjoint, thus tangent lines are only two, thus find them 3. compute the tangent lines by tracing convex hulls of P0and P1 in clockwise order from o, (like Graham scan) A point is scanned at most twice, thus O(n) time O(n log n) in linear time o
Quick Hull Concepts of quick hull and quick sort are similar; roughly partition so that the merging process become simple, for practical efficiency 1. partition P by a line connecting leftmost point l and right most r 2. find the furthest point v from the line in each area if there is no such point, the line is an edge of the convex hull 3. connect the l and v, and r and v, and recursive call for each line to compute the edges of the hull in the area Points inside the convex hull drastically deleted, thus very fast in practice O(n2) time in the worst case
In Higher Dimensions How are these algorithms in three or more dimensions? First, tangent lines will be tangent hyperplanes they are not two; even two convex hulls are disjoint There is no clockwise order used by Graham scan and etc. Incremental algorithms exist; add a vertex one by one to the current convex hull, and compute all tangent hyperplanes In three dimension, the tangent hyperplanes are connected like a path, so the divide and conquer works
Voronoi Diagram Incremental Algorithm Divide and Conquer
Voronoi Diagram Voronoi diagram is a partition of the all points in the plane into regions by their nearest point in the given point set + each edge is a part of perpendicular bisector of some points + any perpendicular bisector appears one place + all regions are convex polygons + each region includes exactly one point + each edge of a region is a perpendicular bisector of the point and that of another Useful to check which point is closest from here
Making Voronoi Diagram Easy if points are two just give their perpendicular bisector It will not be a line if we add one more point diagram is composed of three perpendicular bisectors Their cross point is equal distance to the three points How about four and more points?
Point Addition Generally, there appears one new region when we add a point Changes happen only between the region of new point and the remaining regions sufficient to know the shape of only new region Let v be the new point, and u be the point of the region that v is in a new region including v appears an edge of the region is of perpendicular bisectors of u and v This bisector goes to the cross with edges of other regions triangle point is a cross of bisectors
Crossing Bisectors Extend bisectors of v and u until it meets another bisector The opposite region is of another point w, thus this bisector can not exist as an edge of the region the bisector ends at the cross Edge of v s region locating in the region is the bisector of v and w it continues until meeting another bisector it ends there, and new bisector with another point begins Finally, it comes back to the first bisector, and we get the region
Complexity Analysis Algorithm operates the following repeatedly + compute the perpendicular bisector of new point v and the point u of the current looking region + find the cross point of the bisector and the edges of the region Perpendicular bisector is calculated in O(1) time Finding cross point can be done by binary search on the polygon edges of the region, in O(log n) time #edge of a region can be n-1, thus O(nlog n) time for one addition O(n2log n) time in total
Divide and Conquer In practice, each region of Voronoi diagram does not contain many edges, but actually constant number practical computation time is O(nlog n) Divide and conquer attains O(nlog n) even for the worst case + partition the points into almost equal sizes by a vertical line + find the Voronoi diagram of each group recursively
Divide and Conquer In practice, each region of Voronoi diagram does not contain many edges, but actually constant number practical computation time is O(nlog n) Divide and conquer attains O(nlog n) even for the worst case + partition the points into almost equal sizes by a vertical line + find the Voronoi diagram of each group recursively
Divide and Conquer Merge the two Voronoi diagrams to obtain that for all Find the lowest points of both diagrams; their perpendicular bisector is an edge in very low area Find the point crossing with an edge of another region replace one of the point to the point of new region, and repeat this with finding perpendicular bisectors again
Complexity Analysis Solve two subproblems of size n/2 to solve a problem of size n Merge process takes O(n) time by checking the cross points with all edges of a region, and accumulated time for this is O(n) This simple method works since any Voronoi diagram of n points has O(n) edges The recursion T(n) = cn + 2T(n/2) implies that the time complexity is O(nlog n)
In Higher Dimensions How about three or higher dimensions? A region in a Voronoi diagram is a convex polytope There is no concept of clockwise order A bisector is a hyperplane, and it intersects to many facets of a region polytope Updating Voronoi diagram by adding a points becomes a problem of finding all facets of a polytope corresponding to the new region induced by the new point
Conclusion Line segment crossing enumeration + sweep vertical line from left to right, and update the order of crossing segments Convex hull + algorithm designs for sorting work for convex hull + divide and conquer works +Jarvis s march, Graham scan, marge hull, quick hull Voronoi Diagram + incremental algorithm + divide and conquer
