\def\pschap#1#2{
\vskip30pt minus15pt plus20pt\penalty-600
\hbox{{\chapfont CHAPTER #1. #2}}
\penalty 1000\vskip 10pt plus 3pt}

\def\section#1{
\vskip 20pt plus 10 pt minus 3pt\penalty-600
\hbox{{\hskip20pt\secfont #1}}
\penalty 1000\vskip 6pt plus 3pt}

\def\subsection#1{
\vskip 20pt plus 10 pt minus 3pt\penalty-600
\hbox{{\hskip40pt\subsecfont #1}}
\penalty 1000\vskip 6pt plus 3pt}

\def\remk#1{\hangindent60pt after0 {\small \it <<#1>>}}

\def\item#1{\hangindent60pt after0 $\bullet$ #1}

\remk{This table of contents follows a bottom-up, simple-to-complex, pseudo-random-walk strategy. In other words, (i) we introduce each concept or tool as it is needed, rather than having a "Basic tools" chapter at the beginning; (ii) we introduce each new tool or concept in a simple, restricted version first, and generalize it gradually as we go along, rather than giving the most general version from the outset; and finally (iii) we skip from topic to topic in an apparently random way, like a relaxed stroll around town, without trying to make the structure of the whole book (if there is any) visible to the reader.}

\item{This is the warm-up chapter, where many of the primitive concepts and operations we will need later on are introduced informally. Among possible candidates for such introduction: the Cartesian plane (Eucidean plane plus coordinate system), points, lines (oriented?), and circles, and counterclockwise orientation of a triangle. Also the notions of geometrical algorithm, considerations on number representation (floating point vs. rational), formula for circumcircle, etc.}

\item{This chapter doesn't seem justifiable in the bottom-up philosophy we are using here, since the warming-up will be distributed throughout the book anyway. In a more formal kind of outline, this chapter would provide the necessary motivation for the "Basic concepts and notations" chapter that would follow it.}

\item{Classical definition of convex sets. Include unbounded figures.}

\item{Define interior, boundary, exterior.}

\item{Define convex figure as closed convex set with non-empty interior.}

\remk{Simplicity would require we limit the discussion that follows to bounded figures. However, we will run into unbounded ones very soon anyway (for example, in the characterization of convex polygons as the intersection of finitely many half-planes), and then we would have to go back and revise all previous theorems and definitions. On the other hand, uniform treatment of unbounded figures sems to require the 2SP.

\item{Examples and properties.}

\item{Define oriented lines.}

\item{Define supporting (?) line of a set (a line that leaves the set entirely on its left side)}

\item{Define tangent as supporting line that touches the boundary of the set.}

\item{Associated theorems. In particular, (1) to every point on the boundary there passes at least one tangent, and (2) the figure is the intersection of the left sides of all its tangents.}

\item{Asymptotes (as limits of tangents to points at infinity).}

\remk{Shouldn't we define states and tracings (forward only) here?}

\item{Define (or at least characterize) as intersection of a finite number of half-planes. Define edges and vertices.}

\item{Computer representation (clockwise ordered list of vertices). Require strict convexity: no collinear edges (in particular, no coincident vertices).}

\item{Discuss here the angle tests, and in particular the CCW one. Give algorithm using CCW test and star-shapedness as seen from an interior point. Observe that the algorithm determines an edge of the polygon s.t. the line Op intersects that edge and therefore proves the query point p to be either inside or outside the polygon. \small{In fact, any correct algorithm which in time T concludes that "x has property Q" must have found a certificate of length $O(T)$ proving that assertion.}}

\item{Improved algorithm using a vertex as center.}

\item{Motivated by the point-inclusion algorithm.}

\item{Point location. \remk{Should testing for monotonicity be given as an exercise, or postponed?}.}

\item{Theorem on unicity of p-to-P tangent.}

\item{Naive algorithm: linear scan along P.}

\item{Use this algorithm to motivate the car analogy. Introduce the notion of state (as a point on the boundary and a tangent to that point). \remk{Extend to general convex figures?} Show that there is a circular ordering of the states, and perhaps give some properties.}

\remk{Again, for this analogy to work we must either limit ourselves to convex figures or introduce the 2SP.}

\item{Statement: given a line, test whether it intersects or not the polygon.}

\item{Define extremal vertices and tangents in a given direction. Equivalent to maximization of a linear function in a convex polygon.}

\item{Reduce line location to checking the two extremal points in the direction normal to the line. (i.e. maximizing the signed distance from the line).}

\remk{Binary search on an unimodal circular list will fit here, I suppose.}

\item{Geometric duality. The duals of points, lines and states.}

\item{The dual of a convex polygon.}

\item{Show that locating point $p$ relative to the convex polygon $P$ is equivalent to locating the line $p\ast$ relative to the polygon $P\ast$.}

\remk{By this time the 2SP seems almost inevitable.}

\item{Reduces to point-polygon tangents by duality.}

\item{Definition of diameter of set. Theorem: the diameter is the maximum distance between two antiparallel tangents (or asymptotes).}

\item{Algorithm for computing the diameter of a convex polygon.}

\item{Width and minimum enclosing rectangle as other examples of convex polygon algorithms that enumerate matching antiparallel states (perhaps as exercises?)}

\item{Algorithms: $O(n)$, $O(\log^2 n)$, $O(\log n)$. Give either a common point or a separating line.}

\item{Algorithms for separable polygons: $O(n)$ (give code?), $O(\log^2 n)$, $O(\log n)$.}

\item{Leave Kirkpatrick's $O(n)$ point-set common tangents for later.}

\item{Common tangents of intersecting polygons: use duality with intersection.}

\remk{This could be a good place to introduce convolution (of forward convex counterclockwise tracings only).}

\item{Separable case only. Use convolution?}

\item{(a) using $O(n)$ common tangent algorithm}

\item{(b) $OP(n\log h)$ using Kirkpatrick's common tangent}

\item{By duality}

\item{Naive: compute intersection of constraints and find extremal vertices}}

\item{Megiddo's algorithm?}

\item{A.k.a. Tracings}

\remk{Including brief justification of why the formalism that follows is necessary, i.e., why we can't just define a polygon by an ordered list of vertices. Perhaps example of convolution of opposite convex polygons to give outer tangents.}

\item{Definition and properties (?)}

\item{Computer representation}

\item{Visibility (?)}

\item{By sum of signed areas of edge triangles.}

\item{Fill this section with selected parts of Kinetic framework paper.}

\item{Point-polygon tangents?}

\item{Subdivision of manifolds}

\item{Straight-line, convex, monotone, and triangular subdivisions}

\remk{Perhaps prove it later, using Splices?}

\item{Based on 2D subdivisions.}

\item{Oriented planes and the 3D CCW predicate. Homogeneous coordinates.}

\item{Correspondence to planar subdivision by stereographic projection.}

\item{Inverse correspondence also by quadratic mapping.}

\item{Projective transforms on 3-space: preserve straight lines and incidence.}

\item{Perpective transformations?}

\remk{talk about two-sided space???}

\item{Duality of convex polyhedra.}

\item{Reduce to point location in a planar subdivision?}

\item{Naive algorithm (Dijkstra's?)}

\item{Divide-and-conquer by planar split. What about random split?}

\item{Use duality.}

\item{Naive; compute polyhedron and find extremal point}

\item{Megiddo's?}

\item{Convex polyhedra.}

\item{Necessity of "Steiner" vertices.}

\item{$O(n^2)$ pieces in worst-case.}

\item{McCreight, etc}

\item{Bentley?, etc.}

\item{Reduce to half-space queries by quadratic mapping}

\item{Quad trees, k-d trees, cell techniques?}

\item{{\bf Contents in preparation. Some random topics:}}

\item{Nearest-neighbor}

\item{Voronoi and Delaunay; relation with 3D convex hulls}

\item{RNG, Gabriel graph}

\item{Cell techniques}

\item{MST}

\item{Other metrics and higher dimensions}

\item{All nearest-neighbors}

\item{Furthest neighbors and All-furthest-neighbors.}

\item{Nearest line query problems}

\item{Including MST in $L
1$ metric.}

\item{Connected components; Union of rectagons, polygons, polyhedra, etc.}