\documentclass[12pt]{article} \usepackage{wide,me} \parindent0pt

### Geometry

Model

• RAM
• operations on reals, including sqrts.
• (why OK)
• line segment intersections
• DISCRETE randomization

Applications:

• graphics of course
• any domain where few variables, many constraints

### Point location in line arrangements

setup:

• $n$ lines in plane
• gives $O(n^2)$ convex regions
• goal: given point, find containing region.
• for convenience, use triangulated $T(L)$
• triangulation introduces $O(n^2)$ segments (planar graph)
• assume all inside a bounding triangle

how about a binary space partition?

• single line splits input into two groups of n-1 rays
• search time (depth) could be $n$

A good algorithm:

• choose $r$ random lines $R$, triangulate
• inside each triangle, some lines.
• good if each triangle has only $an(\log r)/r$ lines in it
• choose $r$ so this is $< n/2$
• will show good with prob. 1/2
• recurse in each triangle---halves lines
• search by finding right triangle then searching its child structure
Lookup method: $O(\log n)$ depth.

Simple analysis:

• $n^2$ triangles
• prob. bad one “lives” is $2^{-r}$
• so take $r=O(\log n)$; whp no bad triangles
• polylog time to find root triangle
• so polylogarithmic search time
• better analysis shortly

Proof of good

• As with cut sampling, consider individual “problem” events, show unlikely
• Let $\Delta$ be all triplets of $L$-intersections
• when $\delta \in \Delta$ is bad:
• let $I(\delta)$ be number of lines hitting $\delta$
• let $G(\delta)$ be lines that induce $\delta$ (at least 3, at most 6)
• for bad $\delta$, must have all lines of $G(\delta)$ in $R$ (call this $B_1(\delta)$), no lines of $I(\delta)$ in $R$ (call this $B_2(\delta)$.
• bound prob. of bad $\delta$:
• we know $\Pr[\delta] \le \Pr[B_1(\delta)]\Pr[B_2(\delta)\mid B_1(\delta)]$ (why not equal? Because triangulation may not create triangle from $\delta$)
• Given $B_1(\delta)$, still need $r-|G(\delta)| \ge r-6 \ge r/2$ drawings (assuming $r > 12$)
• prob. none picked is at most $(1-\frac{|I(\delta)|}{n})^{r/2} \le e^{-rI(\delta)/2n}$
• Only care if $I(\delta) > an(\log r)/r$---large triplets
• $\Pr[B_2(\delta) \mid B_1(\delta)] \le r^{-a/2}$ for large triplet
• prob. some bad at most $r^{-a/2} \sum_\delta \Pr[B_1(\delta)]$
• sum is expected number of large triplets.
• at most $r^2$ points in sample
• at most $(r^2)^3=r^6$ triplets in sample
• expectation at most $r^6$
• choose $a>12$, deduce result.

Construction time:

• Construction recurrence: $T(n) \le nr^2 + cr^2T(an\frac{\log r}{r}) = O(n^{2+\epsilon(r)})$
• $\epsilon$ decreasing with $r$
• by choosing large $r$, arbitrarily close to $O(n^2)$
• Space recurrence: replace $nr^2$ by $r$, but get same bound
• Note $n^2$ line intersections, so this is lower bound

### Randomized incremental construction

Special sampling idea:

• Sample all except one item
• hope final addition makes small or no change

Method:

• process items in order
• average case analysis
• randomize order to achieve average case
• e.g. binary tree for sorting

### Convex Hulls

$\newcommand{\conv}{\mbox{\em conv}}$

Define

• 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

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? centroid of 3 vertices.)
• 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

Book studies 3d convex hull using same idea, time $O(n\log n)$, also gets voronoi diagram and Delauney triangulations.