Transcript CG-tutorial-part2 - Stony Brook University

An Introduction to
Computational Geometry
Joseph S. B. Mitchell
Stony Brook University
Mini-Course Info



Joe Mitchell (Math 1-109)
[email protected] (631-632-8366)
http://www.ams.sunysb.edu/~jsbm/nasa/tutorial.html
Recommended Texts:
• Computational Geometry, by Mark de Berg, Marc van Kreveld,
Mark Overmars and Otfried Schwartzkopf (2nd edition)
• Computational Geometry in C, by Joe O’Rourke (2nd Edition)

Surveys/Reference books:
• CRC Handbook of Discrete and Computational Geometry,
editted by Goodman and O’Rourke (2nd edition)
• Handbook of Computational Geometry, editted by Sack and
Urrutia
Sessions and Topics

Session 1:
• Introduction
• Convex Hulls in 2D, 3D
• A variety of algorithms

Session 2:
• Searching for intersections: Plane sweep
• Halfspace intersections, low-dimensional
linear programming (LP)
• Range Search
3
Sessions and Topics

Session 3:
• Triangulation
• Proximity: Voronoi/Delaunay diagrams
• Point location search

Session 4:
• Arrangements
• Duality and applications
• Visibility graphs, shortest paths
4
Sessions and Topics

Session 5:
• Spatial partitioning, optimization, load
balancing
• Binary Space Partitions
• Clustering trajectories

Session 6:
• GeoSect: Overview and algorithms
• 3D partitioning
• Flow-respecting partitioning
5
Outline



Intersection search
Linear programming, halfspace
intersections
Range Search
6
Intersection Search

Input: A set S of geometric objects
(segments, polygons, disks, solid models, etc)
7
Intersection Search

Versions of the problem:
• DETECT: Answer yes/no: Are there any
intersections among the objects S?
(if “yes”, then we may insist on returning a witness)
• REPORT: Output all pairs of objects that intersect
• COMPUTE: Compute the common intersection of all
objects
• COUNT: How many pairs intersect?
• QUERY: Preprocess S to support fast queries of
the form “Does object Q intersect any member of
S?” (or “Report all intersections with Q”)
May also want to insert/delete in S, or
allow objects of S to move.
8
Intersection Search: Segments

Segment intersection: Given a set S of
n line segments in the plane, determine:
• Does some pair intersect? (DETECT)
• Compute all points of intersection
(REPORT)
Naïve: O(n2)
CG: O(n log n) DETECT,
O(k+n log n) REPORT
Element Uniqueness
Input: {x1, x2, …,xn }
Are they distinct?
(yes/no)
(n log n)
Lower Bound to DETECT: (n log n) , from ELEMENT UNIQUENESS
Primitive Computation

Does segment ab intersect segment cd ?
• Types of “intersect”
• Test using “Left” tests (sign of a cross
product (determinant), which determines
c
the orientation of 3 points)
Left( a, b, c ) = TRUE  ab  ac > 0
• Time O(1)
(“constant”)
a
b
c is left of ab
10
Bentley-Ottmann Sweep


Main idea: Process events in order of
discovery as a vertical line, L, “sweeps”
over the scene, from left to right
Two data structures:
L
• SLS: Sweep Line Status: bottom-to-top
ordering of the segments intersecting L
• EQ: Event Queue
11

Two data structures:
• SLS: Sweep Line Status: bottom-to-top
ordering of the segments intersecting L
• EQ: Event Queue

Initialize:
• SLS = 
• EQ = sorted list of segment endpoints

L
O(n log n)
How to store:
• SLS: balanced binary search tree
(dictionary, support O(log n) insert, delete, search)
• EQ: priority queue (e.g., heap)
12
Event Handling

Hit left endpt of e
O(log n)

a
e
b
L
Hit right endpt of e
L
a
e
O(log n)

Find segs a and b above/below e
in SLS. Insert e into SLS.
Test(a,e), Test(b,e) and insert
crossings (if any) in EQ
b
Find segs a and b above/below e
in SLS. Delete e from SLS.
Test(a,b), and insert crossing
(if any) in EQ
Hit crossing point e  f (only needed in REPORT)
O(log n)
e
a
Exchange e, f in SLS.
Test(a,f), Test(b,e) and insert
crossings (if any) in EQ
b
f
L
13
Algorithm Analysis

Invariants of algorithm:
• SLS is correctly ordered.
• Test(a,b) for intersection is done whenever segments a and b
become adjacent in the SLS order

Discovered crossings are inserted into EQ
(for REPORT; for DETECT, stop at first detected crossing)





Claim: All crossings are discovered
Time: O(n log n) to DETECT (O(n) events @ O(log n) )
Time: O((n+k) log n) to REPORT (O(n+k) events @ O(log n) )
Example Applet
k = # crossings = output size
Another nice applet
14

Optimal REPORT algorithms exist:
• O(k + n log n)

[Chazelle-Edelsbrunner, Balaban]
(Complex)
Special Case: REPORT for horiz/vert segs
• Bentley-Ottmann sweep: O(k + n log n)

Special case: Simplicity testing
• O(n), from Chazelle triangulation

Sweeping applies also to
• Unions
• Intersections
• Arrangements
15
Data Structures for Planar Subdivisions



Winged Edge Data
Structure.
Quad Edge Data
Structure.
Our focus on “Doubly
Connected Edge List”.
• Every edge e is struct:
– e.org, e.dest: pointer to origin
and dest vertices.
– e.face is face on left of edge
– e.twin is the same edge,
oriented the other direction.
– e.next is next edge along the
face
v2
v3
v1
f0 e
e4,0
v7
e’s f
1
twin
v0
e0,1
v6
v5
v4
[DCEL: doubly connected edge list]
- represent edge as 2 halves
- lists: vertex, face, edge/twin
-facilitates face traversal
Ack: R. Pless
DCEL
v2
• Every edge e is struct:
– e.org, e.dest: pointer to origin
and dest vertices.
– e.face is face on left of edge
– e.twin is the same edge,
oriented the other direction.
• Each Face has a pointer to
one edge of that face.
• Each vertex has pointer to
one edge away from that
vertex.
v3
v1
f0 e
e4,0
v7
e’s f
1
twin
v0
e0,1
v6
v5
v4
Pop quiz.
-How to enumerate
all edges of a face?
-How to enumerate
all edges incident on
a node?
Ack: R. Pless
Practical Methods, 3D

Uniform grid

Quadtrees
With each pixel, store a
list of objects
intersecting it.
Do brute force on
pixel-by-pixel basis.
See Samet books, SAND website

Bounding volume hierarchies
18
Bounding Volume Hierarchies
Input: Set S of objects.
S
Bounding volume
19
QuickCD: Collision Detection
The 2-Box Cover Problem
• Find “smallest” (tightest fitting) pair
of bounding boxes
• Motivation:
Best outer approximation
 Bounding volume hierarchies

Bounding Volume Hierarchy
BV-tree:
Level 0
k-dops
BV-tree: Level 1
6-dops
14-dops
18-dops
26-dops
BV-tree: Level 2
BV-tree: Level 5
BV-tree: Level 8
Large Convex Inner Approx

“Grow” k-dops from selected seed
points: collision detection (QuickCD),
response
Outline



Intersection search
Linear programming, halfspace
intersections
Range Search
28
Linear Programming
Maximize
Subject to:
c1x1 + c2x2 + ... + cdxd
a1,1x1 + ... a1,dxd  b1
a2,1x1 + ... a2,dxd  b2
:
:
:
an,1x1 + ... an,dxd  bn
Matrix form:
max cT x
s.t. Ax  b
Linear Program (LP) of dimension d:
c = (c1,c2,...,cd)
hi = {(x1,...,xd) ; ai,1x1 + ... + ai,dxd  bi}
li = hyperplane for halfspace hi
(straight lines, if d=2 )
H = {h1, ... , hn}
29
Linear Programming Background

Dantzig [40’s]: Simplex method
• Works well in practice, but not poly-time

Khachian et al. [79-]: Ellipsoid algorithm
• Weakly poly-time

Karmarkar et al.[84+]: Interior-point methods
• Weakly poly-time and practical extensions/variants

Megiddo; Dyer; Clarkson; Seidel [84-90] :
• Low-dimensional strongly poly-time O(n)

Here: Simple O(n) randomized [Seidel]
30
One Approach to 2D LP

Construct the feasible region:
•
•
•
•
Q = intersection of all n halfplanes, h1, h2, …, hn
convex polygon
Divide and conquer: T(n)  2T(n/2) + O(n)
merge
Merge: Intersect 2 convex polygons
4 sorted lists: upper/lower chain of each
Merge the 4 lists
O(n)
Sweep left to right, constructing intersection
Total Time to construct Q: O(n log n)
Best possible: (n log n), from SORTING
Key Idea: It is “easier” to find the lowest point of31Q
(solve LP) than to construct the feasible region Q
Randomized Incremental LP



Constraints added in random order
Assume we start with h1 , h2 feasible
Add hi Cases:
• (1) Constraint hi already satisfied: Do nothing
• (2) Constraint hi violated: Solve 1D LP, time O(i)
32
Randomized Incremental 2D LP

WLOG: All halfspaces are “upwards”, c = (0,-1)
c
33
c
1D LP
Constraint violation!
35
Analysis of Randomized Incremental LP



Constraints added in random order
Assume we start with h1 , h2 feasible
Add hi Cases:
• (1) Constraint hi already satisfied: Do nothing
• (2) Constraint hi violated: Solve 1D LP, time O(i)



P( case (2) )  2/i
(backwards analysis)
E( work to insert hi ) = (2/i )O(i ) = O(1)
Total expected work = O(n)
36
LP-Type Problems


Example: Minimum enclosing ball (MEB),
min-enclosing ellipsoid, etc.
O(n) in any fixed dimension
But, exponential
dependance on dimension
See [KMY03] talk
In high dimensions: use core-sets
to get (1+)-approximation using coreset of size O(1/), independent of
dimension
37
Outline



Intersection search
Linear programming, halfspace
intersections
Range Search
38
Range Search

Input: Set S of n points

Preprocess to support range search queries
•
•
•
•
axis-aligned boxes (orthogonal range search)
Halfspaces
Disks
Triangles, simplices, polyhedra
39
Kd-tree demo
Range Search






Grids
Quadtrees
Kd-trees
Partition trees
R-trees and variants; bounding volume hierarchies
Range trees: Orthogonal range search:
• Decompose x-coordinates into “canonical intervals”
• Associated with each node of 1D range tree is a y-search
structure
• Query is decomposed into O(log n) 1D queries, one per
canonical x-interval

Range tree Applet
40