Geometric Algorithms
asics
B
2
Convex hulls 3
Map overlay 4
Line segment intersection 4
Doubly-connected edge list 5
Overlaying the maps 8
Polygon triangulation 10
Polyhedron casting 13
Enclosing circles 15
Vertical decomposition 17
Range searching 20
KD-trees 20
Range trees 23
Voronoi diagram 25
Delaunay triangulations 27
Duality and arrangements 30
Windowing queries 33
,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
asics
B
2
Convex hulls 3
Map overlay 4
Line segment intersection 4
Doubly-connected edge list 5
Overlaying the maps 8
Polygon triangulation 10
Polyhedron casting 13
Enclosing circles 15
Vertical decomposition 17
Range searching 20
KD-trees 20
Range trees 23
Voronoi diagram 25
Delaunay triangulations 27
Duality and arrangements 30
Windowing queries 33
,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
