\documentclass{article} \usepackage{me} \setlength{\parindent}{0pt} $\newcommand{\vol}{\mbox{vol}}$

## 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$
$\newcommand{\conv}{\mathit{conv}}$

### 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
$\newcommand{\indx}{\mathit{index}}$
2011 Lecture 22 End
2013 Lecture 25 End

## 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
• $\indx(u,v)=k$ if $k$ lines block $v$ from $u$
• $u \dashv v$ if $v$ cut by $u$ auto
• probability $1/(1+\indx(u,v))$.
• tree size is (by linearity of $E$) $$\begin{eqnarray*} n+\sum 1/\indx(u,v) &\le & \sum_u 2H_n \end{eqnarray*}$$
• 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 $\conv(S_{i-1})\rightarrow \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 $\conv(S_i)$ hit by $\vec{p_0p}$
• say $p$ cuts this edge
• To update $p_i$ in $\conv(S_{i-1})$:
• if $p_i$ inside, discard
• delete new non hull vertices and edges
• $2$ vertices $v_1,v_2$ of $\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 $\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.