\begfile{CgBib1.tex of June 15, 1984 1:23:58 am PDT --- Stolfi}

% Bibliography on computational geometry  (A--D)

\suction{A}

\ref [\AklI] {\refauth{Akl, S. G.}
\reftit{Comments on: G. Manacher, ``An application of pattern matching to a problem in geometrical complexity''.}
\refpub{Information Processing Letters Vol. 7, 86 (1978)}
\refrem{OK.}}

\ref [\AklII] {\refauth{Akl, S. G.}
\reftit{Two remarks on a convex hull algorithm.}
\refpub{Information Processing Letters Vol. 8, 108--109 (1979)}
\refrem{Bug found and fixed.}}

\ref [\AklIII] {\refauth{Akl, S. G.}
\reftit{Addendum to ``An improved algorithm to check for polygon similarity''.}
\refpub{Information Processing Letters Vol. 8, 157--158 (1979)}
\refrem{Bug found and corrected.}}

\ref [\AklTouI] {\refauth{Akl, S. G., and Toussaint, T.}
\reftit{An improved algorithm to check for polygon similarity.}
\refpub{Information Processing Letters Vol. 7, 127--128 (1978)}}

\ref [\AklTouII] {\refauth{Akl, S. G., and Toussaint, T.}
\reftit{A fast convex hull algorithm.}
\refpub{Information Processing Letters Vol. 7, 219--222 (1978)}
\refrem{Eddy's algorithm with x-sort.}}

\ref [\And] {\refauth{Andrew, A. M.}
\reftit{Another efficient algorithm for convex hulls in two dimensions.}
\refpub{Information Processing Letters Vol. 9, 216--219 (1979)}
\refrem{Sort in x.}}

\ref [\AviaSha] {\refauth{Aviad, Z., and Shamir, E.}
\reftit{A direct dynamic solution to range search and related problems for product regions.}
\refpub{Proc. 22nd Annual IEEE Symp. on Foundations of Computer Science (Oct. 1981), 123--126}}

\ref [\AvisI] {\refauth{Avis, D.}
\reftit{Comments on a lower bound for convex hull determination.}
\refpub{Information Processing Letters Vol. 11, 126 (1980)}
\refrem{Reply to [\Emd]: Linear tests (in any number) can't compute convex hulls.}
\reftop{convex hull, lower bounds, linear decision trees.}}

\ref [\AvisII] {\refauth{Avis, D.}
\reftit{On the complexity of finding the convex hull of a set of points.}
\refpub{Discrete and Applied Mathematics Vol. 4, 81--86 (1982)}
\refrem{Shows that $n\log n$ linear tests are necessary and sufficient to find the convex hull of $n$ points with integer coordinates with $k\log n$ bits each. Shows that the quadratic test of Graham's scan can be simulated by $O(k\log n)$ linear tests (not surprising - can do a multiply in that time, can't we?).}}

\ref [\AvisIII] {\refauth{Avis, D.}
\reftit{Lower bounds for geometric problems.}
\refpub{Allerton Conf. Proc.? [Date and issue unknown], 35--40}
\refrem{Important lower bounds using quadratic (?) primitives. Comments on linear-decision-tree fallacy.}}

\ref [\AvisIV] {\refauth{Avis, D.}
\reftit{A survey of heuristics for the weighted matching problem.}
\refpub{Tech. Rep. SOCS-82.4, School of Computer Science, McGill Univ. (February 1982)}
\refrem{Survey of heuristics for near-optimal solutions to the Euclidean matching problem in the plane.}}

\ref [\AvisV] {\refauth{Avis, D.}
\reftit{Worst case bounds for the Euclidean matching problem.}
\refpub{Comp. and Mathematics with Applications Vol. 7 (U.K., 1981), 251--257}
\refrem{Bounds for a greedy heuristic for the bounded (?) Euclidean matching problem in $d$ dimensions, using results from the classical theory of sphere packing.}}

\ref [\AvisBha] {\refauth{Avis, D., and Bhattacharya, B. K.}
\reftit{Algorithms for computing $d$-dimensional Voronoi diagrams and their duals.}
\refpub{Tech. Rep. SOCS-82.5, School of Computer Science, McGill Univ. (February 1982)}
\refrem{Computes the Voronoi diagram (by brute force?) in $O(dn^{\lceil d/2\rceil+1})+O(d^3n^{\lceil d/2\rceil}\log n)$ time. Computes the Delaunay by some unrelated technique, with unknown complexity.}}

\ref [\AvisElGI] {\refauth{Avis, D., and El-Gindy, H.}
\reftit{A combinatorial approach to polygon similarity.}
\refpub{IEEE Transactions on Information Theory Vol. IT-29 No. 1 (January 1983) 148--150}
\refrem{Proposes to represent a shape (simple polygon) by its visibility graph, and considering two shapes equivalent if their graphs are isomorphic under a cyclic permutation of the vertices.}}

\ref [\AvisElGII] {\refauth{Avis, D., and El-Gindy, H.}
\reftit{A simple on-line algorithm for planar convex hulls.}
\refpub{Manuscript [Place unknown], March 1983}
\refrem{Maintains the convex hull of $n$ points in the plane in $O(\log n)$ time per insertion (no deletions?). Uses 2-3-trees.}}

\ref [\AvisTouI] {\refauth{Avis, D., and Toussaint, G. D.}
\reftit{An optimal algorithm for determining the visibility of a polygon from an edge.}
\refpub{IEEE Transactions on Computers Vol. C-30 No. 12 (Dec. 1981), 910--914}
\refrem{Is all of a simple polygon visible from a point in one of its edges? from all points in some edge?.}}

\ref [\AvisTouII] {\refauth{Avis, D., and Toussaint, G. D.}
\reftit{An efficient algorithm for decomposing a polygon into star-shaped polygons.}
\refpub{Pattern Recognition Vol. 13 No. 6 (U.K., 1981), 395--398}
\refrem{An $O(n\log n)$ algorithm for decomposing a simple polygon into star-shaped pieces. Triangulates the polygon as a first step. The resulting decomposition is not necessarily optimal, but has at most $\lfloor n/3\rfloor$ pieces.}}

\ref [\AvisTouB] {\refauth{Avis, D., Toussaint, G. D., and Bhattacharya, B. K}
\reftit{On the multimodality of distances in convex polygons.}
\refpub{Comp. and Mathematics with Applications Vol. 8 No. 2 (U.K., 1982), 153--156}
\refrem{Shows that the distance from a vertex of an $n$-sided convex polygon to the others may have $n/2$ maxima and minima. Furthermore, there are polygons for which $n^2/8$ vertex-to-vertex distances are local maxima. Therefore, the general technique of Dobkin and Snyder [\DobSny] can't be used to find the diameter of a convex polygon. Poses as an open problem the determination of all furthest-neighbors of the vertices of a convex polygon in $O(n)$ time.}
\reftop{diameter, convex polygon, all-furthest-neighbors problem.}}

\suction{B}

\ref [\Bal] {\refauth{Ballard, D. H.}
\reftit{Strip trees: A hierarchical representation for curves.}
\refpub{Comm. ACM Vol. 24, 310--321 (1981)}
\refrem{Hierarchical tree representation for curves, closed under boolean operations.}}

\ref [\BarSob] {\refauth{Barndorff-Nielsen, O., and Sobel, M.}
\reftit{On the distribution of the number of admissible points in a vector sample.}
\refpub{Theory of Probability and its Applications, Vol. XI N. 2 (1966) 249--269}
\refrem{Defines the $r$-th layer of $n$ points as the points that have exactly $r-1$ other points in their upper left quadrant. Computes statistics for the number of points in the $r$-th layer.}}

\ref [\Bat] {\refauth{Batchelor, B. G.}
\reftit{Shape descriptors for labeling concavity trees.}
\refpub{Journal of Cybernetics Vol. 10 (1980) 233--237}
\refrem{Engineering? Not deep, perhaps interesting idea.}}

\ref [\Bau] {\refauth{Baumgart, B. G.}
\reftit{A polyhedron representation for computer vision.}
\refpub{AFIPS Natl. Comp. Conf. Proc. Vol. 44 (1975), 589--596}}

\ref [\BenI] {\refauth{Bentley, J. L.}
\reftit{Rectangle problems.}
\refpub{Manuscript [Date and place unknown]}}

\ref [\BenII] {\refauth{Bentley, J. L.}
\reftit{Solutions to Klee's rectangle problems.}
\refpub{[Date and place unknown]}}

\ref [\BenIII] {\refauth{Bentley, J. L}
\reftit{Multidimensional binary search trees in database applications.}
\refpub{IEEE Trans. on Software Eng. Vol. SE-5 No. 4 (Jul. 1979) 333--340}}

\ref [\BenIV] {\refauth{Bentley, J. L.}
\reftit{Algorithms for multivariate nonparametrics.}
\refpub{[Date and place unknown]}}

\ref [\BenV] {\refauth{Bentley, J. L.}
\reftit{Divide and conquer algorithms for closest point problems in multidimensional space {\rm (Ph. D. Thesis).}}
\refpub{University of North Carolina at Chapel Hill, Dec. 1976}}

\ref [\BenVI] {\refauth{Bentley, J. L.}
\reftit{Decomposable searching problems.}
\refpub{Information Processing Letters Vol. 8, 244--251 (1979). Also Tech. Rep. CMU-CS-78-145, Carnegie-Mellon Univ., 1978}
\refrem{Fundamental methodology.}}

\ref [\BenVII] {\refauth{Bentley, J. L.}
\reftit{Multidimensional divide-and-conquer.}
\refpub{Communications ACM Vol. 23 No. 4 (Apr. 1980), 214--229. Also in manuscript form [Date and place unknown]}
\refrem{Important. General divide-and-conquer paradigm in higher dimensions: to solve a problem of size $n$ in $k$ domensions, solve two problems of size $n/2$ in $k$ dimensions and one of size $n$ in $k-1$ dimensions.\par
Examples include counting octant neighbors, finding extremal points, orthogonal range queries, fixed-radius neighbors, closest pair of points, etc. Running times are generally $O(n\log^{k}n+A)$, $O(n\log^{k-1}n+A)$, $O(n\log^{k-2}n+A)$, or similar.}
\reftop{divide and conquer, maxima of a set of vectors, octant search, orthogonal range search, fixed-radius neighbors, closest pair, all-nearest-neighbor, higher dimensions, $k-d$ trees.}}

\ref [\BenVIII] {\refauth{Bentley, J. L.}
\reftit{Priority queues with range restriction.}
\refpub{[Date and place unknown]}}

\ref [\BenIX] {\refauth{Bentley, J. L.}
\reftit{Squeezing constant factors of geometric algorithms.}
\refpub{Allerton Conf. Proc. [Date and issue unknown], 11--20}
\refrem{Squeezes cycles out of the Euclidean traveling salesman problem.}}

\ref [\BenCar] {\refauth{Bentley, J. L., and Carruthers, W.}
\reftit{Algorithms for testing the inclusion of points in polygons.}
\refpub{Allerton Conf. Proc. [Issue and date unknown], 11--19}
\refrem{Nothing too profound. Re-analyzes the slab technique for point inclusion in a simple polygon, expressing running time as a function of $n$ and $k$ (max number of times a vertical line intersects the polygon). Shows that Shamos' algorithm uses $O(nk)$ space, $O(n\log n+nk)$ preprocessing, and $O(\log n)$ query time. Solves also the batched problem (locating $m$ points) in $O((n+m)\log(n+m))$ time and $O(n)$ space, by the obvious sweeping line technique. The time can be reduced to $O((n+m)\log(k+m))$ by using an $O(n\log k)$ algorithm for sorting the vertices of a single polygon by $x$.\par
Contains also empirical analysis of the algorithms, compared against some undescribed algorithm apparently due to Shamos and running in $O(n^2)$ time.}
\reftop{point inclusion, slab technique, point location, sweeping line technique, simple polygon, average-case analysis.}}

\ref [\BenFauI] {\refauth{Bentley, J. L., Faust, M. G., and Preparata, F. P.}
\reftit{Approximate algorithms for convex hulls.}
\refpub{Comm. ACM Vol. 25, 64--68 (1982)}
\refrem{Approximate algorithms, in linear time.}}

\ref [\BenFauII] {\refauth{Bentley, J. L., Faust, M. G., Papadimitriou, C. H., and Preparata, F. P.}
\reftit{Two papers on computational geometry.}
\refpub{Tech. Rep. CMU-CS-80-109, Carnegie Mellon Univ., Mar. 1980}
\refrem{Contains [\PapBen] and [\BenFauI].}}

\ref [\BenFriI] {\refauth{Bentley, J. L., Friedman, J. H., and Maurer, H. A.}
\reftit{Two papers on range searching.}
\refpub{Tech. Rep. CMU-CS-78-136, Carnegie-Mellon Univ., Aug. 1978}
\refrem{Contains [\BenFriIII] and [\BenMau].}}

\ref [\BenFriII] {\refauth{Bentley, J. L., and Friedman, J. H.}
\reftit{Fast algorithms for constructing minimal spanning trees in coordinate spaces.}
\refpub{Tech. Rep. STAN-CS-75-529, Stanford Univ., 1979.  Submitted to IEEE Trans. on Computers [Date unknown]}}

\ref [\BenFriIII] {\refauth{Bentley, J. L., and Friedman, J. H.}
\reftit{A survey of algorithms and data structures for range searching.}
\refpub{In [\BenFriI].}
\refrem{Survey of orthogonal range query techniques. Discusses in particular $k-d$ trees range trees, and $k$-ranges. Gives a comparative table for these and other methods (static structures only).}
\reftop{range queries, rectangle problems.}}

\ref [\BenHak] {\refauth{Bentley, J. L., Haken, D., and Won, R. W.}
\reftit{Fast geometric algorithms for VLSI tasks.}
\refpub{[Date and place unknown]}}

\ref [\BenKun] {\refauth{Bentley, J. L., Kung, H. T., Schkolnick, M., and Thompson, C. D.}
\reftit{On the average number of maxima in a set of vectors and applications.}
\refpub{J. of the ACM Vol. 25 (1978), 536--543. Also manuscript, Carnegie-Mellon Univ. (July 1977)}
\refrem{Derives said average ($O((\lg n)^{d-1})$) and related algorithm.}}

\ref [\BenMau] {\refauth{Bentley, J. L., and Maurer, H. A.}
\reftit{Efficient worst-case data structures for range searching.}
\refpub{In [\BenFriI]. Also manuscript [Date and place unknown]}
\refrem{Discussion of the ``$k$-ranges'' data structure for orthogonal range queries. Variants: (1) overlapping $k$-ranges: preprocessing and space $O(n^{2d-1})$, query $O(\log n+A)$; (2) modified overlapping $k$-ranges: prep. and space $O(n^{1+\epsilon})$, query $O(f(\epsilon)\log n+A)$; and (3) non-overlapping $k$-ranges: prep. $O(an\log n)$, space $O(an)$, query $O(n^{1/a}+A)$ for given integer $a$.}
\reftop{}}

\ref [\BenOttI] {\refauth{Bentley, J. L., and Ottman, Th.}
\reftit{Algorithms for reporting and counting geometric intersections.}
\refpub{Tech. Rep. CMU-CS-78-135, Carnegie-Mellon Univ. (Aug. 1978). Also IEEE Trans. on Computers Vol C-28 No. 9 (Sep. 1979), 643--647}}

\ref [\BenOttII] {\refauth{Bentley, J. L., and Ottman, Th.}
\reftit{The complexity of manipulating hierarchically defined sets of rectangles.}
\refpub{Tech. Rep. CMU-CS-81-109, Carnegie-Mellon University, Apr. 1981}
\refrem{Moderately important. Complexity of VLSI-like rectangle problems when the input is described in a language allowing definition and invocation of (non-recursive, non-parametric) symbols. Concludes that many interesting questions about the rectangles so described are $N$-hard, and some are exponential-time (because the output size is exponential).\par
The paper gives the impression that hierarchically defined rectangle problems are intractable. Note however that the problem size is defined as the length of the input, not the number of rectangles on the final design. Considering that every VLSI design is at some point expanded in full, it makes sense to take the latter as being the problem size. Then algorithms with hierarchical input are hardly slower in the worst case than those with expanded input, and are probably much faster on the average.}
\reftop{rectangle problems, hierarchical descriptions, intersection problems, point location problems, range queries, connected components, NP-hard problems, lower bounds.}}

\ref [\BenSax] {\refauth{Bentley, J. L., and Saxe, J. B.}
\reftit{An analysis of two heuristics for the Euclidean traveling salesman problem.}
\refpub{Allerton Conf. Proc.? [Date and issue unknown], 41--49}}

\ref [\BenShaI] {\refauth{Bentley, J. L.}
\reftit{A problem in multivariate statistics: algorithm, data structure and applications.}
\refpub{Tech. Rep. CMU-CS-78-110, Carnegie-Mellon University, Apr. 1978}}

\ref [\BenShaII] {\refauth{Bentley, J. L., and Shamos, M. I.}
\reftit{Divide and conquer for linear expected time.}
\refpub{Information Processing Letters Vol. 7, 87--91 (1978)}
\refrem{By Renyi, merge step is sublinear.}}

\ref [\BenShaIII] {\refauth{Bentley, J. L., and Shamos, M. I.}
\reftit{Divide-and-conquer in multidimensional space.}
\refpub{Proc. 8th. Annual ACM Symp. on Theory of Computing (May 1975) 220--230}}

\ref [\BenStaI] {\refauth{Bentley, J. L., and Stanat, D. F.}
\reftit{Analysis of range searches in quad trees.}
\refpub{Information Processing Letters Vol. 6, 170--173 (1975)}
\refrem{And comparison with empirical data.}}

\ref [\BenStaWI] {\refauth{Bentley, J. L., Stanat, D. F., and Williams, E. H., Jr.}
\reftit{The complexity of finding fixed-radius near neighbors.}
\refpub{Information Processing Letters Vol. 6, 209--212 (1977)}
\refrem{Trivial.}}

\ref [\BenWeiY] {\refauth{Bentley, J. L., Weide, B. W., and Yao, A. C.}
\reftit{Optimal expected-time algorithms for closest-point problems.}
\refpub{Allerton Con. Proc.? [Date unknown], 843--851. Also Tech. Rep. CMU-CS-79-111, Carnegie-Mellon Univ., Mar. 1979}
\refrem{Closest-point algorithms using cell techniques (assumes uniform or nearly uniform distribution in some bounded region). In particular: Post-office in $k$-space ($O(n)$ prep. and storage, $O(1)$ query); All-nearest-neighbors in $k$-space ($O(n)$ space and time); Voronoi and MST in the plane ($O(n)$ space and time); MST in $k$-space ($O(n)$ storage, $O(n\log\log n)$ time for $k$ fixed); Voronoi in $k$-space (computes any given region in $O(1)$ time with probability tending to 1).}
\reftop{nearest neighbor problem, closest-point problem, Voronoi diagram, minimum spanning tree, cell technique, average-case analysis, higher dimensions.}}

\ref [\BenWoo] {\refauth{Bentley, J. L., and Wood, D.}
\reftit{An optimal worst-case algorithm for reporting intersections of rectangles.}
\refpub{IEEE Transactions on Computers Vol. C-29 No. 7 (Jul. 1980), 571--577}}

\ref [\Bha] {\refauth{Bhattacharya, B. K}
\reftit{Application of computational geometry to pattern recognition problems {\rm (Ph. D. Thesis).}}
\refpub{Tech. Rep. TR 82-3, Simon Fraser Univ. (Canada), 1982}}

\ref [\BieNef] {\refauth{Bieri, H., and Nef, W.}
\reftit{A recursive sweep-plane algorithm, determining all cells of a finite division of $R^d$.}
\refpub{Computing, Vol. 28 (1982), 189--198}}

\ref [\Bow] {\refauth{Bowyer, A.}
\reftit{Computing Dirichlet tesselations.}
\refpub{The Computer Journal Vol. 24 No. 2 (1981), 162--166}
\refrem{Moderately important. Dirichlet (i.e., Voronoi) tesselations in $d$ dimensions. Represents the Voronoi by the unordered adjacency lists. Uses a variant of the incremental algorithm (nicely described). Uses also an iterative point-location algorithm (based on moving closer to the query point along the edges of the Delaunay) that runs on average time $O(n^{1/k})$  for random set of sites; from this concludes $O(n^{1+1/k})$ average time for the whole algorithm (fixed $k$). Worst-case time unknown.}
\reftop{Voronoi diagram, Delaunay diagram, higher dimensions, incremental algorithm, closest-point algorithm, handling degeneracies, higher dimensions, average-case analysis.}}

\ref [\BoycDob] {\refauth{Boyce, J. E., Dobkin, D. P., Drysdale, R. L. S., and Guibas, L. J.}
\reftit{Finding extremal polygons.}
\refpub{Proc. 14th Annual ACM Symp. on Theory of Computing (Apr. 1982), 282--289}
\refrem{Finds convex $k$-gon of maximum perimeter with vertices on a given $n$-point set in linear space and $O(kn\log n+n\log^2 n)$ time. In the special case $k=3$, time reduces to $O(n\log n)$. Discusses several related issues.}}

\ref [\BoyePaq] {\refauth{Boyer, M., and Paquette, L.}
\reftit{An algorithm to decide if the intersection of convex polyhedral cones has a non empty interior.}
\refpub{BIT 16 (1976), 459--465}
\refrem{Improves on [\Stor]. Still no asymptotics.}}

\ref [\Boys] {\refauth{Boyse, J. W.}
\reftit{Interference detection among solids and surfaces.}
\refpub{Comm. ACM Vol. 22, 3--9 (1979)}
\refrem{Shallow - engineering.}}

\ref [\Brai] {\refauth{Braid, I. C..}
\reftit{Notes on a geometric modeller.}
\refpub{CAD Group document No. 101, Computer Laboratory, Cambridge Univ., Cambridge CB2 3QG, England (1979)}
\refrem{A classic: the origin of Euler operators.}}

\ref [\BraiHilS] {\refauth{Braid, I. C., Hillyard, R. C., and Stroud, I. A.}
\reftit{Stepwise construction of polyhedra in geometric modeling.}
\refpub{In Brodlie, K. W. (ed.), {\it Mathematical Methods in Computer Graphics and Design}. Academic Press, London, 1980, 123--141}}

\ref [\BrasRei] {\refauth{Brassel, K. E., and Reif, D.}
\reftit{A procedure to generate Thiessen polygons.}
\refpub{Geographical Analysis Vol. 11 N. 3 (July 1979) 289--303}
\refrem{Incremental construction preceded by $x$-sort. Empirical tests seem to indicate $O(n^{6/5})$ behavior for u.d. random points; worst case is probably $O(n^2)$.}}

\ref [\Broo] {\refauth{Brooks, R. A.}
\reftit{Find-path for a PUMA-class robot.}
\refpub{Manuscript, Artificial Intelligence Laboratory, Massachusetts Inst. of Technology (1982)}
\refrem{Configuration space.}}

\ref [\BrooLoz] {\refauth{Brooks, R. A., and Lozano-P\'erez, T.}
\reftit{A subdivision algorithm in configuration space for findpath with rotation.}
\refpub{A.I. Memo No. 684, Artificial Intelligence Laboratory, Massachusetts Inst. of Technology (December 1982)}
\refrem{Configuration space using hierarchical representations.}}

\ref [\BrosDus] {\refauth{Brostow, W., Dussault, J.-P., and Fox, B. L.}
\reftit{Construction of Voronoi polyhedra.}
\refpub{Journal of Computational Phisics, Vol. 29 (1978), 81--92}
\refrem{Physicist's view of three-dimensional Voronoi. Iterative algorithm. To compute the Delaunay neighbors and the Voronoi region of a site $p_i$, enumerate the other sites by increasing distance from $p_i$. For each $p_j$ in that list, check if the bisector of $p_i$ and $p_j$ intersects the Voronoi region determined by the previous sites on the list. If it does, then add $p_j$ to the Delaunay neighbors of $p_i$, otherwise ignore $p_j$. The sorting guarantees that none of the previously found neighbors will have to be discarded. This is yet another $O(n\log n)$ algorithm for the intersection of $n$ half-planes; the total time is therefore $O(n^2\log n)$.\par The paper also notes that Voronoi diagram for a random set of $n$ sites has $O(n)$ size (is this true for any fixed dimension?). Suggests also that Gabriel graphs are more economical than Delaunay (how much more? what about relative neighborhood graphs?). Interesting.}
\reftop{Voronoi diagram, Delaunay diagram, Gabriel graph, iterative algorithm, average-case analysis.}}

\ref [\Brow] {\refauth{Brown, K. Q.}
\reftit{Comments on ``Algorithms for reporting and counting geometric intersections''.}
\refpub{IEEE Trans. on Computers Vol. C-30 No. 2 (Feb. 1981), 147--148}
\refrem{Comments on [\BenOttI]. Says that storage can be reduces to $O(n)$ instead of $O(n+I)$.}}

\ref [\BurkFre] {\refauth{Burkhard, W. A., Fredman, M, L., and Kleitman, D. J.}
\reftit{Inherent complexity trade-offs for range-query problems.}
\refpub{Theoretical Computer Science Vol. 16 (1981), 279--290}
\refrem{Important. Update/retrieve tradeoffs in generalized ``range sum'' problems. A range sum problem is of the following form. given a set $V=\set{v_1, v_2, \ldots, v_m}$ of numbers, and a family of {\it regions} ${\cal T}=\set{T_1, T_2, \ldots, T_n}$ (which are subsets of $[1\sp m]$), give algorithms for the two operations of\par
Update$(i,x)$: set $v_i\gets v_i+x$\par
Retrieve$(j)$: return $\sum_{k\in T_j} v_k$.\par
Obtains a tradeoff between the costs of the update and retrieve algorithms. Roughly, there are region families ${\cal T}$ such that if the retrieve costs $O(f(n))$ in the worst case, then the updates must cost $\Omega(n/f(n))$ in the worst case.\par
It would be nice to have the tradeoffs given in terms of the size of the $T_j$'s, but it is not clear if that problem is addressed at all. Also, it is not clear whether the result apply to `` range enumeration'' problems.}
\reftop{range queries, range sum queries, dynamization techniques, lower bounds.}}

\ref [\BurtSmi] {\refauth{Burton, R. P., and Smith D. R.}
\reftit{A hidden-line algorithm for hyperspace.}
\refpub{SIAM J. on Computing Vol. 11 (1982), 71--80}
\refrem{Fiction.}}

\ref [\BykI] {\refauth{Bykat, A.}
\reftit{Convex hull of a finite set of points in two dimensions.}
\refpub{Information Processing Letters Vol. 7, 296--298 (1978)}
\refrem{Floyd-like idea - shown to be $O(n^2)$ by Fournier [\Fou].}}

\ref [\BykII] {\refauth{Bykat, A.}
\reftit{On polygon similarity.}
\refpub{Information Processing Letters Vol. 9, 23--25 (1979)}
\refrem{Tests affine equivalence in $O(n)$.}}

\suction{C}

\ref [\CatCla] {\refauth{Catmull, E., and Clark, J.}
\reftit{Recursively generated $B$-spline surfaces on arbitrary topological meshes.}
\refpub{Computer-Aided Design (England) [Issue unknown] (1978), 350--365}
\refrem{Oddball}}

\ref [\ChaI] {\refauth{Chazelle, B.}
\reftit{Computational geometry and convexity {\rm (Ph. D. Thesis)}.}
\refpub{Tech. Rep. CMU-CS-80-150, Carnegie-mellon Univ. (Jul. 1980)}}

\ref [\ChaII] {\refauth{Chazelle, B.}
\reftit{Convex decomposition of polyhedra.}
\refpub{Proc. 13th Annual ACM Symp. on Theory of Computing (May 1981), 70--79}}

\ref [\ChaIII] {\refauth{Chazelle, B.}
\reftit{A theorem on polygon cutting with applications.}
\refpub{Proc. 23rd Annual IEEE Symp. on Foundations of Computer Science (Nov. 1982), 339--349}}

\ref [\ChaIV] {\refauth{Chazelle, B.}
\reftit{The polygon containment problem.}
\refpub{Manuscript, Carnegie-Mellon Univ. [Date and place unknown]}
\refrem{$O(pq^2)$ algorithm for deciding if polygon $P$ fits into polugon $Q$, with rotations and translations. Also $O(p+q)$ algorithm for the case without rotations. The latter is closely connected to convolution.}}

\ref [\ChaV] {\refauth{Chazelle, B.}
\reftit{An improved algorithm for the fixed-radius neighbor problem.}
\refpub{Manuscript, Brown Univ. [Date and place unknown]}
\refrem{Query time $O(\log n + A)$ ($A=$ size of answer), Preprocessing time $O(n^2\log n)$, storage $O(n^2 \log n)$. Remarks that naive solution would require $O(n^3)$ storage.}}

\ref [\ChaVI] {\refauth{Chazelle, B.}
\reftit{Optimal algorithms for computing depths and layers.}
\refpub{Technical Rep. CS-83-13, Brown Univ., April 1983}
\refrem{$O(n)$ space, $O(n\log n)$ time algorithm for computing the convex layers of a set of points. Also practical algorithm for computing convex depth of a point.}}

\ref [\ChaVII] {\refauth{Chazelle, B.}
\reftit{Applications of the concept of duality to the smallest-area triangle and the halfplanar range query problems.}
\refpub{Technical Rep. CS-83-12, Brown Univ., March 1983}
\refrem{Describes an $O(\log n + A)$ algorithm for the half-plane range query, using the convex layers of a point set. This algorithm is basically the same as Leo's. Also describes an $O(n^2)$ algorithm for finding the smallest-area triangle with vertices on a given set of points. In both cases, he uses a duality transform that maps the point $(a, b)$ to the line $y=aX+b$. We should investigate the relationship between this mapping and that of the 2SP.}}

\ref [\ChaVIII] {\refauth{Chazelle, B.}
\reftit{Filtering search: a new approach to query-answering.}
\refpub{Technical Rep. CS-83-10, Brown Univ., March 1983}
\refrem{Shows that significant improvements in efficiency of range-query problems can be obtained by balancing search time vs. report time. For example, in the extreme case when the query is going to report a substantial fraction of all the points, there is no need to have a special data structure or fancy serching algorithm; just enumeration will do. In less extreme cases, a less extreme form of this policy still can be used, and seems to give significant asymptotic improvements.}}

\ref [\ChaIX] {\refauth{Chazelle, B.}
\reftit{How to search in history.}
\refpub{Technical Rep. CS-83-08, Brown Univ., March 1983}
\refrem{Gives algorithms and data structures for the following problem: given a set of $n$ points in a line, and a sequence of $h$ updates on this set (deletions and insertions), answer efficiently queries of the form ``what was the point immediately to the left of point $v_i$ at time $t$?''. The structure takes $O(n+h)$ space and each query can be answered in $O(\log n\log h)$ time. Discusses also other derived algorithms, including point location in 3 dimensions with $O(\log^2n)$ query time and $O(n^3\log n)$ space (sic), and also dynamic/historical closest neighbor search.}}

\ref [\ChaX] {\refauth{Chazelle, B.}
\reftit{Fast computation of segment intersections.}
\refpub{Technical Rep. CS-83-11, Brown Univ., March 1983}
\refrem{Finds all intersections of a query segment with a set of given ones in $O(n^2)$ preprocessing and storage, $O(\log n + A)$ query time. If the segment has fixed slope or its line passes through a fixed point, storage reduces to $O(n)$.}}

\ref [\ChaDobI] {\refauth{Chazelle, B., and Dobkin, D.}
\reftit{Intersection of convex objects.}
\refpub{[Date and place unknown]}}

\ref [\ChaDobII] {\refauth{Chazelle, B., and Dobkin, D.}
\reftit{Decomposing a polygon into its convex parts.}
\refpub{Proc. 11th Annual ACM Symp. on Theory of Computing (Apr. 1979), 38--48}}

\ref [\ChaDobIII] {\refauth{Chazelle, B., and Dobkin, D.}
\reftit{Detection is easier than computation.}
\refpub{Proc. 12th Annual ACM Symp. on Theory of Computing (Apr. 1980), 146--152}
\refrem{Important. A collection of algorithms (in 3-space) for detecting intersection of polygon-line and polygon-polygon ($O(\log n)$), plane-polyhedron, line-polyhedron, and polygon-polyhedron ($O(\log^2 n)$), and polyhedron-polyhedron  ($O(\log^3 n)$). They use $O(n^2)$ storage (slab technique), but conjecture that $O(n\log n)$ may be sufficient with some tricks. Doesn't Kirkpatrick+duality give an $O(\log n)$ algorithm for plane-polyhedron and line-polyhedron?}
\reftop{convex polygon, convex polyhedron, intersection, separating line, line location, point location, slab technique.}}

\ref [\ChaGuiL] {\refauth{Chazelle, B., Guibas, L. J., and Lee, D. T.}
\reftit{The power of geometric duality.}
\refpub{Manuscript, May 1983}
\refrem{Half-plane queries in $O(\log n + A)$, using Leo's triangulation and 2SP duality.}}

\ref [\Chen] {\refauth{Chen, Nang-Ping.}
\reftit{New algorithms for Steiner tree on graphs.}
\refpub{[Date and place unknown]}}

\ref [\CherTar] {\refauth{Cheriton, D. , and Tarjan, R. E.}
\reftit{Finding minimum spanning trees.}
\refpub{Siam J. on Computing Vol. 5 No. 4 (Dec. 1976) 724--742}}

\ref [\Cla] {\refauth{Clark, J. H..}
\reftit{Designing surfaces in 3-D.}
\refpub{Comm. ACM Vol. 19, 454-460 (1976)}
\refrem{Graphics system.}}

\ref [\CohHic] {\refauth{Cohen, J., and Hickey, T.}
\reftit{Two algorithms for determining volumes of convex
polyhedra.}
\refpub{J. of the ACM Vol. 26, 401--414 (1979)}
\refrem{Marginal.}}

\ref [\ColYap] {\refauth{Cole, R. and Yap, C. K.}
\reftit{Geometric retrieval problems.}
\refpub{Manuscript, Courant Inst. of Mathematical Sciences, New York Univ [Date unknown; about April 1983]}
\refrem{Various sublinear, high-storage algorithms for half-plane, wedge, triangle, polygon queries in the plane.}}

\ref [\ComODo] {\refauth{Comer, D., and O'Donnell, M. J.}
\reftit{Geometric problems with application to
hashing.}
\refpub{SIAM J. on Computing Vol. 11, 217--226 (1982)}
\refrem{Min span of n points, etc.}}

\ref [\CorMac] {\refauth{Cori, R., and Machi, S.}
\reftit{Construction of maps with prescribed automorphism group.}
\refpub{Theoretical Comp. Science, Vol. 21, 1982, 91--98}}

\ref [\CoxI] {\refauth{Coxeter, H. S. M.}
\reftit{The classification of zonohedra by means of projective diagrams.}
\refpub{Journal de Math\'ematique, Vol. XLI Fasc. 2 (1962), 137--156}
\refrem{Oddball. Studies {\it zonohedra}, polyhedra whose faces are centrally symmetric polygons. Zonohedra are centrally symmetric too, and all edges parallel to a given direction have the same length. The {\it parallelohedra}, polyhedra that fill the space by repeated translations, are zonohedra (not true in four dimensions). There are five non-isomorphic parallelohedra. If we distinguish those further depending on how many equal edges they have, we get 25 different classes, all of which seem to occur as Voronoi regions of regular lattices.}
\reftop{convex polyhedra, center-symmetric polytopes, higher dimensions, Voronoi diagram, Delaunay diagram.}}

\suction{D}

\ref [\DegFin] {\refauth{Degtyar, V. U., and Finkel'shteyn, M. \t IA.}
\reftit{Classification algorithms based on construction of convex hulls of sets.}
\refpub{Engineering Cybernetics, Vol. 12 (1963) 150--154}
\refrem{Convex hull in $n$ dimensions by brute force + heuristics?}}

\ref [\DevaSze] {\refauth{D\'evai, F., and Szendr\'enyi, T.}
\reftit{Comments on convex hull of a finite point set in two dimensions.}
\refpub{Information Processing Letters Vol. 9, 141--142 (1979)}
\refrem{Bykat is wrong.}}

\ref [\Devr] {\refauth{Devroye, L.}
\reftit{A note on finding convex hulls via maximal vectors.}
\refpub{Information Processing Letters Vol. 11, 53--56 (1980)}
\refrem{Distribution on number of maximal vectors.}}

\ref [\Dob] {\refauth{Dobkin, D. P.}
\reftit{Theorectical and pragmatic concerns in computer graphics.}
\refpub{[Date and place unknown]}
\refrem{Among many other things, mentions that all numbers in Comp Geo are of the form $(a+\sqrt{r})/(b+\sqrt{s})$, for $abrs$ integers. Investigate!}}

\ref [\DobLip] {\refauth{Dobkin, D. P., and Kirkpatrick, D. G.}
\reftit{Fast detection of polyhedral intersections.}
\refpub{To appear in ICALP'82 [Date unknown]}
\refrem{$O(\log n)$ alg. for plane-polyhedron intersection detection, and $O(\log n)^2$ for polyh-polyh.}}

\ref [\DobLip] {\refauth{Dobkin, D. P., and Lipton, R., J.}
\reftit{Multidimensional searching problems.}
\refpub{SIAM J. on Computing Vol. 5, 181-186 (1976)}
\refrem{Binary search generalized.}}

\ref [\DobMun] {\refauth{Dobkin, D. P., and Ian Munro, J.}
\reftit{Efficients uses of the past.}
\refpub{Proc. 21st Annual IEEE Symp. on Foundations of Computer Science (Oct. 1980), 200--206}}

\ref [\DobRei] {\refauth{Dobkin, D. P., and Reiss, S. P.}
\reftit{The complexity of linear programming.}
\refpub{Theoretical Computer Science Vol. 11 (1980) 1--18}
\refrem{Shows that several problems in higher dimensions are polynomially related to linear programming, for example (1) is the intersection of $n$ half-spaces empty (or bounded), (2) is $p$ in the convex hull of $n$ points, (3) test whether $n$ points of $S^d$ lie on an hemisphere, (4) what is the depth of a set of $n$ points, and (5) is a set $P$ linearly separable from $Q$. The paper is pre-Khachian.}
\reftop{linear programming, convex hull, intersection of half-spaces, separability, hemisphere containment.}}

\ref [\DobSny] {\refauth{Dobkin, D. P., and Snyder, L.}
\reftit{On a general method for maximizing and minimizing among certain geometric problems.}
\refpub{Proc. 20th Annual IEEE Symp. on Foundations of Computer Science (Oct. 1979), 9--17}
\refrem{A bug in this paper was reported by Avis, Toussaint and Bhattacharya [\AvisTouB].}}

\ref [\DooSab] {\refauth{Doo, D., and sabin, M.}
\reftit{Behaviour of recursive division surfaces near extraordinary points.}
\refpub{Computer-Aided Design (England) [Issue unknown] (1978), 356--360}
\refrem{Oddball. Analyzes surfaces obtained by recursively cutting corners off a polyhedron. Refers to [\CatCla]}}

\ref [\Dry] {\refauth{Drysdale III, R. L.}
\reftit{Convex hull algorithms: a case study in computational geometry.}
\refpub{Manuscript, submitted to The Mathematical Intelligencer (Oct. 1981)}
\refrem{Important. An extremely readable summary of the main convex hull algorithms, aimed at mathematicians with no knowledge of computer science. Included are naive algorithms, Graham's Jarvis's, Shamos's, and Eddy and Floyd's. Others are briefly mentioned. The description of Eddy and Floyd's algorithm and its variantes is particularly detailed.}
\reftop{convex hull, higher dimensions, average-case analysis.}}

\ref [\DryLee] {\refauth{Drysdale III, R. L., and Lee, D. T.}
\reftit{Generalized Voronoi diagram in the plane.}
\refpub{Allerton Conf. Proc.? [Date and issue unknown], 833--843}
\refrem{Line segment Voronoi, constructed in $O(n c^{\sqrt{\log n}})$. Superseded by Kirkpatrick?}}

\ref [\Dye] {\refauth{Dyer, C. R.}
\reftit{A fast parallel algorithm for the closest pair problem.}
\refpub{Information Processing Letters Vol. 11, 49--52 (1980)}
\refrem{Linear time, with quadratic processors.}}

\ref [\DyeRos] {\refauth{Dyer, C. R., Rosenfeld, A, and Samet, H.}
\reftit{Region representation: boundary codes from quadtrees.}
\refpub{Comm. ACM Vol. 23 No. 3 (Mar 1980), 171--179}
\refrem{Quad trees. Seems tohave an epsilon of average-behavior analysis. Companion to [\SamII].}
\reftop{quad trees.}}


��$�J�
�������������