6.854 Notes #27

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\)

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\) intervalSolution: 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

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

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).

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

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!

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.

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)\).

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*fociwhich 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 fociwhich 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 lineouter 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 lineonly

**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

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)\) autogives randomized construction

equally important, gives

**probabilistic existence proof**of a small BSPso might hope to find deterministically.

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)\),

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})}\]

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)\)

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 vanishesSo prob. \(1/i\)

Total \(O(1/i)\) for \(i^{th}\) insert, so \(O(\log n)\) overall.