High quality summary covering the entire Geometric Algorithms course. All of the concepts are clearly, yet compactly summarized, and explained in more detail where necessary. Based on the lectures, slides and the associated book.
,Basics
Definitions
- Plane= 2D space
- Point= set of coordinates (depending on 2D, 3D etc.)
- Line=y = m * x + c
- Half-plane= one side of the line;y <= m * x + c
- Line segment= two endpoints
- Two segments intersect if they have some point in common
- Proper intersection: common point is exactly one interiorpoint of each line
segment
- Polygon= connected region of a plane, bounded byline segments
- Edges = its line segments
- Vertices = endpoints of the edges
- Circle= only the boundary (edge)
- Disk= boundary + its interior
Relations
- Euclidean distance
- Manhattan distance(sum of the segments below)
- Intersection: set of points that two objects havein common
Description size
- A point, line (segment), circle, rectangle requiresO(1)storage
- A simple polygon withnvertices requiresO(n)storage
2
,Convex hulls
onvex Shape or set if for any two points that arepart of the shape, the connecting line
C
segment is also part of the shape
- Circleis notconvex, but adiskis
Convex hull Intersection of all convex sets thatcontains a subsetSof the plane (set of points,
rectangle, simple polygon); Smallest set that containsS
Convex hull problem: give algorithm that computesthe convex hull of any given set ofnpoints
- Input has 2ncoordinates and thusO(n)size
- Output has at least 4 and at most 2n coordinates, and thus betweenO(1)andO(n)size
- Useful insights (that you have toprove!):
- Vertices of the convex are always points from the input
- Supporting line of any convex hulledgehas all inputpoints to one side
- Based on this you can create aslowalgorithm thatgoes through all pairs
of points and adds it to result if all other points lie on one side of the line
through the pair
- Better algorithm: sort the points from left to right (byxcoordinate), then iterate
- Idea: first computeupper boundary, thenlower boundaryis symmetric
1. Add two leftmost points to result
2. Keep adding next point until entire list is processed:
a. If this is a left turn, remove previous points that shouldn’t be in the hull
because of this (can go as far back as the first two points!)
b. If this is a right turn, continue
. D
3 o similar in the other direction (to computebottomboundary)
4. Concatenate two lists
- Analysis:O(n log n)to sort and for each point afterthe first three, there can be
O(1 + k)steps to add it to the hull and remove previouspoints withk <= n, so
you end up withO(n log n) + O(n2) =O(n2)
- BUT, each point can be removed only once from the upper hull, so
actually, we have:
- Hence,O(n log n) + O(n)=O(n log n), which is optimal
Convex hulls in:
- 3D: vertices (0 dim.), edges (1 dim.) and facets (2 dim.), and 3 dim. interior
- 4D: vertices (0 dim.), edges (1 dim.) 2-facets (2 dim.) and 3-facets (3 dim.), and 4 dim.
interior
- Its boundary can haveΘ(n2)facets in worst case
3
, Map overlay
GISGeographic Information System
- Data is stored in separate layers
- Each layer stores geometric info about e.g. roads, land cover, boundaries, habitats
Map overlayCombination of two (or more) map layers
- Answer queries such as total length of roads through forests etc.
Line segment intersection
utput-sensitiveIf output is large, it is fine tospend a lot of time, but if the output is small, the
O
algorithm is fast
- Input-sensitiveapplies to the running time of anyalgorithm (depends onn)
Line intersection problem: givennline segments,find their intersection points
- Naive approach: loop over every pair of segments and report their intersections
- If every line intersects every other line, this is optimal, since there would ben2
intersections to report, and algorithm runs inO(n2)(and every algorithm needs at
least as much time as it takes to report all the answers)
- However, in the map overlay problem, you can expect that not every line
segment intersects alotof line segments from theother map layer
- Typically, can expectk = O(n)intersections, thenyou can find all
intersections inO(n log n) + ktime (andkfallsaway)
Overlapping pairs
- Given set of intervals on a line, find all partly overlapping pairs
- Sort endpoints and iterate left to right, maintaining currently intersected intervals in BST
- Whenever you come across a start endpoint, report all other segments in the
BST, and then insert the segment of this endpoint
- Running timeO(n log n + k), wherekcould be at leastn2/ 4so quadratic worst
- This isoutput-sensitivefor 1D, but not for 2D, becauseit’s possible for there to be a
bunch of vertical line segments that do not intersect, thus should be able to run inO(n
log n), whereas the 1D algorithm would run inO(nlog n + n2)
lane sweep technique Imaginary horizontal line passingover the plane from top to
P
bottom, solving the problem as it moves
- Events: places where the line stops and algorithmcomputes some positions
- Status: storage of relevant situations at currentposition of the sweep line
- At every point, everything above the sweep line is already done
- General guide:
1. Define status
2. Choose status structure and event queue
3. Figure out how events must be handled (use sketches!)
4. Analyze number of events and how much time each event takes
5. Deal with degenerate cases, incorporating them carefully
4
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Suniht. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $10.70. You're not tied to anything after your purchase.
