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

Geometry

Model

Applications:

Point location in line arrangements

setup:

how about a binary space partition?

A good algorithm:

Lookup method: $O(\log n)$ depth.

Simple analysis:

Proof of good

Construction time:

Randomized incremental construction

Special sampling idea:

Method:

Convex Hulls

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

Define

$\Omega(n\log n)$ lower bound via sorting

algorithm (RIC):

Data structure:

Runtime analysis

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