Transcript CG_Lecture7 - Computer Science

UMass Lowell Computer Science 91.504
Advanced Algorithms
Computational Geometry
Prof. Karen Daniels
Spring, 2001
Lecture 7
Geometric Modeling
Approximate Nearest Neighbor Searching
Monday, 4/23/01
Part 2
Advanced Topics
Applications
Manufacturing
Modeling/Graphics
Wireless Networks
Visualization
Techniques
(de)Randomization
Approximation
Robustness
Representations
Epsilon-net
Decomposition tree
Literature for Part II
Aspect
Title
Milenkovic/Daniels Wu/Li
Translational
On
Polygon
calculating
Containment
connected
and Minimal
dominating
Enclosure
set for
using
efficient
Mathematical
routing in ad
Programming
hoc wireless
networks
Source
Journal: ITOR
Application
Areas
manufacturing
Input
Objects
2D nonconvex
polygons
Conf:
Workshop on
Discrete Alg
and Methods
for MOBILE
Computing
&
Communicati
ons
dynamic
wireless
communicati
ons
2D points
representing
hosts
Arya et al.
An optimal algorithm
for approximate nearest
neighbor searching in
fixed dimensions
Journal: ACM
knowledge discovery;
data mining; pattern
recognition;
classification; machine
learning; data
compression;
multimedia databases;
document retrieval;
statistics
d-dimensional points
Goodrich/Ramos
BoundedIndependence
Derandomization
of Geometric
Partitioning with
Applications to
Parallel FixedDimensional
Linear
Programming
Journal: Discrete
& Comp Geom
Shewchuck
Triangle: Engineering a 2D
Quality Mesh Generator and
Delaunay Triangulator
Conf: 1st Workshop on Applied
CG
linear
programming
geometric modeling; graphics
range space
PSLG of object
Literature for Part II
Aspect
Dimensional
ity
Problem/
Task
Theory?
Implementat
ion?
ADTs &
Data
Structures
Algorithmic
Paradigms
&
Techniques
Math Topics
Milenkovic/Daniels Wu/Li
2D
2D
Arya et al.
arbitrary
Goodrich/Ramos
arbitrary
Shewchuck
2D
translational
containment;
overlap
elimination;
distance-based
subdivision;
minimal
enclosure;
visibility
both
dominating
set
partitioning; nearestneighbor query
geometric
randomization;
geometric
derandomization
(constrained) Delaunay
triangulation; robustness
some
experiments
both
theory
implementation
convex hull;
visibility
polygon
undirected
graph
balanced boxdecomposition tree
epsilon-net;
epsilonapproximation
subdivision;
approximate
algorithm;
binary search
Minkowski
sum; linear
programming;
monotonicity;
convex
distance
function
distributed;
heuristic
geometric
preprocessing;
approximation
algorithm
Minkowski metric;
probability
randomization;
derandomization;
parallel
triangular mesh; (constrained)
Delaunay triangulation;
Voronoi diagram; convex hulls;
Guibas/Stolfi quad-edge;
triangular data structure; PSLG;
splay tree; heap
sweep-line; geometric divideand-conquer; incremental
insertion
graph theory:
dominating
set
VC-dimension;
linear
programming;
probability
duality
Geometric Modeling
“Triangle: Engineering a 2D Quality
Mesh Generator and Delaunay
Triangulator”
Jonathan Richard Shewchuck
http://www.cs.cmu.edu/~jrs/jrspapers.html
Goals

Construct 2D mesh of
triangles for geometric
modeling that:
 avoids

 is

 is

small angles
constrained Delaunay triangulation
efficient in time and space
careful choice of data structures &
algorithm
robust
adaptive exact arithmetic
C code at http://www.cs.cmu.edu/~quake/triangle.html
Approach: Overview
Based on Ruppert’s
Delaunay Refinement
Algorithm
 Input: Planar Straight
Line Graph (PSLG)

 collection
of vertices
and segments

Step 1: Construct
Delaunay triangulation
of point set
Approach: Overview (continued)

Step 2:
 Start
with the
Delaunay
triangulation of the
point set
 Add input segments
segments become
constraints
 constrained Delaunay
triangulation

some differences
Approach: Overview (continued)

Step 3:
 Remove
triangles from
concavities


“triangle-eating virus”
Step 4:
 Refine
mesh to satisfy
additional constraints
on triangle’s minimum
angle size
 area

Step 1: Construct Delaunay
Triangulation of Point Set

Delaunay Triangulation Algorithms:
 O(nlogn)
expected time:
deBerg handout
Randomized incremental insertion
 Edge flipping restores empty circle property

 O(nlogn)

Fortune’s plane sweep (parabolic front)
 O(nlogn)

[point location bottleneck]
worst-case time:
Compute Voronoi diagram, then dualize

slowest
worst-case time:
Shewchuck
experimental
comparison
[speed, correctness]
Divide-and-Conquer

alternating cuts
fastest
Delaunay Triangulation Algorithms:
Divide-and-Conquer
O(nlogn) worst-case time
 Recursively halve input
vertex set
 Stop when size = 2 or 3
 Triangulate small set

 forms

edge(s) or triangle
Merge 2 triangulations
 Ghost
triangles allow fast
convex hull traversal
 Fit together like gear teeth
Step 2: Constrained Delaunay
Triangulation
Force mesh to conform to input line segments
 User Chooses Approach:

 Recursive
segment subdivision
Insert segment midpoint
 Flip edges to restore Delaunay (empty circle) property

 Constrained
Delaunay triangulation (default)
Insert entire segment
 Delete triangles it overlaps
 Retriangulate regions on each side of segment
 No new vertices are inserted

Step 4: Mesh Refinement

Refine mesh to satisfy additional constraints on
minimum triangle
angle size
 area

Insert new vertices
 Flip edges to restore Delaunay (empty circle)
property
 Halting Issue:

for angle constraint <= 27o
 May not halt for angle constraint >= 33.9o
 Halts
Step 4: Mesh Refinement (continued)

Vertex Insertion Rules:
 Segment’s
Diametral
Circle
smallest circle containing
segment
 any point in the circle
encroaches on segment
 split encroached segment


insert vertex at midpoint
 Triangle’s
Circumcircle
circle through all 3 vertices
 bad triangle:




angle too small
area too large
split bad triangle

insert vertex at circumcenter
Step 4: Mesh Refinement (continued)
Implementation Issues:
Representation
edge-based
+ Topologically richer
+ Elegant
- Slower
- More memory
Shewchuck
preference
triangle-based
- Topologically less
rich
- Longer code
+ Faster
+ Less memory
representation tradeoffs

Ghost triangles:


connected in ring about a
“vertex at infinity”
facilitate convex hull traversal
Implementation Issues:
Robustness

Tests
incorrectness can be serious
 Can
influence program flow of control
 Can classify entities (e.g. sweep-line events)
 Depend on correctness of geometric
predicates
Orientation (left/right/on)
 In-Circle (in/out/on)
 Each computes sign of a determinant


Constructions
some incorrectness can sometimes be
tolerated
 Represent geometric objects
 Often
determine output
Implementation Issues:
Robustness (continued)

Ideal Goal: real arithmetic
for some operations
 Challenge: compounded
roundoff error in floatingpoint arithmetic calculations:
 Tests: can cause program



to hang
to crash
to produce incorrect output
 wrong topology
 Constructions:

can cause approximate
results
What causes
incorrectness?
Implementation Issues:
Robustness (continued)

Arithmetic Alternatives to Floating-Point:
 Integer
or rational exact arithmetic
fixed precision
 extended precision

 Floating
point +
e-testing
 robust topological decisions
 filter:




exact
hybrid
slow but sure
floating-pt
fast but loose
time vs. error tradeoff
identify adequate precision for an operation (bit complexity)
 if expressible as multivariate polynomial, degree gives clue
floating-point comparisons except when correctness is threatened
adaptive precision:


compute quantity (e.g. sign of determinant) via successively more
accurate approximations
stop when uncertainty in result is small
No single solution fits all needs. Collection of techniques is needed.
Implementation Issues:
Robustness (continued)

Shewchuck uses:
 multi-stage
adaptive precision for geometric primitives
Orientation (left/right/on)
 In-Circle (in/out/on)
 Each





 fast

computes sign of a determinant
takes floating-pt inputs
stops when uncertainty in result is small
can reuse previous, less accurate approximations
arbitrary precision arithmetic
for small (yet extended) precision values
For general discussion of robustness issues and alternatives, see
Strategic Directions in Computational Geometry Working Group Report
Approximate Nearest
Neighbor Searching
“An Optimal Algorithm for
Approximate Nearest Neighbor
Searching in Fixed Dimensions”
Arya, Mount, Netanyahu,
Silverman, Wu
Goals

Fast nearest neighbor query in ddimensional set of n points:
 approximate

nearest neighbor
distance within factor of (1+e) of true closest
neighbor
 preprocess
using O(dnlogn) time, O(dn) space
Balanced-Box Decomposition (BDD) tree
 note that space, time are indepenent of e

 query
in O(cd,e logn) time
C++ code for simplified version is at http://www.cs.umd.edu/~mount/ANN
Approach: Distance Assumptions

Use Lp (also called Minkowski) metric


assume it can be computed in O(d) time
pth root need not be computed when comparing
distances
 d
p
d p (q1 , q2 )    x j (q1 )  x j (q2 ) 
 j 1


Approximate nearest neighbor


1
p
distance within factor of (1+e) of true closest
neighbor p* dist ( p, q)  (1  e )dist ( p*, q)
Can change e or metric without rebuilding
data structure
Approach: Overview

Preprocess points:
 Balanced-Box

Decomposition (BDD) tree
Query algorithm: for query point q
 Locate leaf cell
 Priority search:
containing q in O(log n) time
Enumerate leaf cells in increasing
distance order from q




For each leaf cell, calculate distance from q to cell’s point
Keep track of closest point p seen so far
Stop when distance from q to leaf > dist(q,p)/(1+e)
Return p as approximate nearest neighbor to q.
Balanced Box Decomposition
x x
x
(BBD) Tree
y
3
2
4
3
y2

Similar to kd-tree [Samet handout]
 Binary tree
 Tree structure
y1
stored in main
x1
memory
 Cutting planes are orthogonal to
axes

Alternating dimensions
 O(log n) height
 Subdivides space
into regions of
O(d) complexity using d7
dimensional rectangles

Can be built in O(dn log n) time
<
y1
>=
x1
x1
y2
y2
2
5
x2
8
x3
1
y3
One possible
kd-like tree
for the above
points
(not a BDD
tree, though)
x4
4
9
3
6
Balanced Box Decomposition
(BBD) Tree (continued)

Distinguishing features of BBD tree:

Cell is either



d-dimensional rectangle or
difference of 2 d-dimensional nested rectangles
In this sense, BDD tree is like:

Optimized kd-tree: partition points into roughly =
sized sets



tree
split
While descending in tree, number of points on path
decreases exponentially
Specialized Quadtree: aspect ratio of box is
bounded by a constant


subdivisio
While descending in tree, size of region on path
decreases exponentially
Leaf may be associated with more than 1
point in/on cell: O(n) node
Inner boxes are “sticky”: if it is close to edge,
it “sticks”
shrink
Splitting a Box: Midpoint
Splitting a Box: Middle-Interval
Packing Constraint
Priority Search from Query Point
Incremental Distance
[Arya, Mount93]



Incrementally update distance from parent box to
each child when split is performed
Maintain sum of appropriate powers of coordinate
differences between query point and nearest point
of outer box
Split:



Closer child has same distance as parent
Further child’s distance needs only 1-coordinate update
(along splitting dimension)
Makes a difference in higher dimensions!
Experiments
Experiments generated points from a variety of probability
distributions:
Uniform
Gaussian
Correlated Laplacian
Laplace
Clustered Gaussian
Correlated Gaussian
Clustered Segments
Experiments
Experiments
Experiments
Conclusions

Algorithm is not necessarily practical for large
dimensions


Shrinking helps with highly clustered datasets, but
was not often needed in their experiments


But, for dimensions <= ~20, does well
Only needed for 5-20% of tree nodes
BBD tree (in paper’s form) is primarily for static
point set

But, auxiliary data structure could maintain changes
Project Update
Project
Deliverable Due Date
Proposal
Interim Report
Final Presentation
Final Submission
Grade %
Monday, 4/9
Monday, 4/23
Monday, 5/7
Monday, 5/14
25% of course grade
2%
5%
8%
10%
Guidelines: Final Submission


Abstract: Concise overview (at most 1 page)
Introduction:





Motivation: Why did you choose this project?
Related Work: Context with respect to CG literature
Summary of Results
Main Body of Paper: (one or more sections)
Conclusion:
Summary: What did you accomplish?
 Future Work: What would you do if you had more time?
 References: Bibliography (papers, books that you used)

Well- written final submissions with research content may be
eligible for publishing as UMass Lowell CS technical reports.
Guidelines: Final Submission

Main Body of Paper:
 If
your project involves Theory/ Algorithm:
Informal algorithm description (& example)
 Pseudocode
 Analysis:


Correctness



Solutions generated by algorithm are correct
account for degenerate/boundary/special cases

If a correct solution exists, algorithm finds it

Control structures (loops, recursions,...) terminate correctly
Asymptotic Running Time and/or Space Usage
Guidelines: Final Submission

Main Body of Paper:
 If
your project involves Implementation:
Informal description
 Resources & Environment:



what language did you code in?

what existing code did you use? (software libraries, etc.)

what equipment did you use? (machine, OS, compiler)
Assumptions


parameter values
Test cases

tables, figures

representative examples
Guidelines: Interim Report

Structured like Final Submission, except:
 no Abstract
or Conclusion
 fill in only what you’ve done so far
 can be revised later
 include a revised proposal if needed
 identify any issues you have encountered and
your plan for resolving them