\begfile{CgBib3.tex of June 15, 1984 1:50:03 am PDT --- Stolfi}

% Bibliography on computational geometry (O--Z and anonymous)

\suction{O}

\ref [\ORoChi] {\refauth{O'Rourke, J., Chien, C., Olson, T., and Naddor, D.}
\reftit{A New Linear Algorithm for Intersecting Convex Polygons.}
\refpub{Comp. Graphics and Image Processing, Vol. 19, 1982, 384--391}
\refrem{Important. A ``convolutional'' $O(n)$ algorithm for computing the intersection of two convex polygons, based on the following ``rules of the road'': the outer car always tries to stay on the forward ray of the inner car, until they meet and switch roles.}
\reftop{convex polygons, convex polygon intersection, polygonal tracings.}}

\ref [\ORoSup] {\refauth{O'Rourke, J., Supowit, K. J.}
\reftit{Some NP-hard polygon decomposition problems.}
\refpub{IEEE Transactions on Information Theory Vol. IT-29 No. 2 (March 1983), 181--190}
\refrem{Optimal decomposition of a simple polygon with holes into {\it overlapping} convex pieces is NP-hard. Same for star-shaped or spiral pieces. Proof does not hold if holes are not allowed; says it is an open problem.}
\reftop{convex polygons, convex polygon intersection, polygonal tracings.}}

\ref [\OttWid] {\refauth{Ottman, T., and Widmayer, P.}
\reftit{On translating a set of line segments.}
\refpub{[Date and place unknown]}
\refrem{Gives an optimal ($O(n\log n)$) algorithm for computing $ixdom$ of [\GuiYaoF].}}

\ref [\OukSche] {\refauth{Ouksel, M., and Sceuermann, P.}
\reftit{Multidimensional $B$-trees: analysis of dynamic behavior.}
\refpub{BIT 21 (1981), 401--418}
\refrem{BIT 21 (1981), 401--418}}

\ref [\Ous] {\refauth{Ousterhout, J. K.}
\reftit{Corner Stitching: A Data Structuring Technique for VLSI Design Tools.}
\refpub{[Date and place unknown]}}

\ref [\OveLeeI] {\refauth{Overmars, M. H., and Leeuwen, J. van}
\reftit{Maintenance of configurations in the plane.}
\refpub{Journal of Computer and System Sciences [Issue unknown] (1981), 166--204. Also Tech. Rep. RUU-CS-79-9, Univ. of Utrecht, 1980}
\refrem{A classic. General technique for maintaining configurations of points and lines in the plane so as to allow fast insertion, deletion and binary-search queries, and using only $O(n)$ storage. In particular considers the maintenance of the convex hull of $n$ points, the intersection of $n$ half-planes, and the maxima o a set of $n$ points, with $O(\log^2 n)$ insertion and deletion, and $O(\log n)$ query time. Uses these algorithms to compute the convex layers of $n$ points in $O(n\log^2 n)$ time. Also shows how to compute the maxima of $n$ points on-line (no deletions) in $O(n\log n)$ time.}
\reftop{divide-and-conquer techniques, decomposablee searching problems, convex hull, maxima of a point set, intersection of half-planes, convex layers, dynamical algorithms, dinamization techniques.}}

\ref [\OveLeeII] {\refauth{Overmars, M. H., and Leeuwen, J. van}
\reftit{Further comments on Bykat's convex hull algorithm.}
\refpub{Information Proc. letters Vol. 10 No. 4$+$5 (Jul. 1980), 209--212}
\refrem{Bykat = Eddy, proof of linearity for uniform distribution.}}

\ref [OveLeeIII] {\refauth{Overmars, M. H., and Leeuwen, J. van}
\reftit{Dynamically maintaining configurations in the plane.}
\refpub{Proc. 12th Annual ACM Symp. on Theory of Computing (Apr. 1980), 135--145}}

\ref [\OveLeeIV] {\refauth{Overmars, M. H., and van Leeuwen, J.}
\reftit{Worst-case optimal insertion and deletion methods for decomposable searching problems.}
\refpub{Information Processing Letters Vol. 12, 168--173 (1981)}
\refrem{Applications to dynamic range queries and nearest neighbor searching.}}

\suction{P}

\ref [\Pap] {\refauth{Papadimitriou, C. H.}
\reftit{Worst-case and probabilistic analysis of a geometric location problem.}
\refpub{SIAM J. on Computing Vol. 10 (1981), 542--557. Also Tech. Rep. MIT/LCS/TM-153, Massachusetts Inst. of Technology, Feb. 1980}
\refrem{Selecting reps in L1.}}

\ref [\PapBen] {\refauth{Papadimitriou, C. H., and Bentley, J. L.}
\reftit{A worst-case analysis of nearest-neighbor searching by projection.}
\refpub{In [\BenFauII]. Also manuscript [Date and place unknown]}}

\ref [\Pos] {\refauth{Post, M. J.}
\reftit{A Minimum spanning ellipse algorithm.}
\refpub{Proc. 22nd Annual IEEE Symp. on Foundations of Computer Science (Oct. 1981), 115--122}}

\ref [\PreI] {\refauth{Preparata, F. P.}
\reftit{A note on locating a set of points in a planar subdivision.}
\refpub{SIAM J. on Computing Vol. 8, 542-545 (1979)}
\refrem{The benefits of batching.}}

\ref [\PreII] {\refauth{Preparata, F. P.}
\reftit{A new approach to planar point location.}
\refpub{SIAM J. on Computing Vol. 10 (1981), 473--482}
\refrem{Segment tree use.}}

\ref [\PreIII] {\refauth{Preparata, F. P.}
\reftit{An optimal real time algorithm for planar convex hulls.}
\refpub{Comm. ACM Vol. 22, 402--405 (1979)}
\refrem{Nice.}}

\ref [\PreHon] {\refauth{Preparata, F. P., and Hong, S. J..}
\reftit{Convex hulls of finite sets of points in two and three dimensions.}
\refpub{Comm. ACM Vol. 20 No. 2 (Feb. 1977), 87--93}
\refrem{Important classic.}
\reftop{convex polygon, convex polyhedron, convex hull, 3-dimensional convex hull, common tangents, divide-and-conquer, angle tests, Voronoi diagram.}}

\ref [\PreLips] {\refauth{Preparata, F. P., and Lipski Jr., W.}
\reftit{Three layers are enough.}
\refpub{Proc. 23rd Annual IEEE Symp. on Foundations of Computer Science (1982), 350--357}
\refrem{Nice.}}

\ref [\PreMul] {\refauth{Preparata, F. P., and Muller, D. E.}
\reftit{Finding the intersection of $n$ half-spaces in time $O(n\log n)$.}
\refpub{Theoretical Comp. Sci. Vol. 8 (1979), 44--55}
\refrem{Important. Converts the problem by dualization to the hull of $n$ points in space. The dual transform is that of ``two-sided space'', and many of its characteristics are discussed here. However, they process separately the points on top from those on the bottom, revert the two hulls to the primal, and intersect them using a different $O(n\log n)$ polyhedron intersection algorithm. Can we do it with a single convex huller on the ``two-sided space''?}
\reftop{intersection of half-spaces, duality, convex hull, higher dimensions, intersection of polyhedra, divide-and-conquer techniques.}}

\ref [\PreSup] {\refauth{Preparata, F. P., and Supowit, K. J.}
\reftit{Testing a Simple Polygon for Monotonicity.}
\refpub{Information Processing Letters Vol. 12, 161--164 (1981)}
\refrem{In Linear time.}}

\suction{R}

\ref [\RagCoh] {\refauth{Raghavan, V. V., Cohon, J., and Sahni, S.}
\reftit{Manhattan wiring.}
\refpub{Allerton Cong. Proc. [Date and issue unknown], 1--10}
\refrem{$O(n^3)$ wiring on a rectangular grid, single layer.}}

\ref [\RagYu] {\refauth{Raghavan, V. V., and Yu, C. T.}
\reftit{A note on a multidimensional searching problem.}
\refpub{Information Processing Letters Vol. 6, 133--135 (1977)}
\refrem{Unclear.}}

\ref [\ReiSup] {\refauth{Reingold, E. M., and Supowit, K. J.}
\reftit{Probabilistic analysis of divide-and-conquer heuristics for minimum weighted euclidean matching.}
\refpub{Networks Vol. 13 (1983) 49--66}
\refrem{Gives expected time and expected solution cost of matchings found by various divide-and-conquer heuristic algorithms. Assumes uniform distribution of vertices on the unit square.}}

\ref [\RenSul] {\refauth{R\'enyi, A. and Sulanke, R.}
\reftit{\"Uber die konvexe H\"ulle von $n$ zuf\"allig gew\"ahlten Punkten.}
\refpub{Z. Wahrscheinlichkeitstheorie Vol. 2 (1963) 75--84}
\refrem{Distribution of number of points in the convex hull. A classic.}}

\ref [\Rie] {\refauth{Riesenfeld, R. F.}
\reftit{Homogeneous coordinates and projective planes in computer graphics.}
\refpub{IEEE Computer Graphics and Automation [Issue unknown], 50--55 (Jan. 1981)}
\refrem{Homogeneous coordinates for plane computer graphics. Recognizes problems of one-sided topology.}}

\ref [\RitWoo] {\refauth{Ritter, G. L., Woodruff, H. B., Lowry, S. R., and Isenhour, T. L.}
\reftit{An algorithm for the selective nearest neighbor decision rule.}
\refpub{IEEE Trans. on Information Theory Vol. IT-21 N. 1 (Nov. 1975), 665--669}
\refrem{Application of closest-neighbor to statistical classification. Doesn't even mention Voronoi.}}

\ref [\Riv] {\refauth{Rivest, R. L.}
\reftit{The ``PI'' (placement and interconnect) system.}
\refpub{Proc. of the 19th ACM--IEEE Design Automation Conference (June 1982), 475--481}
\refrem{Description of a LISP-based VLSI design system that does subsystem placement and interconnections.}}

\ref [\Roh] {\refauth{Rohlf, F. J.}
\reftit{A probabilistic minimum spanning tree algorithm.}
\refpub{Information Processing Letters Vol. 7, 44--48 (1978). Also Res. Report RC 6502 ($\hash$28105), IBM Thomas J. Watson Res. Center, 1977}
\refrem{Uses ever coarsening grids for delta-neighbors.}}

\suction{S}

\ref [\SackTou] {\refauth{Sack, J.-R., and Toussaint, G. T.}
\reftit{A linear-time algorithm for decomposing rectilinear star-shaped polygons into convex quadrilaterals.}
\refpub{Allerton Conf. Proc. [Date and issue unknown], 21--30}
\refrem{``Rectilinear star-shaped polygons'' means rectagons with no two consecutive concave angles, i.e. ``quasi-convex'' rectagons. The hard part is doing the decomposition wit no Steiner vertices.}}

\ref [\SamI] {\refauth{Samet, H.}
\reftit{Deletion in two-dimensional quad trees.}
\refpub{Comm. ACM Vol. 23, 703--710 (1980)}
\refrem{Reasonable analysis.}}

\ref [\SamII] {\refauth{Samet, H.}
\reftit{Region representation: quadtrees from boundary codes.}
\refpub{Comm. ACM Vol. 23 No. 3 (Mar 1980), 163--170}
\refrem{Oddball. Computer graphics; companion to [\DyeRos].}
\reftop{quad trees}}

\ref [\San] {\refauth{Santalo, L. A.}
\reftit{Integral geometry and geometric probability. {\rm (Book)}.}
\refpub{Addison-Wesley, 1976}
\refrem{Find the book!!!}}

\ref [\Scha] {\refauth{Schatcher, B.}
\reftit{Decomposition of polygons into convex sets.}
\refpub{IEEE Trans. on Computers Vol. C-27 No. 11 (Nov. 1978), 1078--1082}
\refrem{Computes a convex decomposition of a simple polygon $P$ with $n$ vertices, $m$ of which concave, in $O(n m)$ time. For each concave vertex $v$, the algorithm enumerates the edges of the Delaunay triangulation of $P$ that are incident at $v$, and takes one or two of them so as to break the concave angle into convex ones. The use of Delaunay edges guarantees the output is a proper subdivision (no crossing cuts), but may produce up to four times the optimal number of cuts. Can we improve the running time by using a cleverer Delaunay algorithm?}
\reftop{polygon decomposition, convex subdivision, Delaunay diagram, triangulation of a simple polygon, Delaunay of a simple polygon.}}

\ref [\Schw] {\refauth{Schwartz, J. T.}
\reftit{Finding the minimum distance between two convex polygons.}
\refpub{Information Processing Letters Vol. 13, 168--170 (1981)}
\refrem{In time $O(\lg n)^2$.}}

\ref [\SeiI] {\refauth{Seidel, R.}
\reftit{On the size of closest-point Voronoi diagrams.}
\refpub{Tech. Rept. F 94, Technische Universit\"at Graz, (Austria, July 1982)}
\refrem{Gives exact formulas for number of $k$-facets in Voronoi diagrams in $d$-space. Uses correspondence between Voronoi in $d$ dimensions and convex hull in $d+1$ dimensions. Also analyzes the furtherst-point Voronoi.}
\reftop{convex polyhedra, higher dimensions, Voronoi diagrams, furthest-point Voronoi.}}

\ref [\SeiII] {\refauth{Seidel, R.}
\reftit{Comments on the quadatic map for computing the Voronoi diagram.}
\refpub{Letter to Leo Guibas (march 21, 1983)}
\refrem{Important. Contains several observations on the ``paraboloid projection'' $\lambda()$ used to compute the Dealunay diagram. (1) $\hull(\lambda(P))$ is the Delaunay on the bottom, and the furthest-point Delaunay on top. (2) The planes tangent to the paraboloid at $\lambda(P)$, if projected back, givee the Voronoi. (3) Stellations of this polyhedron give the $k$-th order Voronoi; this observation seems to lead to more efficient algorithms. (4) The Voronoi in any quadratic metric is given by projecting the points onto the paraboloid whose coefficient matrix is that of the metric. (We knew or suspected most of these facts.)}
\reftop{Voronoi diagram, Delaunay diagram, duality, convex hull, intersection of half-planes, furthest-point Voronoi, higher order Voronoi, higher dimensions, convex polyhedra.}}

\ref [\ShaI] {\refauth{Shamos, M. I.}
\reftit{Computational geometry {\rm (Ph. D. thesis)}.}
\refpub{Yale Univ. (Dec. 1977)}
\refrem{A classic.}}

\ref[\ShaII] {\refauth{Shamos, M. I.}
\reftit{Geometric complexity.}
\refpub{Proc. 7th Annual ACM Symp. on Theory of Computing (May 1975) 224-233}}

\ref [\ShaBen] {\refauth{Shamos, M. I., and Bentley, J. L.}
\reftit{Optimal Algorithms for Structuring Geographic Data.}
\refpub{Carnegie-Mellon Univ. [Date unknown]}}

\ref [\ShaHoeI] {\refauth{Shamos, M. I., and and Hoey, D.}
\reftit{Closest-point problems.}
\refpub{16-th Annual IEEE Symp. on Foundations of Comp. Science (Oct. 1975), 151--162}}

\ref [\ShaHoeI] {\refauth{Shamos, M. I., and and Hoey, D.}
\reftit{Geometric intersection problems.}
\refpub{[Publication unknown] FOCS? STOC? 208--215}}

\ref [\ShaYuv] {\refauth{Shamos, M. I., and Yuval, G.}
\reftit{Lower bounds from complex function theory.}
\refpub{Proc. 17th Annual IEEE Symp. on Foundations of Computer Science (Oct. 1976) 268--273}
\refrem{Lower bound of $O(n^2)$ for computing $\sum←{i,j}{dist(p←i, p←j)}$}}

\ref [\ShapFre] {\refauth{Shapira, R., and Freman, H.}
\reftit{The cyclic order property of vertices as an aid in scene analysis.}
\refpub{Comm. ACM Vol. 22, 3--9 (1979)}
\refrem{Which diagrams correspond to solids?}}

\ref [\SilI] {\refauth{Silva Filho, Y. V.}
\reftit{Average case analysis of region search in balanced $k$-$d$
trees.}
\refpub{Information Processing Letters Vol. 8, 219--223 (1979)}
\refrem{More rigorous analysis to derive $O(\sqrt{n})$ bound.}}

\ref [\SilII] {\refauth{Silva Filho, Y. V.}
\reftit{Optimal choice of discriminators in a balanced $k-d$ binary search tree.}
\refpub{Information Processing Letters Vol. 13, 67-70 (1981)}
\refrem{OK.}}

\ref [\SixWoo] {\refauth{Six, H.-W., and Wood, D.}
\reftit{The intersection problem revisited.}
\refpub{Tech. Rep. 79-CS-24, McMaster Univ. (Canada), 1979. Also BIT 20 (1980), 426--433}}

\ref [\SmaI] {\refauth{Smale, S.}
\reftit{The problem of the average speed of the simplex method.}
\refpub{Manuscript written for the International Symp. of Mathematical Programming, Bonn, 1982 [Date and place unknown]}
\refrem{Sumary of [\SmaII]}}

\ref [\SmaII] {\refauth{Smale, S.}
\reftit{On the average speed of the simplex method of linear programming.}
\refpub{Manuscript [Date and place unknown]}}

\ref [\SnyTan] {\refauth{Snyder, W. E., and Tang, D. A.}
\reftit{Finding the extrema of a region.}
\refpub{IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAM-2 N. 3 (May 1980) 266--269}}

\ref [\SoiWoo] {\refauth{Soisalon-Soininen, E., and Wood, D.}
\reftit{Optimal algorithms to compute the closure of a set of iso-rectangles.}
\refpub{[Date and place unknown]}}

\ref [\SteI] {\refauth{Steele, J. M.}
\reftit{Optimal triangulations of random samples in the plane.}
\refpub{The Annals of Probability Vol. 10 No. 3 (1982), 548--553}
\refrem{Shows that the minimal triangulation of $n$ point in the unit square has ``almost certainly'' cost $\beta\sqrt n$. Superseded by [\SupReiP]?}}

\ref [\SteII] {\refauth{Steele, J. M.}
\reftit{Complete convergence of short paths and Karp's algorithm for the TSP.}
\refpub{Mathematics of Operations Research Vol. 6 No. 3 (Aug. 1981), 374--378}
\refrem{Shows a slightly stronger version of the following known result: the minimal traveling salesman tour of $n$ point in the unit square has ``almost certainly'' cost $\beta\sqrt n$.}}

\ref [\SteYaoA] {\refauth{Steele, J. M., and Yao, A. C.}
\reftit{Lower bounds for algebraic decision trees.}
\refpub{J. of Algorithms Vol. 3 (1982), 1--8}
\refrem{Seems important. General technique for proving lower bounds on geometric and combinatorial problems; seems to include and strenghten a little A. Yao's result on the convex hull. Uses higher math.}}

\ref [\Stor] {\refauth{Stor\o y, S.}
\reftit{An algorithm for finding a vector in the intersection of open convex polyhedral cones.}
\refpub{BIT 13 (1973), 114--119}
\refrem{PL type of paper, before $O()$ era; efficiency unknown. See also [\BoyePaq]}}

\ref [\Sug] {\refauth{Sugihara, K.}
\reftit{An $n\log n$ algorithm for determining the congruity of polyhedra.}
\refpub{Journal of Computer and System Sciences [Isuue and page unknown] (May 1982)}
\refrem{Related to planar subdivision data structures.}}

\ref [\Sup] {\refauth{Supowit, K. J.}
\reftit{The relative neighborhood graph, with an application to minimum spanning trees.}
\refpub{Manuscript, Dept. of Computer Science, University of Illinois at Urbana-Champaign (May 1982). To appear in the Journal of the ACM (July 1983)}
\refrem{Important. Gives an $O(n\log n)$ algorithm for the RNG of $n$ points in the plane, based on computing the Delaunay, and then throwing away extra edges. This second step is based on looking from each vertex $v$ along each of six directions $60\deg$ apart, and checking whether $v$ is in the lune defined by the first edge encountered in this process. If so, delete the edge and repeat the test. this can be done with six line sweeps over the points, in the appropriate directions, at $O(n\log n)$ total cost. Gives also an $O(n)$ algorithm for the RNG of a convex polygon. Finally, gives an $O(n^2)$ algorithm for the RNG in arbitrary dimensions, by examining the closest neighbors of each vertex in sufficiently narrow octants. Interestingly, the size of the RNG is $O(n)$ in any dimension.\par
The algorithms are efficient but messy; perhaps they can be simplified. The technique for convex polygons doesn't seem to extend for Delaunay computation. What about the Gabriel graph? Is there an $O(n\log n)$ algorithm for the RNG in higher dimensions? (This would give an $O(n\log n)$ algorithm for MST).}
\reftop{relative neighborhood graph, convex polygons, Delaunay triangulation, minimum spanning tree, sweeping line techniques, higher dimensions, lower bounds.} }

\ref [\SupRei] {\refauth{Supowit, K. J., and Reingold, E. M.}
\reftit{Divide and conquer heuristics for minimum weighted Euclidean matching.}
\refpub{SIAM J. on Computing Vol. 12 No 1 (Feb. 1983), 118--143}
\refrem{Moderately important. $O(n)$ algorithms that give approximations to the minimum Euclidean matching on the unit square, using a trivial divide-and-conquer heuristic. The cost of the result (by the best variant of the heuristic) is at most $1.436\sqrt{n}$, which is little more than double the maximum cost of an optimum matching. However, there are sets of points for which the optimum matching costs virtually zero, but the one given by the heuristic costs $\Omega(\sqrt{n})$, so the relative error is unbounded.}
\reftop{minimum matching, divide-and-conquer techniques, lower bounds, approximate algorithms.}}

\ref [\SupReiP] {\refauth{Supowit, K. J., Reingold, E. M., and Plaisted, D. A.}
\reftit{The minimum traveling salesman problem and minimum matching in the unit square.}
\refpub{SIAM J. on Computing Vol. 12 No 1 (Feb. 1983), 144--156}
\refrem{Asymptotic worst-case analysis of the length of the optimal solutions to TSP, MM, and MST. Obtains $\max←P\set{\hbox{cost (shortest TS tour)}}=\alpha←T\sqrt{n}+o(\sqrt{n})$, and $\max←P\set{\hbox{cost (minimum-length matching)}}=\alpha←M\sqrt{n}+o(\sqrt{n})$, where $1.075\approx 2/\sqrt{\sqrt{12}}\leq 2\alpha←M\leq\alpha←T\leq\sqrt2 \approx 1.41$. Also $\max←P\set{\hbox{cost (chepest MST)}}=\alpha←S\sqrt{n}+o(\sqrt{n})$, where $2/\sqrt{\sqrt{12}}\leq \alpha←S\leq\alpha←T$. Conjectures all three $\alpha$s are equal.\par
Mentions that there is an heuristic for the TSP that runs in time $O(n\log n)$ and whose worst-case cost is also $\alpha←T\sqrt{n}+o(\sqrt{n})$; and similarly for the other two problems. If the floor function is available, then the running time reduces to $O(na(n,n))$ where $a(n,m)$ is an inverse of Ackerman's function.}
\reftop{traveling salesman problem, minimum matching, minimum spanning tree.} }

\ref [\Suz] {\refauth{Suzuki, N.}
\reftit{Analysis of pointer rotation.}
\refpub{Comm. ACM Vol. 25, 330--335 (1982)}
\refrem{Maybe related to planar subdivision data structures.}}

\suction{T}

\ref [\Tam] {\refauth{Tamminen, M.}
\reftit{The EXCELL method for efficient geometric access to data.}
\refpub{Acta Polytechnica Scandinavica, Mathematics and Computer Science Series No. 34, Helsinki (1981)}
\refrem{Divides the space in cells according to a recursive rectangular grid.}}

\ref [\Tar] {\refauth{Tarjan, R. E.}
\reftit{[Title unknown] {\rm (Book)}, Ch. 16: Minimum spanning trees.}
\refpub{Manuscript [Publisher and date unknown]}
\refrem{A lucid an very readable survey of minimum spanning tree algorithms for graphs, including the most efficient ones by Tarjan et al. Does not cover Euclidean MST. Very nice ``edge coloring'' framework.}
\reftop{minimum spanning tree.}}

\ref [\Tom] {\refauth{Tompa, M.}
\reftit{An optimal solution to a wire-routing problem.}
\refpub{STOC? [Publication and date unknown], 161--176}}

\ref [\Tour] {\refauth{Tourlakis, G.}
\reftit{Some results in computational topology {\rm (Ph. D. Thesis)}.}
\refpub{Univ. of Toronto, Dept. of Comp. Science Tech. Rep. No. 50 (Feb. 1973)}
\refrem{Oddball. Complexity of topological problems for unit-edge graphs and other objects embedded in Euclidean $n$-space. Mabe relevant for subdivisions of $n$-dimensional manifolds?}
\reftop{subdivisions of space.}}

\ref [\TousI] {\refauth{Toussaint, G. T.}
\reftit{The symmetric all-furthest-neighbor problem.}
\refpub{Manuscript [Date and place unknown]}
\refrem{Moderately important. Considers the {\it symmetric furthest neighbor problem} (i.e., furthest-point RNG): given a set of $n$ points on the plane, find all pairs $(p, q)$ such that all other points of the set are closer to $p$ or to $q$ than $\dist(p, q)$. That is, $p$ is the furthest neighbor of $q$, and $q$ of $p$.\par
There may be up to $n$ pairs in the FP RNG (only $\lfloor n/2\rfloor$ if all distances are distinct). Each of those pairs is an antipodal pair (admitting parallel tangents) of convex hull vertices. Gives an $O(n)$ algorithm for the FP RNG of an unimodal polygon: one in which $\dist(p←i, p←j)$ is a unimodal function of $j$, for all $i$ (big deal). Unimodal polygons are weakly externally visible, which implies their convex hull can be computed by the Graham scan.\par
An $O(n\log n)$ aalgorithm for the all-furthest-neighbors problem [\TousBha] can be used to give the FP RNG, in the obvious way.}
\reftop{all-furthest-neighbors problem, relative neighborhood graph, symmetric all-furthest-neighbors problem, unimodal polygons, furthest-point Voronoi, diameter, kinetic framework, convex hull.}}

\ref [\TousII] {\refauth{Toussaint, G. T.}
\reftit{The relative neighbourhood graph of a finite planar set.}
\refpub{Pattern Recognition Vol. 12 (1980), 261--268}
\refrem{An interesting concept, somewhere between the MST and Delaunay.}}

\ref [\TousIII] {\refauth{Toussaint, G. T.}
\reftit{Computational geometric problems in pattern recognition.}
\refpub{In: Kittler, J., and Pau, L. F. {\bi Pattern Recognition Theory and Applications} {\rm (book)}, 73--91, R. Deidel, 1982}
\refrem{Review of problems including convex hull of a set and of a simple polygon, diameter, Voronoi and Ionorov, RNG, visibility, distance between sets, polygon decomposition, etc.}}

\ref [\TousIV] {\refauth{Toussaint, G. T.}
\reftit{Decomposing a simple polygon with the relative neighborhood graph.}
\refpub{Allerton Conference Proceedings [Number unknown] (October 1980), 20--28. Also in manuscript.}
\refrem{Proves that the RNG of a simple polygon (RNG of its vetices with the restriction that neighbors should be visible) is a planar (but not convex) decomposition of the polygon.Doesn't have any characterization of the pieces produced. Gives an essentially brute-force $O(n^3)$ time, $O(n^2)$ space algorithm. Doesn't seem to have any advantage over Greene's $O(n\log n)$, except perhaps simplicity of code. Mentions $O(n)$ RNG algor. for convex polygon by Supowit!!}
\reftop{relative neighborhood graph, Gabriel graph, decomposition problems, simple polygons, visibility graph, delaunay triangulation.}}

\ref [\TousV] {\refauth{Toussaint, G. T.}
\reftit{Solving geometric problems with the ``rotating calipers''.}
\refpub{Proceedings of IEEE MELECON '83, Athens, Greece (May 1983) [Page unknown]}
\refrem{Important. ``Kinetic'' algorithms for convex polygon problems including common tangents, diameter, minimum spanning rectangle, convolution, recursive convex hull, etc.}
\reftop{convex polygons, kinetic framework, diameter, minimum spanning rectangle, convex hull, distance between polygons, common tangents, convolution, supporting lines.}}

\ref [\TousVI] {\refauth{Toussaint, G. T.}
\reftit{A simple proof of Pach's extremal theorem for convex polygons.}
\refpub{Pattern Recognition Letters Vol. 1 (December 1982), 85--86}
\refrem{A simple proof of the fact that the minimum-area triangle inscribed in a convex polygon has two sides that are edges of the polygon.}}

\ref [\TousAkl] {\refauth{Toussaint, G. T., Akl, S. G., and Devroye, L. P.}
\reftit{Efficient convex hull algorithms for points in two and more dimensions.}
\refpub{Tech. rep. SOCS-78.5, School of Computer Science, McGill Univ. (Canada), May 1978}
\refrem{Line sweep algorithm similar to that of Floyd. Runs in time $O(n^2)$. Variant that runs in $O(n\log n)$ using divide and conquer is also given.}}

\ref [\TousAvis] {\refauth{Toussaint, G. T., and Avis, D.}
\reftit{On a convex hull algorithm for polygons and its application to triangulation problems.}
\refpub{Pattern Recognition Vol. 15 No. 1 (UK, 1982), 23--29. Also Tech. Rep. SOCS-80.6, School of Computer Science, McGill Univ. (Canada), May 1980}
\refrem{Moderately important. Shows that Graham's scan (here called Sklansky's algorithm) does not give the convex hull of arbitrary simple polygons, but does work for the so-called {\it weakly externally visible} ones (where every vertex can seee infinitely far away). These include star-shaped and monotone polygons, and also ``quasi-convex'' rectagons (those without two consecutive right turns).\par
Notes that Graham's scan gives a triangulation for the pockets between $P$ and its hull. If the polygon is monotone and its two extremal vertices can see each other, the same scan gives a triangulation of the interior (not surprising).}
\reftop{convex hull, simple polygon, star-shaped polygons, monotone polygon, visibility in polygons, triangulation of polygons, externally visible polygons, iso-oriented polygons.}}

\ref [\TousBha] {\refauth{Toussaint, G. T., and Bhattacharya, B. K.}
\reftit{On geometric algorithms that use the furthest-point Voronoi diagram.}
\refpub{Tech. rep. SOCS-81.3, School of Computer Science, McGill Univ. (Canada), Jan. 1981.}
\refrem{Proves that an edge $e$ of the furthest-point Voronoi diagram is the diameter of a point set $P$ if and only if $P$ is contained in the circle whose diameter is $e$. Therefore, the diameter of $P$ is not necessarily realized by an edge of the f.p.V.d., and many algorithms that use this ``fact'' are trash.}}

\ref [\TousElG] {\refauth{Toussaint, G. T., and El-Gindy, H.}
\reftit{Traditinal galleries are star-shaped if every two paintings are visible from some common point.}
\refpub{Tech. rep. SOCS-81.10, School of Computer Science, McGill Univ. (Canada), March 1981}
\refrem{Proves that a rectagon is star-shaped iff for every two points on its boundary there is some point that sees both. Gives an $O(n)$ algorithm for computing the kernel of a rectagon. (For general polygons, the theorem is true if we replace {\it two} by {\it three}; this is known as Krasnosselsky's theorem.}}

\ref [\TousMcAl] {\refauth{Toussaint, G. T., and McAlear, J. A.}
\reftit{A simple $O(n\log n)$ algorithm for finding the maximum distance between two finite planar sets.}
\refpub{Pattern Recognition Letters Vol. 1 (October 1982), 21--24}
\refrem{The algorithm reduces to $O(n)$ if the points determine two simple polygons.}}

\suction{U}

\ref [\Urs] {\refauth{Ursic, S.}
\reftit{The ellipsoid algorithm for linear inequalities in exact arithmetic.}
\refpub{Proc. 23rd IEEE Symp. on Foundations of Computer Science (1982), 321--326}
\refrem{Someting like $O(n^5)$ algorithm for exact LP.}}

\suction{V}

\ref [\VaiI] {\refauth{Vaishnavi, V.}
\reftit{Optimal worst-case algorithms for rectangle intersection and batched range searching problems.}
\refpub{Tech. rep. 79-CS-12, McMaster Univ. (Canada), 1979}}

\ref [\VaiII] {\refauth{Vaishnavi, V.}
\reftit{Computing point enclosures.}
\refpub{IEEE Transactions on Computers Vol. C-31 No. 1 (Jan. 1982), 22--29}
\refrem{Converse of range-query problem: given a point, find all parallelepipeds that contain it. Uses a variant of segment trees, with $O(n \log^2 n)$ preprocessing and space, $O(\log n + A)$ query time in the plane.}}

\ref [\VaiKri] {\refauth{Vaishnavi, V., Kriegel, H. P., and Wood, D.}
\reftit{Space and time optimal algorithms for a class of rectangle intersection problems.}
\refpub{Tech. rep. 79-CS-15, McMaster Univ. (Canada), 1979}}

\ref [\VaiWooI] {\refauth{Vaishnavi, V., and Wood, D.}
\reftit{Data structures for the rectangle containment and enclosure problems.}
\refpub{Tech. Rep. 79-CS-19, McMaster Univ. (Canada), 1979}}

\ref [\VaiWooII] {\refauth{Vaishnavi, V. K., Wood, D.}
\reftit{Rectilinear line segment intersection, layered segment trees, and dynamization}
\refpub{J. Algorithms Vol. 3 (1982), 160--176}
\refrem{Learn about layered segment trees.}}

\ref [\VitWoo] {\refauth{Vit\'anyi, P. M. B., and Wood, D.}
\reftit{Computing the Perimeter of a Set of Rectangles.}
\refpub{Tech. Rep. 79-CS-23, McMaster Univ. (Canada), 1979}}

\suction{W}

\ref [\Wat] {\refauth{Watson, D. F.}
\reftit{Computing the $n$-dimensional Delaunay tesselation with application to Voronoi polytopes.}
\refpub{The Computer Journa Vol. 24 No. 2 (1981), 167--172}
\refrem{Computes Voronoi diagrams in dimension $d\geq 2$. Works on the Delaunay (represented as a list of cells, each a tuple of sites). Uses an incremental method: to adda new point, locate by brute force all cells whose circumsphere contains the point, and break each into $d+1$ new cells. If the points are inserted in order of $x$-coordinate, then a cell with center $c$ and radius $r$ can be output (and deleted from the list) as soon as $\left| x←{curr}-x←{c}\right| > r$.\par
For a random collection of points, the average number of potentially incomplete regions is $O(n^{1-1/k})$, so the total time is $O(n^{2-1/k})$ (hand-wawing). Worst case time is at least $\Omega(n^2)$, probably much more.\par Discusses handling of degeneracies, points at infinity and arithmetic errors (mentions the ``don't ask twice'' technique). Says (erroneously) that the Delaunay neighbors of a site form a convex polytope. Important.}
\reftop{Voronoi diagram, Delaunay diagram, closest-point problem, higher dimensions, incremental algorithms, degeneracies, average-case analysis.}}

\ref [\WilI] {\refauth{Willard, D. E.}
\reftit{New data structures for orthogonal queries.}
\refpub{[Date and place unknown]}}

\ref [\WilII] {\refauth{Willard, D. E.}
\reftit{Polygon retrieval.}
\refpub{SIAM J. on Computing Vol. 11 (1982), 149--165}
\refrem{Good.}}

\ref [\Willi] {\refauth{Williams, M. H.}
\reftit{Cubic map configurations.}
\refpub{Information Processing Letters Vol. 11, 180--185 (1980)}
\refrem{Oddball.}}

\ref [\WorI] {\refauth{W\"ordenweber, B.}
\reftit{Surface-triangulation.}
\refpub{C. A. D. Group Document No. 107, Computer Lab., Univ. of Cambridge, Mar. 1980}}

\ref [\WorII] {\refauth{W\"ordenweber, B.}
\reftit{Volume-triangulation.}
\refpub{C. A. D. Group Document No. 110, Computer Lab., Univ. of Cambridge, Nov. 1980}}

\suction{Y}

\ref [\YamLev] {\refauth{Yamnitsky, B., and Levin, L. A.}
\reftit{An old linear programming algorithm runs in polynomial time.}
\refpub{Proc. 23rd Annual IEEE Symp. on Foundations of Computer Science (1982), 327--328}
\refrem{Instead of diameter, use four extremal vertices in x and y.}}

\ref [\YanLee] {\refauth{Yang, C. C., and Lee, D. T.}
\reftit{A note on the all nearest-neighbor problem for convex polygons.}
\refpub{Information Processing Letters Vol. 8, 193--194 (1979)}
\refrem{Instead of diameter, use four extremal vertices in x and y.}}

\ref [\YaoAI] {\refauth{Yao, A. C.}
\reftit{A lower bound to finding convex hulls.}
\refpub{J. of the ACM Vol. 28, 780--787 (1981). Also Stanford Univ. Tech. Rept. STAN-CS-79-733 (Apr. 1979)}
\refrem{A classic. Shows that determination of the convex hull of $n$ points on the plane requires $\Omega(n\log n)$ operations in the worst case, under the quadratic decision tree model, even if we do not require the vertices of the hull to be given in ccw. order. The first (and for a long time the only) lower bound for non-linear decision trees that is independent of sorting.}
\reftop{convex hull, lower bounds.}}

\ref [\YaoAII] {\refauth{Yao, A. C}
\reftit{On constructing the minimum spanning trees in $k$-dimensional spaces and related problems.}
\refpub{SIAM J. on Computing Vol. 11 (1982), 721--736. Also Tech. Rep. STAN-CS-77-642, Stanford Univ., Dec. 1977}
\refrem{Wonderful.}}

\ref [\YaoAIII] {\refauth{Yao, A. C}
\reftit{Space-time tradeoff for answering range queries.}
\refpub{Proc. 18th Annual ACM Symp. on Theory of Computing (1982), 128--136}
\refrem{Known: $O(n(\log n)^d)$ lower bound for $n$ orthogonal range queries+ inserts+deletes in $\reals^d$. Shows the bound is actually $T\geq \alpha(S, n)$ if no deletes. Also shows that $O(n^{1+\epsilon})$ time is required for $n$ circular queries.}}

\ref [\YaoARiv] {\refauth{Yao, A. C., and Rivest, R. L.}
\reftit{On the polyhedral decision problem.}
\refpub{SIAM J. on Computing Vol. 9, 343--347 (1980)}
\refrem{The complexity of polytope inclusion in terms of faces.}}

\ref [\YaoAYaoF] {\refauth{Yao, A. C., and Yao, F. F.}
\reftit{On computing the rank function for a set of vectors.}
\refpub{Tech. Rep. UIUCDCS-R-75-699, Univ. of Illinois at Urbana-Champaign, Feb. 1975}}

\ref [\YaoF] {\refauth{Yao, F. F.}
\reftit{On the priority approach to hidden-surface algorithms (preliminary report).}
\refpub{Proc. 21st Annual IEEE Symp. on Foundations of Computer Science (Oct. 1980), 301--307}}

\ref [\YuvI] {\refauth{Yuval, G.}
\reftit{Finding near-neighbours in $k$-dimensional space.}
\refpub{Information Processing Letters Vol. 3, 113--114 (1975)}
\refrem{Grid used as buckets.}}

\ref [\YuvII] {\refauth{Yuval, G.}
\reftit{Finding nearest neighbours.}
\refpub{Information Processing Letters Vol. 5, 63--65 (1976)}
\refrem{Buckets.}}

\suction{Z}

\ref [Zol] {\refauth{Zolnowski, J. E.}
\reftit{Topics in computational geometry. {\rm (Ph. D. Thesis)}}
\refpub{Tech. Rep. STAN-CS-78-659, Stanford Univ., May 1978}}

\suction{Anonymous}

\ref [\XXXI] {\refauth{[Author unknown]}
\reftit{Corrigendum on convex hull algorithms.}
\refpub{Information Processing Letters Vol. 10, 168 (1980)}
\refrem{Find whose algorithm it is!}}

\ref [\XXXII] {\refauth{[Author unknown]}
\reftit{Convex hull.}
\refpub{Slides of a talk [Date and place unknown]}
\refrem{Find whose it is!\par
Moderately important. Projection transparencies for a talk on convex hull algorithms. Contains a survey of algorithms (Graham's, Jarvis's, and divide-and-conquer by random split, results on the average size of convex hulls and average number of maxima of $n$ vectors, average-case analysis of random-split divide-and-conquer ($O(n)$ expected time), some applications (diameter, convex hull in 3D [\PreHon], smallest enclosing circle in $O(n)$ expected time, linear programming, intersection of $n$ half-planes, maxima of $n$ vectors.\par
A very interesting part, relating to geometric duality, is the analysis of the average number of vertices on the intersection of $n$ half-planes (Ziezold's theorem).}
\reftop{convex hull, divide-and-conquer technique, average size of convex hull, intersection of half-planes, maxima of a set of vectors, diameter, minimum spanning circle, linear programming, duality, average-case analysis, higher dimensions.}}

\ref [\XXXIII] {\refauth{[Author unknown]}
\reftit{Expected number of points on hull of points drawn from triangle.}
\refpub{Manuscript [Date and place unknown]}
\refrem{Find whose it is!\par
Important. Consider a random (Poisson) distribution of points on the plane, with one point per unit area on the average. Let $P$ be the set of points that fall inside a given triangle of area $A$. Proves that the expected number of vertices of $\hull(P)$ is $f(A)={2\over 3}\ln A + O(1)$. This probably is equivalent to R\'enyi and Sulanke's result.}
\reftop{convex hull, average size of convex hull, average-case analysis}}

\ref [\XXXIV] {\refauth{[Author unknown]}
\reftit{Segments and rectangles.}
\refpub{Manuscript [Place unknown] (June 1977)}
\refrem{Find whose it is!}}