Transcript 503_lecture8 - Computer Science

UMass Lowell Computer Science 91.503
Graduate Algorithms
Prof. Karen Daniels
Spring, 2005
Computational Geometry
Overview from Cormen, et al.
Chapter 33
Overview

Computational Geometry Introduction

Line Segment Intersection

Convex Hull Algorithms

Nearest Neighbors/Closest Points
Introduction
What is
Computational Geometry?
Computational Geometry
Computer
Graphics
Visualization
Design
Analyze
CAD
Apply
Telecommunications
Manufacturing
Sample Application Areas
Data Mining &
Visualization
Bioinformatics
Robotics
Geographic
Information Systems
Medical
Imaging
Computer Graphics
Telecommunications
Astrophysics
Typical Problems

bin packing

Voronoi diagram

simplifying
polygons

shape similarity

convex hull

maintaining line
arrangements

polygon
partitioning

nearest neighbor
search

kd-trees
SOURCE: Steve Skiena’s Algorithm Design Manual
(for problem descriptions, see graphics gallery at http://www.cs.sunysb.edu/~algorith)
Common Computational
Geometry Structures
Convex Hull
Voronoi Diagram
New Point
Delaunay Triangulation
source: O’Rourke, Computational Geometry in C
Sample Tools of the Trade
Algorithm Design Patterns/Techniques:
binary search
divide-and-conquer
randomization
sweep-line
derandomization parallelism
duality
Algorithm Analysis Techniques:
asymptotic analysis, amortized analysis
Data Structures:
winged-edge, quad-edge, range tree, kd-tree
Theoretical Computer Science principles:
NP-completeness, hardness
MATH
Sets
Summations
Probability
Growth of Functions
Combinatorics
Proofs
Geometry
Linear Algebra
Recurrences
Graph Theory
Computational Geometry
in Context
Geometry
Design
Applied
Math
Analyze
Computational
Geometry
Efficient
Geometric Algorithms
Apply
Applied Computer Science
Theoretical
Computer
Science
Sample of Supporting Algorithmic &
Math Areas & Techniques


Computational
Geometry














Convex hulls
Visibility polygons
Arrangements
Mathematical
Programming
Linear programming
Integer programming
Lagrangian relaxation
Upper, lower bounding
Dynamic Data
Structures
Algorithm Design Patterns


Algorithm Analysis
Techniques
Complexity Theory


search space subdivision
binary search
divide-and-conquer
sweep-line
discrete-event simulation
NP-completeness, hardness
Discrete Math




Minkowski sum
Monotone matrices
Lattices
Set operations: union,
intersection, difference
Line Segment Intersections
(2D)
Intersection of 2 Line Segments
Intersection of > 2Line Segments
Cross-Product-Based
Geometric Primitives
Some fundamental geometric questions:
source: 91.503 textbook Cormen et al.
p3
p2
p3
(1)
p4
p2
p1
p0
p2
p1
p1
(2)
(3)
Cross-Product-Based
Geometric Primitives: (1)
p2
33.1
p1
p0
 x1
p1  p2  det
 y1
x2 
  x1 y2  x2 y1
y2 
Advantage: less sensitive to accumulated round-off error
(1)
source: 91.503 textbook Cormen et al.
Cross-Product-Based
Geometric Primitives: (2)
p2
p1
33.2
p0
(2)
source: 91.503 textbook Cormen et al.
Intersection of 2 Line Segments
Step 1:
Bounding Box
Test
p3
p3 and p4 on opposite sides of p1p2
p2
p4
p1
(3)
Step 2: Does each
segment straddle
the line containing
the other?
33.3
source: 91.503 textbook Cormen et al.
Segment-Segment Intersection


Finding the actual intersection point
Approach: parametric vs. slope/intercept
 parametric generalizes to more complex intersections


Lcd
e.g. segment/triangle
Parameterize each segment
Lcd
c
C=d-c
Lab
c
b
a
Lab
b
q(t)=c+tC
A=b-a
d
d
a
p(s)=a+sA
Intersection: values of s, t such that p(s) =q(t) : a+sA=c+tC
2 equations in unknowns s, t : 1 for x, 1 for y
source: O’Rourke, Computational Geometry in C
Demo
Segment/Segment Intersection
http://cs.smith.edu/~orourke/books/CompGeom/CompGeom.html
Intersection of >2 Line Segments
Sweep-Line Algorithmic Paradigm:
33.4
source: 91.503 textbook Cormen et al.
Intersection of >2 Line Segments
Sweep-Line Algorithmic Paradigm:
source: 91.503 textbook Cormen et al.
Intersection of >2 Line Segments
Time to detect if any 2
segments intersect:O(n lg n)
Balanced BST stores segments in order
of intersection with sweep line.
Associated operations take O(lgn) time.
Note that it exits as soon as one intersection is detected.
33.5
source:
91.503
textbook
Cormenet
et al.
al.
source:
91.503
textbook
Cormen
Intersection of Segments


Goal: “Output-size sensitive” line segment intersection algorithm
that actually computes all intersection points
Bentley-Ottmann plane sweep: O((n+k)log(n+k))= O((n+k)logn) time


k = number of intersection points in output
Intuition: sweep horizontal line downwards




just before intersection, 2 segments are adjacent in sweep-line intersection structure
check for intersection only adjacent segments
insert intersection event into sweep-line structure
event types:



top endpoint of a segment
bottom endpoint of a segment
intersection between 2 segments
 swap order
Improved to O(nlogn+k) [Chazelle/Edelsbrunner]
source: O’Rourke, Computational Geometry in C
Convex Hull Algorithms
Definitions
Gift Wrapping
Graham Scan
QuickHull
Incremental
Divide-and-Conquer
Lower Bound in W(nlgn)
Convexity & Convex Hulls
source: O’Rourke, Computational Geometry in C

A convex combination of points
x1, ..., xk is a sum of the form
a1x1+...+ akxk where
a i  0 i and a1    a k  1

Convex hull of a set of points is the
set of all convex combinations of
points in the set.
source: 91.503 textbook Cormen et al.
nonconvex polygon
convex hull of a point set
Naive Algorithms
for Extreme Points
Algorithm: INTERIOR POINTS
for each i do
for each j = i do
for each k = j = i do
for each L = k = j = i do
if pL in triangle(pi, pj, pk)
then pL is nonextreme
O(n4)
Algorithm: EXTREME EDGES
for each i do
for each j = i do
for each k = j = i do
if pk is not left or on (pi, pj)
then (pi , pj) is not extreme
O(n3)
source: O’Rourke, Computational Geometry in C
Algorithms: 2D Gift Wrapping

Use one extreme edge as an
anchor for finding the next
q
Algorithm: GIFT WRAPPING
i0
index of the lowest point
i
i0
repeat
for each j = i
Compute counterclockwise angle q from previous hull edge
k
index of point with smallest q
Output (pi , pk) as a hull edge
i
k
until i = i0
O(n2)
source: O’Rourke, Computational Geometry in C
Gift Wrapping
source: 91.503 textbook Cormen et al.
33.9
Output Sensitivity: O(n2) run-time is actually O(nh)
where h is the number of vertices of the convex hull.
Algorithms: 3D Gift Wrapping
O(n2) time
[output sensitive: O(nF) for F faces on hull]
CxHull Animations: http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html
Algorithms: 2D QuickHull


Concentrate on points close to
hull boundary
Named for similarity to
Quicksort
a
b
A
c
finds one of upper or lower hull
Algorithm: QUICK HULL
function QuickHull(a,b,S)
if S = 0 return()
else
c
index of point with max distance from ab
A
points strictly right of (a,c)
B
points strictly right of (c,b)
return QuickHull(a,c,A) + (c) + QuickHull(c,b,B)
O(n2)
source: O’Rourke, Computational Geometry in C
Algorithms: 3D QuickHull
CxHull Animations: http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html
Algorithms: >= 2D
Convex Hull
boundary is
intersection of
hyperplanes, so
worst-case
combinatorial size
(not necessarily running
time)
in:
Qhull: http://www.geom.umn.edu/software/qhull/
complexity is
(n
d / 2 
)
Graham’s Algorithm
source: O’Rourke, Computational Geometry in C


Points sorted angularly provide
“star-shaped” starting point
Prevent “dents” as you go via
convexity testing
q
p0
Algorithm: GRAHAM SCAN, Version B
Find rightmost lowest point; label it p0.
Sort all other points angularly about p0.
In case of tie, delete point(s) closer to p0.
Stack S
(p1, p0) = (pt, pt-1); t indexes top
i
2
while i < n do
if pi is strictly left of pt-1pt
then Push(pi, S) and set i
i +1
else Pop(S) “multipop”
O(nlgn)
Graham Scan
source: 91.503 textbook Cormen et al.
Graham Scan
33.7
source: 91.503 textbook Cormen et al.
Graham Scan
33.7
source: 91.503 textbook Cormen et al.
Graham Scan
source: 91.503 textbook Cormen et al.
Graham Scan
source: 91.503 textbook Cormen et al.
Algorithms: 2D Incremental
source: O’Rourke, Computational Geometry in C

Add points, one at a time


update hull for each new point
Key step becomes adding a
single point to an existing hull.

Find 2 tangents


Results of 2 consecutive LEFT tests
differ
Idea can be extended to 3D.
Algorithm: INCREMENTAL ALGORITHM
Let H2
ConvexHull{p0 , p1 , p2 }
for k
3 to n - 1 do
Hk
ConvexHull{ Hk-1 U pk }
O(n2)
can be improved to O(nlgn)
Algorithms: 3D Incremental
O(n2) time
CxHull Animations: http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html
Algorithms:
2D Divide-and-Conquer
source: O’Rourke, Computational Geometry in C

Divide-and-Conquer in a geometric
setting

O(n) merge step is the challenge



Find upper and lower tangents
Lower tangent: find rightmost pt of A &
leftmost pt of B; then “walk it downwards”
B
A
Idea can be extended to 3D.
Algorithm: DIVIDE-and-CONQUER
Sort points by x coordinate
Divide points into 2 sets A and B:
A contains left n/2 points
B contains right n/2 points
Compute ConvexHull(A) and ConvexHull(B) recursively
Merge ConvexHull(A) and ConvexHull(B)
O(nlgn)
Algorithms:
3D Divide and Conquer
O(n log n) time !
CxHull Animations: http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html
Lower Bound of O(nlgn)
source: O’Rourke, Computational Geometry in C


Worst-case time to find convex hull of n
points in algebraic decision tree model is in
W(nlgn)
Proof uses sorting reduction:



Given unsorted list of n numbers: (x1,x2 ,…, xn)
Form unsorted set of points: (xi, xi2) for each xi
Convex hull of points produces sorted list!



Parabola: every point is on convex hull
Reduction is O(n) (which is in o(nlgn))
Finding convex hull of n points is therefore at
least as hard as sorting n points, so worst-case
time is in W(nlgn)
Parabola for sorting 2,1,3
Nearest Neighbor/
Closest Pair of Points
Closest Pair
Goal: Given n (2D) points in a set Q, find the closest pair
under the Euclidean metric in O(n lgn) time.
Divide-and-Conquer Strategy:
-X = points sorted by increasing x
-Y = points sorted by increasing y
-Divide: partition with vertical line L into PL, PR
-Conquer: recursively find closest pair in PL, PR
dL, dR are closest-pair distances
d  min( dL, dR )
-Combine: closest-pair is either d or pair straddles partition line L
Check for pair straddling partition line L
both points must be within d of L
create array Y’ = Y with only points in 2d strip
for each point p in Y’
find (<= 7) points in Y’ within d of p
source: 91.503 textbook Cormen et al.
Closest Pair
Correctness
33.11
source: 91.503 textbook Cormen et al.
Closest Pair
Running Time: T (n)  2T (n / 2)  O(n)


O(1)
if n  3
  O(n lg n)
if n  3
Key Point: Presort points, then at each step form
sorted subset of sorted array in linear time
Like opposite of MERGE step in MERGESORT…
L
R
source: 91.503 textbook Cormen et al.
Additional Computational Geometry
Resources
 Computational
Geometry in C
 second
edition
 by Joseph O’Rourke
 Cambridge University Press
 1998
Web Site: http://cs.smith.edu/~orourke/books/compgeom.html
See also 91.504 Course Web Site:
http://www.cs.uml.edu/~kdaniels/courses/ALG_504.html