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

Geometry

Field:

$\newcommand{\conv}{\mathit{conv}}$

Range Trees for Orthogonal Range Queries

One key idea in CG: reducing dimension

What points are in this box?

Generalize: Solve in each coordinate “separately”

Refining idea 2:

Dynamic maintenance:

$\newcommand{\indx}{\mathit{index}}$
2011 Lecture 22 End
2013 Lecture 25 End

Sweep Algorithms

Another key idea:

Convex Hull by Sweep Line

Build upper hull:

Output sensitive algorithm can achieve $O(n\log k)$ (Chan 1996).

Halfspace intersection

LP in 2 dimensions

Duality.

So, $O(n\log n)$ time.

What if no “origin in intersection”?

Segment intersections

We saw this one using persistent data structures for a query structure.

Voronoi Diagram

Goal: find nearest Athena terminal to query point.

Definitions:

Space complexity:

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:

2011 lecture 23 end

Descent of one parabola:

Site event:

Claim: no other create events.

Summary:

Randomized Incremental Constructions

BSP

Backwards Analysis---Convex Hulls

Define.

algorithm (RIC):

Runtime analysis

Linear Programming

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:

Definition.

Randomized incremental construction:

Implementation

Analysis:

Search structure

Starting idea:

Goal: apply binary search in slabs, without $n^2$ space

The structure:

Inserting an edge contained in a trapezoid

Inserting an edge that crosses trapezoids

Search time analysis