\input TR10GBReviewFormat.tex \begfile{GBnOutline.tex of October 17, 1983 8:33 pm --- Stolfi} % Proposed book outline % macros % chapter, section, etc. \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} \chapter{C}{Table of contents} % general % general \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.} \pschap{\Ch1}{The minimum spanning circle} % general % general \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.} \pschap{\Ch2}{Convex polygons} \section{Convex figures} % general \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.} \subsection{Tangents to convex figures} \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?} \section{Convex polygons} \subsection{Definition} \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).} \section{Point-polygon problems} \subsection{Point inclusion} \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.} \subsection{Star-shaped polygons} \item{Motivated by the point-inclusion algorithm.} \subsection{Monotone polygons} \item{Point location. \remk{Should testing for monotonicity be given as an exercise, or postponed?}.} \subsection{Point-polygon tangents} \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.} \subsection{Point-polygon distance} \section{Line-polygon problems} \subsection{Line location} \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.} \subsection{Geometric duality} \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.} \subsection{Line-polygon intersection} \item{Reduces to point-polygon tangents by duality.} \section{Diameter of a convex polygon} % general \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?)} \section{Polygon-polygon problems} \subsection{Testing for separability/intersection} \item{Algorithms: $O(n)$, $O(\log^2 n)$, $O(\log n)$. Give either a common point or a separating line.} \subsection{Computing the intersection of two polygons} \subsection{Computing common tangents} \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).} \subsection{Polygon-polygon distance} \item{Separable case only. Use convolution?} \pschap{\Ch3}{Convex hull} \section{Definition, properties} \section{Algorithms} \subsection{Jarvis} \subsection{Graham} \subsection{Half-hull variants} \subsection{Divide-and-conquer by random split} \subsection{Divide-and-conquer by median split} \item{(a) using $O(n)$ common tangent algorithm} \item{(b) $OP(n\log h)$ using Kirkpatrick's common tangent} \subsection{On-line algorithms} \subsection{Real-time (Preparata)} \subsection{Dynamic algorithms} \section{Good-average algorithms} \subsection{Average size of convex hull} \subsection{Average-case analysis of divide-and-conquer algorithms} \subsection{Floyd-Eddy algorithm} \section{Lower bounds} \section{Intersection of half-planes} % general \item{By duality} \section{Linear programming in 2D} % general \item{Naive: compute intersection of constraints and find extremal vertices}} \item{Megiddo's algorithm?} \pschap{\Ch4}{General polygons} \section{Introduction} % general \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.} \section{Formal definitions and notation} \subsection{States and trips} \subsection{Concatenation of trips} \subsection{Equivalence of trips; tracings} \subsection{Moves and turns; polygonal tracings} \section{Winding numbers} \subsection{Interior of a polygon} \subsection{Computing winding numbers} \section{Simple polygons} % general \item{Definition and properties (?)} \item{Computer representation} \item{Visibility (?)} \subsection{Convex hull and Kernel of a simple polygon} \subsection{Area of a simple polygon} \item{By sum of signed areas of edge triangles.} \section{Convolution and related operations} % general \item{Fill this section with selected parts of Kinetic framework paper.} \section{Monostrofic polygons} % general \item{Point-polygon tangents?} \pschap{\Ch5}{Pairwise intersection problems} \remk{Proper placement of this chapter is not clear.} \section{Sweep-line technique: general} \section{Bentley-Ottman} \section{Mairson} \subsection{Intersection of simple polygons} \section{Rectangle intersection (McCreioght?)} \remk{Should it go on range-query chapter?} \pschap{\Ch6}{Decomposition problems} \section{Decomp of a simple polygon in monotone pieces} \section{Triangulation of a monotone polygon} \section{Decomposition in convex pieces (Greene)} \subsection{Optimal, $O(n^4)$} \subsection{Near-optimal, $O(n\log n)$} \pschap{\Ch7}{Two-dimensional subdivisions} \section{Definitions} % general \item{Subdivision of manifolds} \item{Straight-line, convex, monotone, and triangular subdivisions} \section{Euler's relation} % general \remk{Perhaps prove it later, using Splices?} \section{Edge algebras} \section{The quad-edge data structure} \subsection{Definition} \subsection{Operations} \subsection{Basic algorithms?} \subsection{Superposition of two subdivisions (Mairson/Nievergelt)} \pschap{\Ch8}{Point location in planar subdivisions} \section{Naive algorithms} \section{On-line problem} \subsection{Slab techniques} \subsection{Lee-preparata} \subsection{Kirkpatrick} \subsection{Segment tree?} \section{Batch location by line sweep} \pschap{\Ch9}{Polyhedra} \section{Definition} % general \item{Based on 2D subdivisions.} \section{Convex polyhedra} % general \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.} \section{Point, line and plane location on convex polyhedra} % general \item{Reduce to point location in a planar subdivision?} \section{Exremal vertices of a convex polyhedron} \section{Plane-polyhedron intersection} \section{3D convex hull} % general \item{Naive algorithm (Dijkstra's?)} \item{Divide-and-conquer by planar split. What about random split?} \section{Intersection of half-spaces} % general \item{Use duality.} \section{Linear programming in 3D} % general \item{Naive; compute polyhedron and find extremal point} \item{Megiddo's?} \section{Intersection of convex polyhedra} \subsection{Detection} \subsection{Reporting} \section{Odds and ends} \subsection{Convolution of polyhedra?} \subsection{Problem of diameter of polyhedron} \subsection{Volume of a polyhedron} \subsection{Decomposition into tetrahedra} \item{Convex polyhedra.} \item{Necessity of "Steiner" vertices.} \item{$O(n^2)$ pieces in worst-case.} \pschap{\Ch{10}}{Geometric searching} \section{Rectangle queries (2D)} % general \item{McCreight, etc} \section{Orthogonal range queries} % general \item{Bentley?, etc.} \section{Half-plane queries} \section{Half-space queries} \section{Circle queries} % general \item{Reduce to half-space queries by quadratic mapping} \section{Polygon queries} \section{Other data structures?} % general \item{Quad trees, k-d trees, cell techniques?} \pschap{\Ch{11}}{Closest-point and related problems} % general % general \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} \pschap{\Ch{12}}{Optimization problems} % general \remk{Problems of the sort: find a (big) object X such that its total cost is minimum} \section{MST} % general \item{Including MST in $L1$ metric.} \section{Steiner tree?} \section{Minimum matching} \section{Traveling salesman tour?} \section{Minimum-weight tringulation?} \pschap{\Ch{13}}{Odds and ends to fit somewhere} \section{Union problems} % general \item{Connected components; Union of rectagons, polygons, polyhedra, etc.} \section{Minimum spanning ellipse, rectangle, parallelpiped, etc.} \section{Stabbing line problems} \section{Hemisphere containment problem.} \par\vfill\eject\end