Geometry
Field:
We have been doing geometry—eg linear programming
But in computational geometry, historical key difference in focus: low dimension \(d\)
(more recently, innovations in “high dimensional CG”)
Lots of algorithms that are great for \(d\) small, but exponential in \(d\)
Range Trees for Orthogonal Range Queries
One key idea in CG: reducing dimension
Do some work that reduces problem to smaller dimension
Since few dimensions, work doesn’t add up much.
What points are in this box?
goal: \(O(n)\) space
query time \(O(\log n)\) plus number of points
(can’t beat \(\log n\) even for 1d)
1d solution: binary tree.
Find leftmost in range
Walk tree till rightmost
Generalize: Solve in each coordinate “separately”
Idea 1: solve each coord, intersecting
Too expensive: maybe large solution in each coord, none in intersection
Idea 2:
we know \(x\) query will be an interval,
so build a \(y\)-range structure on each distinct subrange of points by \(x\)
Use binary search to locate right \(x\) interval
Then solve 1d range search on \(y\)
Problem: \(n^2\) distinct intervals
So \(n^3\) space and time to build
Refining idea 2:
Build binary search tree on \(x\) coords
Each internal node represents a tree subinterval containing some points
Our query’s \(x\) interval can be broken into \(O(\log n)\) tree subintervals (think of the subtree between search paths of two endpoints of that \(x\) interval)
We want to reduce dimension: on each subinterval, range search \(y\) coords only among nodes in that \(x\) interval
Solution: each internal node has a \(y\)-coord search tree on points in its subtree
Size: \(O(n\log n)\), since each point in \(O(\log n)\) internal nodes
Query time: find \(O(\log n)\) nodes, range search in each \(y\)-tree, so \(O(\log^2 n)\) (plus output size)
more generally, \(O(\log^d n)\)
fractional cascading improves to \(O(\log n)\)
Dynamic maintenance:
Want to insert/delete points
Problem to maintain tree balance
When insert \(x\) coord, may want to re-balance
Rotations are obvious choice, but have to rebuild auxiliary structures
Linear cost to rotate a tree.
Remember treaps?
We showed expect 1 rotation
Can show expected size of rotated tree is small
Then insert \(y\) coord in \(O(\log n)\) auxiliary structures
So, \(O(\log^2 n)\) update cost
Sweep Algorithms
Another key idea:
dimension is low
so worth expending lots of energy to reduce dimension
plane sweep is a general-purpose dimension reduction
Run a plane/line across space
Study only what happens on the frontier
Need to keep track of “events” that occur as sweep line across
simplest case, events occur when line hits a feature
Convex Hull by Sweep Line
define
good for: width, diameter, filtering
assume no 3 points on straight line.
output:
points and edges on hull
in counterclockwise order
can leave out edges by hacking implementation
\(\Omega(n\log n)\) lower bound via sorting
Build upper hull:
Sort points by \(x\) coord
Sweep line from left to right
maintain upper hull “so far”
as encounter next point, check if hull turns right or left to it
if right, fine
if left, hull is concave. Fix by deleting some previous points on hull.
just work backwards till no left turn.
Each point deleted only once, so \(O(n)\)
but \(O(n\log n)\) since must sort by \(x\) coord.
Output sensitive algorithm can achieve \(O(n\log k)\) (Chan 1996).
Halfspace intersection
LP in 2 dimensions
feasibility problem is deciding whether halfspace intersection nonempty
and optimization is easy, given intersection
just visit all vertices in linear time
Duality.
Assume origin inside intersection
map \((a,b) \rightarrow L_{ab} = \{(x,y) \mid ax+by+1=0\}\).
\((a,b) \in L_{qr}\) implies \(qa+rb+1=0\) implies \((q,r) \in L_{ab}\)
so \((q,r) = \bigcap_{(a,b) \in L_{qr}} L_{ab}\)
line through two points becomes point at intersection of 2 lines
point at distance \(d\) antipodal line at distance \(1/d\).
intersection of halfspace become convex hull.
So, \(O(n\log n)\) time.
What if no “origin in intersection”?
ignore verticals
divide into plances that “look up” and “look down”
i.e. each contains either \((0,\infty)\) or \((0,-\infty)\)
easy to find feasible “origin” in each half
then build polygon for each half
the interset the two polygons
Segment intersections
We saw this one using persistent data structures for a query structure.
Maintain balanced search tree of segments ordered by current height.
Heap of upcoming “events” (line intersections/crossings)
pull next event from heap, output, swap lines in balanced tree
check swapped lines against neighbors for new intersection events
lemma: next event always occurs between neighbors, so is in heap
note: next event is always in future (never have to backtrack).
so sweep approach valid
and in fact, heap is monotone!
Voronoi Diagram
Goal: find nearest Athena terminal to query point.
Definitions:
point set \(p\)
\(V(p_i)\) is space closer to \(p_i\) than anything else
for two points, \(V(P)\) is bisecting line
For 3 points, creates a new “voronoi” point
And for many points, \(V(p_i)\) is intersection of halfplanes, so a convex polyhedron
And nonempty of course.
but might be infinite
Given VD, can find nearest neighbor via planar point location:
\(O(\log n)\) using persistent trees
Space complexity:
VD is a planar graph: no two voronoi edges cross (if count voronoi points)
add one point at infinity to make it a proper graph with ends
Euler’s formula: \(n_v-n_e+n_f=2\)
By induction.
Removing one edge kills one face, cancels
Removing shortcutting degree two vertex removes on vertex and one edge, cancels
eventually you have a triangle: 3 vertices, 3 edges, 2 faces (inside and out).
(\(n_v\) is voronoi points, not original ones)
But \(n_f = n\)
Also, every voronoi point has degree at least 3 while every edge has two endpoints.
Thus, \(2n_e \ge 3(n_v+1)\)
rewrite \(2(n+n_v-2) \ge 3(n_v+1)\)
So \(n-2 \ge (n_v+3)/2\), i.e., \(n_v \le 2n-7\)
Gives \(n_e \le 3n-6\)
Summary: \(V(P)\) has linear space and \(O(\log n)\) query time.
Construction
VD is dual of projection of lower CH of lifting of points to parabola in 3D.
And 3D CH can be done in \(O(n\log n)\)
Can build each voronoi cell in \(O(n\log n)\), so \(O(n^2\log n)\).
Sweep Line
Basic idea:
Build portion of Voronoi behind sweep line.
problem: not fully determined! may be about to hit a new site.
What is determined? Stuff closer to a point than to line
boundary is a parabola
boundary of known space is pieces of parabolas: “beach line”
as sweep line descends, parabolas descend too.
We need to maintain beach line as “events” change it
2011 lecture 23 end
Descent of one parabola:
sweep line (horizontal) \(y\) coord is \(t\)
Equation \((x-x_f)^2+(y-y_f)^2 = (y-t)^2\).
Fix \(x\), find \(dy/dt\)
\(2(y-y_f)dy/dt = 2(y-t)(dy/dt-1)\)
So \(dy/dt=(y-t)/(y_f-t)\)
Thus, the higher \(y_f\) (farther from sweep line) the slower parabola descends.
Two parabolas
when sweep line hits second point, creates new parabola
called a “site event”
new parabola starts degenerate—a vertical line
we can see where it intersects first parabola
as sweep descends, broadens into another parabola
splits first parabola in two—now three pieces
topologically interesting: intersection of parabolas
point at intersection is equidistant from sweep and both foci
which means it is on the bisector
as sweep descends, intersection traces out bisector
note there are two intersections; they trace out bisector in both directions
so one intersection is tracing upwards as sweep descends
More parabolas
more generally, voronoi edge gets traced by two intersecting parabolas
when does edge “stop”? When it collides with another edge to make a Voronoi point.
happens at intersection of 3 parabolas that were all beach line
equidistant from 3 sites: “circle event”
after intersection, one parabola vanishes—falls behind the beach line
Summary:
site event adds segment to beach line
circle event removes segment from beach line
Topology:
“breakpoints” where two parabola’s of beach line meet up
these points are equidistant from sweep line and both foci
which means they are on the bisector of the two points
which is a voronoi edge because no other points are closer
since other parabola are “higher”, so farther, so foci are farther too
as sweep line descends, this intersection traces out the voronoi edge
what changes breakpoints? changes in voronoi edges
case 1: a single edge splits in two
a new voronoi region is created “between” the previous two
What changes the beach line?
Site event:
Sweep line hits site
creates new degenerate parabola (vertical line)
widens to normal parabola
adds arc piece to beach line.
Claim: no other create events.
case 1: one parabola passing through one other
At crossover, two parabolas are tangent.
then “inner” parabola has higher focus then outer
so descends slower
so outer one stays ahead, no crossover.
this case cannot happen
case 2: new parabola descends through intersection point of two previous parabolas.
At crossover, all 3 parabolas intersect
thus, all 3 foci and sweep line on boundary of circle with intersection at center.
called circle event
“appearing” parabola has highest focus
so it is slower: won’t cross over
In fact, this is how parabola’s disappear from beach line
outer parabolas catch up with, cross inner parabola.
Summary:
maintain beach line as pieces of parabolas
Note one parabola may appear several times
only site events add to beach line
only circle events remove from beach line.
\(n\) site events
so only \(n\) circle events
as insert/remove events, only need to check for events in newly adjacent parabolas
so \(O(n\log n)\) time
Randomized Incremental Constructions
BSP
linearity of expectation. hat check problem
Rendering an image
render a collection of polygons (lines)
painters algorithm: draw from back to front; let front overwrite
need to figure out order with respect to user
define BSP.
BSP is a data structure that makes order determination easy
Build in pre-process step, then render fast.
Choose any hyperplane (root of tree), split lines onto correct side of hyperplane, recurse
If user is on side 1 of hyperplane, then nothing on side 2 blocks side 1, so paint it first. Recurse.
time=BSP size
sometimes must split to build BSP
how limit splits?
auto-partitions
random auto
analysis
\(\mathit{index}(u,v)=k\) if \(k\) lines block \(v\) from \(u\)
\(u \dashv v\) if \(v\) cut by \(u\) auto
probability \(1/(1+\mathit{index}(u,v))\).
tree size is (by linearity of \(E\)) \[\begin{aligned} n+\sum 1/\mathit{index}(u,v) &\le & \sum_u 2H_n \end{aligned}\]
result: exists size \(O(n\log n)\) auto
gives randomized construction
equally important, gives probabilistic existence proof of a small BSP
so might hope to find deterministically.
Backwards Analysis—Convex Hulls
Define.
algorithm (RIC):
random order \(p_i\)
insert one at a time (to get \(S_i\))
update \(\mathit{conv}(S_{i-1})\rightarrow \mathit{conv}(S_i)\)
new point stretches convex hull
remove new non-hull points
revise hull structure
Data structure:
point \(p_0\) inside hull (how find?)
for each \(p\), edge of \(\mathit{conv}(S_i)\) hit by \(\vec{p_0p}\)
say \(p\) cuts this edge
To update \(p_i\) in \(\mathit{conv}(S_{i-1})\):
if \(p_i\) inside, discard
delete new non hull vertices and edges
\(2\) vertices \(v_1,v_2\) of \(\mathit{conv}(S_{i-1})\) become \(p_i\)-neighbors
other vertices unchanged.
To implement:
detect changes by moving out from edge cut by \(\vec{p_0 p}\).
for each hull edge deleted, must update cut-pointers to \(\vec{p_iv_1}\) or \(\vec{p_iv_2}\)
Runtime analysis
deletion cost of edges:
charge to creation cost
2 edges created per step
total work \(O(n)\)
pointer update cost
proportional to number of pointers crossing a deleted cut edge
BACKWARDS analysis
run backwards
delete random point of \(S_i\) ( not \(\mathit{conv}(S_i)\)) to get \(S_{i-1}\)
same number of pointers updated
expected number \(O(n/i)\)
what \(\Pr[\mbox{update } p]\)?
\(\Pr[\mbox{delete cut edge of } p]\)
\(\Pr[\mbox{delete endpoint edge of } p]\)
\(2/i\)
deduce \(O(n\log n)\) runtime
3d convex hull using same idea, time \(O(n\log n)\),
Linear Programming
define
assumptions:
nonempty, bounded polyhedron
minimizing \(x_1\)
unique minimum, at a vertex
exactly \(d\) constraints per vertex
definitions:
hyperplanes \(H\)
basis \(B(H)\)
optimum \(O(H)\)
Simplex
exhaustive polytope search:
walks on vertices
runs in \(O(n^{d/2})\) time in theory
often great in practice
polytime algorithms exist, but bit-dependent!
OPEN: strongly polynomial LP
goal today: polynomial algorithms for small \(d\)
Randomized incremental algorithm \[T(n) \le T(n-1,d)+\frac{d}{n}(O(dn)+T(n-1,d-1)) = O(d!n)\]
Combine with other clever ideas: \[O(d^2 n) + 2^{O(\sqrt{d \log d})}\]
Trapezoidal decomposition:
Motivation:
manipulate/analayze a collection of \(n\) segments
assume no degeneracy: endpoints distinct
(simulate touch by slight crossover)
e.g. detect segment intersections
e.g., point location data structure
Basic idea:
Draw verticals at all points and intersects
Divides space into slabs
binary search on \(x\) coordinate for slab
binary search on \(y\) coordinate inside slab (feasible since lines noncrossing)
problem: \(\Theta(n^2)\) space
Definition.
draw altitudes from each endpoints and intersection till hit a segment.
trapezoid graph is planar (no crossing edges)
each trapezoid is a face
show a face.
one face may have many vertices (from altitudes that hit the outside of the face)
but max vertex degree is 6 (assuming nondegeneracy)
so total space \(O(n+k)\) for \(k\) intersections.
number of faces also \(O(n+k)\) (at least one edge/face, at most 2 face/edge)
(or use Euler’s theorem: \(n_v-n_e+n_f \ge 2\))
standard clockwise pointer representation lets you walk around a face
Randomized incremental construction:
to insert segment, start at left endpoint
draw altitudes from left end (splits a trapezoid)
traverse segment to right endpoint, adding altitudes whenever intersect
traverse again, erasing (half of) altitudes cut by segment
Implementation
clockwise ordering of neighbors allows traversal of a face in time proportional to number of vertices
for each face, keep a (bidirectional) pointer to all not-yet-inserted left-endpoints in face
to insert line, start at face containing left endpoint
traverse face to see where leave it
create intersection,
update face (new altitude splits in half)
update left-end pointers
segment cuts some altititudes: destroy half
removing altitude merges faces
update left-end pointers
(note nonmonotonic growth of data structure)
Analysis:
Overall, update left-end-pointers in faces neighboring new line
time to insert \(s\) is \[\sum_{f \in F(s)} (n(f)+\ell(f))\] where
\(F(s)\) is faces \(s\) bounds after insertion
\(n(f)\) is number of vertices on face \(f\) boundary
\(\ell(f)\) is number of left-ends inside \(f\).
So if \(S_i\) is first \(i\) segments inserted, expected work of insertion \(i\) is \[\frac1i \sum_{s \in S_i}\sum_{f \in F(s)} (n(f)+\ell(f))\]
Note each \(f\) appears at most 4 times in sum since at most 4 lines define each trapezoid.
so \(O(\frac1i \sum_f (n(f)+\ell(f)))\).
Bound endpoint contribution:
note \(\sum_f \ell(f) = n-i\)
so contributes \(n/i\)
so total \(O(n\log n)\) (tight to sorting lower bound)
Bound intersection contribution
\(\sum n(f)\) is just number of vertices in planar graph
So \(O(k_i+i)\) if \(k_i\) intersections between segments so far
so cost is \(E[k_i]\)
intersection present if both segments in first \(i\) insertions
so expected cost is \(O((i^2/n^2)k)\)
so cost contribution \((i/n^2)k\)
sum over \(i\), get \(O(k)\)
note: adding to RIC, assumption that first \(i\) items are random.
Total: \(O(n\log n+k)\)
Search structure
Starting idea:
extend all vertical lines infinitely
divides space into slabs
binary search to find place in slab
binary search in slab feasible since lines in slab have total order
\(O(\log n)\) search time
Goal: apply binary search in slabs, without \(n^2\) space
Idea: trapezoidal decom is “important” part of vertical lines
problem: slab search no longer well defined
but we show ok
The structure:
A kind of search tree
“\(x\) nodes” test against an altitude
“\(y\) nodes” test against a segment
leaves are trapezoids
each node has two children
But may have many parents
Inserting an edge contained in a trapezoid
update trapezoids
build a 4-node subtree to replace leaf
Inserting an edge that crosses trapezoids
sequence of traps \(\Delta_i\)
Say \(\Delta_0\) has left endpoint, replace leaf with \(x\)-node for left endpoint and \(y\)-node for new segment
Same for last \(\Delta\)
middle \(\Delta\):
each got a piece cut off
cut off piece got merged to adjacent trapezoid
Replace each leaf with a \(y\) node for new segment
two children point to appropriate traps
merged trap will have several parents—one from each premerge trap.
Search time analysis
depth increases by one for new trapezoids
RIC argument shows depth \(O(\log n)\)
Fix search point \(q\), build data structure
Length of search path increased on insertion only if trapezoid containing \(q\) changes
Odds of top or bottom edge vanishing (backwards analysis) are \(1/i\)
Left side vanishes iff unique segment defines that side and it vanishes
So prob. \(1/i\)
Total \(O(1/i)\) for \(i^{th}\) insert, so \(O(\log n)\) overall.