\begfile{CgBib2.tex of June 15, 1984 1:24:05 am PDT --- Stolfi} % Bibliography on computational geometry (E--N) % BUG -- check problem with \Lin! \suction{E} \ref [\EddI] {\refauth{Eddy, W. F.} \reftit{Untitled letter to R. W. Floyd.} \refpub{Attached to [\Flo] (Nov. 1976)} \refrem{Describes the Floyd-Eddy convex hull algorithm and asks for proof of average linearity.}} \ref [\EddII] {\refauth{Eddy, W. F..} \reftit{A new convex hull algorithm for planar sets.} \refpub{Manuscript [Date and place unknown]. To be published in TOMS? 1977?} \refrem{A classic.Describes the $O(n)$ expected-time convex hull algorithm of Eddy and Floyd. Has worst-case and empirical analyses only; for the average case, see [\Flo].} \reftop{convex hull, empirical analysis, average size of convex hull.}} \ref [\EdeI] {\refauth{Edelsbrunner, H.} \reftit{Dynamic data structures for orthogonal intersection queries.} \refpub{Tech. Rep. 59, Graz Tech. Univ. (Austria), Oct. 1980}} \ref [\EdeII] {\refauth{Edelsbrunner, H.} \reftit{Dynamic rectangle intersection searching.} \refpub{Tech. Rep. 47, Graz Tech. Univ. (Austria), Feb. 1980}} \ref [\EdeIII] {\refauth{Edelsbrunner, H.} \reftit{A time- and space-optimal solution for the planar all intersecting rectangles problem.} \refpub{Tech. Rep. 50, Graz Tech. Univ. (Austria), Apr. 1980}} \ref [\EdeLeeu] {\refauth{Edelsbrunner, H., and Leeuwen, J. van} \reftit{Multidimensional algorithms and data structures {\rm (bibliography).}} \refpub{EATCS Bulletin, July 1980}} \ref [\EdeMauI] {\refauth{Edelsbrunner, H., and Maurer, H. A.} \reftit{On the intersection of orthogonal objects.} \refpub{Information Processing Letters Vol. 13, 177--181 (1981)} \refrem{Segment tree use.}} \ref [\EdeMauII] {\refauth{Edelsbrunner, H., and Maurer, H. A.} \reftit{A space-optimal solution of general region location.} \refpub{Theoretical Computer Science Vol. 16 (1981), 329--336} \refrem{Seems important: Claims to be better, simpler and more general than Kirkpatrick! However takes $O(\log^3 n)$ query, $O(n\log n)$ preprocessing, and $O(n)$ space.}} \ref [\EdeMauK] {\refauth{Edelsbrunner, H., Maurer, H. A., and Kirkpatrick, D. G.} \reftit{Polygonal intersection searching.} \refpub{Information Processing Letters Vol. 14, 74--79 (1982)} \refrem{Given lots of storage, you can do everything fast.}} \ref [\EdeMauP] {\refauth{Edelsbrunner, H., Maurer, H. A., Preparata, F. P., Rosenberg, A. L., Welzl, E., and Wood, D.} \reftit{Stabbing line segments.} \refpub{BIT Vol. 22 (1982), 274--281} \refrem{Finds in $O(n\log n)$ the set of all lines that stab a collection of arbitrary segments in the plane.}} \ref [\EdeOveI] {\refauth{Edelsbrunner, H., and Overmars, M. H.} \reftit{On the equivalence of some rectangle problems.} \refpub{Information Processing Letters Vol. 14, 124--127 (1982)} \refrem{Equivalence of rectangle to dominance problems.}} \ref [\EdeOveW] {\refauth{Edelsbrunner, H., Overmars, M. H., and Wood, D.} \reftit{Graphics in Flatland: a case study.} \refpub{Rep. CS-82-25, Univ. of Waterloo (Canada), Aug. 1982} \refrem{Moderately important. A survey of problems related to 1-dimensional projections (parallel and conic) of 2-dimensional figures. Consider the problems of computing a projection, updating it as the set of objects changes, or as the view point/direction of projection changes. Generally huge costs; no big new results.} \reftop{projection, ordering in a given direction, visibility, stabbing line problem, common tangents, dinamization, divide and conquer, decomposition searching, shortest path with obstacles.}} \ref [\Efr] {\refauth{Efron, B.} \reftit{The convex hull of a random set of points.} \refpub{Biometrika Vol. 52 No. 3$+$4 (1965), 331--343} \refrem{Mildly interesting. Gives exact integrals for the average values of several properties of the convex hull of $n$ random points in two and three dimensions. Two distributions are considered: multivariate normal and uniform in a circle. The same techniques seem to be applicable to many other distributions. The properties include: vertices, faces, edges, total area, total edge length, probability content. Unfortunately, the final expressions contain unevaluated integrals (like $\int_{-\infty}^{+\infty}\Phi^n(x)\exp(x) dx$, where $\Phi$ is the gaussian integral, so the asymptotics are not readily available.} \reftop{convex hull, average size of convex hull, higher dimensions.}} \ref [\ElGAvis] {\refauth{El-Gindy, H., and Avis, D.} \reftit{A linear algorithm for computing the visibility polygon from a point.} \refpub{J. of Algorithms Vol. 2 (1981), 186--197} \refrem{Moderately mportant. Computes in $O(n)$ the parts of a simple polygon that are visible from a given interior point. The algorithm seems very similar in spirit to that of Preparata (?) for determining the directions along which a polygon is monotone, even though details and presentation are somewhat different.} \reftop{simple polygon, visibility of polygons, kernel of a simple polygon, monotone polygons.}} \ref [\Emd] {\refauth{Emde Boas, P. van} \reftit{On the $\Omega(n \log n)$ lower bound for convex hull and maximal vector determination.} \refpub{Information Processing Letters Vol. 10, 132--136 (1980)} \refrem{Proves that at least $O(n\log n)$ tests are needed to compute the convex hull of $n$ points. useless, since linear tests (in any number) are too weak to solve this problem; see [\AvisI]. Contains a survey of other lower bounds for this problem.} \reftop{convex hull, lower bounds, linear decision trees.}} \ref [\Eve] {\refauth{Even, S.} \reftit{Algorithmic Combinatorics {\rm (book)}.} \refpub{Macmillan, N. Y., 1973}} \suction{F} \ref [\Fil] {\refauth{Filotti, I. S.} \reftit{An efficient algorithm for determining whether a cubic graph is toroidal.} \refpub{Proc. 10th. Annual ACM Symp. on Theory of Computing (May 1978), 133--141}} \ref [\FilMilR] {\refauth{Filotti, I. S., Miller, G. L., and Reif, J.} \reftit{On determining the genus of a graph in $O(v^{O(g)})$ steps (preliminary report).} \refpub{Manuscript [Date and place unknown]. Corrected 16 May 1979}} \ref [\Flo] {\refauth{Floyd, R. W.} \reftit{Untitled letter to W. F. Eddy.} \refpub{Attached to [\EddI] (Feb. 1977).} \refrem{Replies to a letter by W. F. Eddy on Eddy-Floyd convex hull algorithm. proves that the algorithm is avg. linear and suggests another avg. linear algorithm that can be extended to higher dimensions.}} \ref [\ForrI] {\refauth{Forrest, A. R.} \reftit{Computational geometry project library catalogue.} \refpub{School of Computer Studies and Accountancy, Univ. of East Anglia, Norwich NR4 7TJ, England, Mar. 1983}} \ref [\ForrII] {\refauth{Forrest, A. R.} \reftit{Random toughts on geometric operations.} \refpub{Working draft. Xerox PARC, Mar. 1983} \refrem{Moderately important. List of geometric primitives, sprinkled with many comments.} \reftop{geometric primitives, polygons, duality.}} \ref [\FortHop] {\refauth{Fortune, S., and Hopcroft, J.} \reftit{A note on Rabin's nearest-neighbor algorithm.} \refpub{Information Processing Letters Vol. 8, 20--23 (1979)} \refrem{Unrandomized, in time $O(n \lg \lg n)$.}} \ref [\Fou] {\refauth{Fournier, A.} \reftit{Comments on convex hull of a finite set of points in two dimensions.} \refpub{Information Processing Letters Vol. 8, 193--194 (1979)} \refrem{Bykat is wrong.}} \ref [\FouKed] {\refauth{Fournier, A., and Kedem, Z.} \reftit{Comments on the all nearest-neighbohr problem for convex polygons.} \refpub{Information Processing Letters Vol. 9, 105--107 (1979)} \refrem{Comments on Lee and Preparata, and Yang and Lee.}} \ref [\FowPat] {\refauth{Fowler, R. J., Paterson, M. S., and Tanimoto, S. L.} \reftit{Optimal packing and covering in the plane are NP-complete.} \refpub{Information Processing Letters Vol. 12, 133--137 (1981)} \refrem{Some geometric NP-completeness results.}} \ref [\FreI] {\refauth{Fredman, M. L.} \reftit{Lower bounds on the complexity of some optimal data structures.} \refpub{To appear in SIAM J. on Computing [Date unknown]}} \ref [\FreII] {\refauth{Fredman, M. L.} \reftit{The spanning bound as a measure of range query complexity.} \refpub{To appear as Univ. of California at San Diego EECS Tech. Rep. [Date unknown]}} \ref [\FreIII] {\refauth{Fredman, M. L.} \reftit{A lower bound on the complexity of orthogonal range queries.} \refpub{To appear in J. of the ACM [Date unknown]}} \ref [\FreIV] {\refauth{Fredman, M. L.} \reftit{A near-optimal data structure for a type of range query problem.} \refpub{Proc. 11th Annual ACM Symp. on Theory of Computing (Apr. 1979), 62--66}} \ref [\FreV] {\refauth{Fredman, M. L.} \reftit{The inherent complexity of dynamic data structures which accomodate range queries.} \refpub{Proc. 21st Annual IEEE Symp. on Foundations of Computer Science (Oct. 1980), 191--199} \refrem{Very important. Gives $O(n^{4/3})$ lower bound for half-plane queries (and circles and polygons), and others. Seem the assumption of DELETES allowed is essential for these bounds (see [\YaoAIII].}} \ref [\FreVI] {\refauth{Fredman, M. L.} \reftit{Inherent complexity of range query problems.} \refpub{Allerton conf. [Date and issue unknown], 231--240} \refrem{Seems similar to (but not the same as) [\FreV].}} \ref [\FreVolI] {\refauth{Fredman, M. L., and Volper, D. J.} \reftit{The complexity of partial match retrieval in a dynamic setting.} \refpub{[Date and place unknown]}} \ref [\FreVolII] {\refauth{Fredman, M. L., and Volper, D. J.} \reftit{Query time versus redundancy: Trade-offs for range queries.} \refpub{J. of Computer and System Sciences Vol. 23 (1981), 355-365}} \ref [\FreWei] {\refauth{Fredman, M. L., and Weide, B.} \reftit{On the complexity of computing the measure of $\bigcup [a_i, b_i]$.} \refpub{Comm. ACM Vol. 21, 540--544 (1978)} \refrem{Nice lower bound arguments.}} \ref [\FreeSha] {\refauth{Freeman, H., and Shapira, R.} \reftit{Determining the minimum-area encasing rectangle for an arbitrary closed curve.} \refpub{Comm. ACM Vol. 18, 409--413 (1975)} \refrem{Finds convex hull and shows min. area rectangle must be parallel to one side of it.}} \ref [\FriBen] {\refauth{Friedman, J. H., Bentley, J. L., and Finkel, R. A.} \reftit{An algorithm for finding the best matches in logarithmic expected time.} \refpub{ACM Trans. on Math. Software Vol. 3 No. 3 (Sep. 1977), 209--226}} \suction{G} \ref [\GarJohI] {\refauth{Garey, M. R., Johnson, D. S., Preparata, F. P., and Tarjan, R. E.} \reftit{Triangulating a simple polygon.} \refpub{Information Processing Letters, Vol. 7 No. 4 (Jun. 1978), 175--179} \refrem{A classic.}} \ref [\GarJohII] {\refauth{Garey, M. R., Graham, R. L., and Johnson, D. S.} \reftit{The complexity of computing steiner minimal trees.} \refpub{SIAM J. on Applied Math. Vol. 32 No. 4 (Jun. 1977), 835--859}} \ref [\GilPol] {\refauth{Gilbert, E. N., and Pollack, H. O.} \reftit{steiner minimal trees.} \refpub{SIAM J. on Applied Math., Vol.16 No. 1 (1968), 1--29}} \ref [\GowKir] {\refauth{Gowda, I. G., and Kirkpatrick, D. G.} \reftit{Exploiting linear merging and extra storage in the maintenance of fully geometric data structures.} \refpub{Allerton Conf. Proceedings? [Date and issue unknown], 1--10} \refrem{}} \ref [\Gra] {\refauth{Graham, R. L.} \reftit{An efficient algorithm for determining the convex hull of a finite planar set.} \refpub{Information Processing Letters Vol. 1, 132--133 (1972)} \refrem{An even greater classic than Jarvis [\Jar].}} \ref [\GraYao] {\refauth{Graham, R. L., and Yao, F. F.} \reftit{Finding the convex hull of a simple polygon.} \refpub{[Date and place unknown]} \refrem{A classic. Very simple $O(n)$ algorithm. Can it be generalized to other classes (e.g., monostrofic)?} \reftop{convex hull, simple polygon, angle test.}} \ref [\GreenSib] {\refauth{Green, P. J., and Sibson, R.} \reftit{Computing Dirichlet tesselation in the plane.} \refpub{Comp. J. Vol. 21 No. 2 (1977), pp. 168--173}} \ref [\GreenSil] {\refauth{Green, P. J., and Silverman, B. W.} \reftit{Constructing the convex hull of a set of points in the plane.} \refpub{The Computer Jounal Vol. 22 No. 3 [Date unknown], 262--266} \refrem{Practical notes on implementing a modified version of Eddy's algorithm. Benchmarks.}} \ref [\Greene] {\refauth{Greene, D. H.} \reftit{The decomposition of polygons into convex parts.} \refpub{Manuscript, ca. 1980 [Date and place unknown]}} \ref [\Gro] {\refauth{Gross, J. L.} \reftit{Voltage graphs.} \refpub{Discrete Mathematics Vol. 9 (1974), 239--246} \refrem{Important. Voltage graphs seem not relevant to our concerns, but they are defined in terms of {\it rotation graphs} ($\approx$ edge algebras) and their correspondence to {\it Heffter embeddings} ($\approx$ two-dimensional subdivisions? ) is noted. (Heffter's paper was published in 1891!). They seem to consider embeddings on surfaces with branching points. Mentions duality, but no Splice. Must get main reference!} \reftop{edge algebras, subdivisions, quad-edge data structure, polyhedra.}} \ref [\GroTuc] {\refauth{Gross, J. L., and Tucker, W.} \reftit{Generating all graph coverings by permutation voltage assignments.} \refpub{Discrete Mathematics Vol. 18 (1977), 273--283} \refrem{Probably not relevant. Uses voltage graphs in several combinatorial problems. Embeddings and subdivisions are mentioned {\it en passant}.} \reftop{subdivisions, edge algebras, quad-edge data structure, polyhedra.}} \ref [\GuiYaoF] {\refauth{Guibas, L. J., and Yao, F. F.} \reftit{On translating a set of rectangles.} \refpub{Proc. 12th. Annual ACM Symp. on Theory of Computing, Apr. 1980, 154--160} \refrem{Important. Given a set of disjoint convex figures in the plane and a direction $d$, shows that the relation ``$F$ blocks $G$ in the direction $d$'' is a partial order, and shows how to compute a linear order compatible with it in $O(n\log n)$ time and $O(n)$ space. In the particular case of iso-oriented rectangles, for every quadrant there is a linear order that is compatible with all directional orderings in that quadrant. This linear order has a nice algebraic expresion in terms of the $x$- and $y$- separability relations.} \reftop{convex subdivisions, rectangular subdivisions, geometric sorting, rectangle problems, monotone subdivisions.}} \ref [\GutI] {\refauth{G\"uting, R. H.} \reftit{An optimal contour algorithm for iso-oriented rectangles.} \refpub{Tech. Rep. 82-CS-03, McMaster Univ. (Canada), 1982} \refrem{Given $n$ iso-oriented rectangles, finds the contour of their union in time $O(n\log n+A)$. Uses the sweeping line technique. Uses also a data structure (contracted segment tree) for representing $n$ intervals in $O(n)$ space that allows insertion and deletion of an interval, while reporting of all intervals covered/uncovered by it, in time $O(\log n + A)$. Can it be used to compute the union of several rectagons with $n$ sides total in $O(n\log n + A)$ time?} \reftop{rectangle problems, sweeping line technique, contracted segment tree, interval problems.}} \ref [\GutII] {\refauth{G\"uting, R. H.} \reftit{Stabbing $C$-oriented polygons.} \refpub{Information Processing Letters Vol. 16 (Jan. 1983), 35--40} \refrem{Important. $C$-oriented means that all sides are parallel to some direction of a given set $C$ of $c$ directions. The problem addressed is the following: given a point and a set of (not necessarily disjoint) $C$-oriented polygons, report the set of all polygons enclosing the point. (This includes point location in a rectangular subdivision.) Given a mixed set of points and polygons with total complexity $n$, computes all stabbing numbers in $O(cn\log n)$ time and $O(cn)$ space, by the sweeping line technique. If the polygons are given in advance, by expending $O(cn\log n)$ preprocessing and storage it is possible to compute the stabbing number of a query point in $O(c\log n)$ further time. This latter result is obtained by using segment trees, as improved by Vaishnavi [\VaiII].\par Since the answer is computed as the difference between the number of upper and lower polygon boundaries passing above the query point, the techniques here described cannot be extended to give the {\it set} of enclosing polygons.} \reftop{point-in-polygon problems, point location problems, stabbing number, iso-oriented polygons, sweeping line technique, segment tree.}} \ref [\GutWoo] {\refauth{G\"uting, R. H., and Wood, D.} \reftit{Finding rectangle intersections by divide-and-conquer.} \refpub{Tech. Rep. 82-CS-04, McMaster Univ. (Canada), 1982} \refrem{Important. Gives two divide-and-conquer (not line-sweep) algorithms for (1) reporting all intersections in a collection of vetical and horizontal line segments, in time $O(n\log n+A)$ and space $O(n\log n)$; and (1) reporting all pairs $p\in R$ from agiven collection of points and rectangles in $O(n\log n+A)$ time and $O(n)$ space. With some extra machinery, can be used to report rectangle intersections in $O(n\log n+A)$ time and $O(n)$ space. Presents a data structure for intervals on the line that supports merge and point inclusion in linear time.} \reftop{segment intersection, rectangle intersection, divide-and-conquer, point in rectangle problem, mergeable interval lists, rectangle problems, interval problems.}} \suction{H} \ref [\Hara] {\refauth{Harary, F.} \reftit{Graph Theory {\rm (book)}.} \refpub{Addison-Wesley, 1972, p. 105}} \ref [\Hare] {\refauth{Harel, D.} \reftit{A linear time algorithm for the lowest common ancestors problem.} \refpub{[Date and place unknown] 1980 FOCS?, 308--319}} \ref [\Hart] {\refauth{Hart, J. M.} \reftit{Parmutation inversions and multidimensional cumulative distribution functions.} \refpub{Allerton Conf. Proc. [Date and issue unknown], 29--34}} \ref [\Her] {\refauth{Hermeline, F.} \reftit{Triangulation automatique d'un poly\`edre en dimension $N$.} \refpub{R.A.I.R.O. Analyse Num\'erique Vol. 16 No. 3 (1982) 211--242} \refrem{Triangulation of polyhedrons in $n$ dimensions, using the Delaunay triangulation. Some theoretical discussion. Not clear what he does with polyhedrons that can't be triangulated. Important.}} \ref [\Hig] {\refauth{Highnam, P. T.} \reftit{The ears of a polygon.} \refpub{Information Processing Letters Vol. 15 N. 5 (Dec. 1982), 196--198}} \ref [\Hil] {\refauth{Hilden, J.} \reftit{Testing the relative position of several points on a circle.} \refpub{BIT 12 (1972), 182--187} \refrem{Seems interesting, but not very deep.}} \ref [\HwaI] {\refauth{Hwang, F. K.} \reftit{On steiner minimal trees with rectilinear distance.} \refpub{SIAM J. on Applied Math. Vol. 30 No. 1 (Jan. 1976), 104--114}} \ref [\HwaII] {\refauth{Hwang, F. K.} \reftit{An $O(n \log n)$ algorithm for rectilinear minimal spanning trees.} \refpub{J. of the ACM Vol. 26, 177--182 (1979)} \refrem {L1 Voronoi and MST.}} \suction{I} \ref [\Ins] {\refauth{Inselberg, A.} \reftit{$N$-dimensional graphics: Part I - lines and hyperplanes.} \refpub{Tech. Rep. G320-2711, IBM Los Angeles Scientific Center, Jul. 1981}} \ref [\IyaKaw] {\refauth{Iyanaga, S., and Kawada, Y.} \reftit{Encyclopedic Dictionary of Mathematics {\rm (2nd. ed.)}. } \refpub{MIT Press, Cambridge, Mass., 1968}} \suction{J} \ref [\Jar] {\refauth{Jarvis, R. A.} \reftit{On the identification of the convex hull of a finite set of points in the plane.} \refpub{Information Processing Letters Vol. 2, 18--21 (1973)} \refrem{A classic.}} \ref [\Jaro] {\refauth{Jaromczyk, J. W.} \reftit{Linear decision trees are too weak for convex hull problem.} \refpub{Information Processing Letters Vol. 12, 138--141 (1981)} \refrem{Proves that linear tests don't suffice to compute the convex hull of $n$ points in the plane. [\AvisI] gives a simpler proof.} \reftop{convex hull, lower bounds, linear decision algorithms.}} \ref [\JohPre] {\refauth{Johnson, D. S., and Preparata, F. P.} \reftit{The densest hemisphere problem.} \refpub{Theoretical Comp. Science Vol. 6 (1978), 93--107} \refrem{Find the hemisphere of $S^d$ that contains the maximum number of points out of a given set of $n$ points. Shows that a discretized version of the problem is $NP$-complete of $d$ and $n$ are inputs. Gives also an algorithm that does it in $O(n^{d-1}\log n)$ time. Note: the unit circle for them is $S^2$, not $S^1$.}} \ref [\Jun] {\refauth{Jung, H.} \reftit{Ueber die kleinste Kugel, die eine r\"aumliche Figur einschliesst.} \refpub{[Publication unknown] Reine and Angewandte Mathematik? 1901?, 241--257} \refrem{A classic. Shows that (1) the minimum spanning sphere of $n$ points in $d$ dimensions exists, (2) it is the only ``local minimum'', (3) it is characterized by the property that its center is contained in the convex hull of the points through which it passes, and (4) its radius is at most $\sqrt{d/(2d+2)}$ times the diameter of the point set (an example realizing this bound is also given).} \reftop{minimum spanning circle, convex hull, diameter, higher dimensions.}} \suction{K} \ref [\Kei] {\refauth{Keil, J. M.} \reftit{Decomposing a simple polygon into convex polygons without Steiner points.} \refpub{[Date and place unknown]}} \ref [\KeiKir] {\refauth{Keil, J. M., and Kirkpatrick, D. G.} \reftit{Computational geometry on integer grids.} \refpub{Allerton Conf. Proc [Date and issue unknown], 41--50} \refrem{If coordinates are in the range $[0..m)$, you can do convex hull in $O(n\log\log_n m + n)$ time and other wonders like this.}} \ref [\KimRos] {\refauth{Kim, C. E., and Rosenfeld, A.} \reftit{Digital straightness and convexity.} \refpub{Proc. 13th Annual ACM Symp on Theory of Computing (May 1981), 80--89}} \ref [\KirI] {\refauth{Kirkpatrick, D. G.} \reftit{Efficient computation of continuous skeletons.} \refpub{Proc. 20th Annual IEEE Symp. on Foundations of Computer Science (Oct 1979), 18--27}} \ref [\KirII] {\refauth{Kirkpatrick, D.} \reftit{Optimal search in planar subdivisions.} \refpub{SIAM J. on Computing Vol. 12 No. 1 (Feb. 1983), 28--35. Also as Tech. Rep. 81-13, Dept. of Comp. Science, Univ. of British Columbia, 1981} \refrem{A classic. Practical $O(n)$ storage, $O(n)$ preprocessing, $O(\log n)$ query algorithm for point location in a planar subdivision.} \reftop{point location, point inclusion, convex polyhedra, Voronoi diagram, planar subdivision.}} \ref [\KirIII] {\refauth{Kirkpatrick, D. G.} \reftit{A note on Delaunay and optimal triangulations.} \refpub{Information Processing Letters Vol. 10, 127--128 (1980)} \refrem{Delaunay is even worse than Manacher and Zobrist [\ManaZobI] showed.}} \ref [\KirSei] {\refauth{KirkPatrick, D. G., and Seidel, R.} \reftit{The Ultimate Planar Convex Hull Algorithm?} \refpub{to appear in Proc. 20th Annual Allerton Conf. on Communications, Control and Computing, Oct. 1982}} \ref [\Kle] {\refauth{Klee, V.} \reftit{On the complexity of $d$-dimensional Voronoi diagrams.} \refpub{Archiv der Mathematik Vol. 34 (1980) 75--80} \refrem{Establishes lower and upper asymptotic bounds on the maximum number of $k$-dimensional facets in the $d$-dimensional Voronoi diagram of $n$ points (bounds are exact when $k=d-1$). Superseded by [\SeiI].} \reftop{Voronoi diagram, higher dimensions, convex polyhedra.}} \ref [\Knu] {\refauth{Knuth, D. E.} \reftit{The Art of Computer Programming, {\rm Vol. I:} Fundamental Algorithms {\rm (2nd. ed.).}} \refpub{Addison-Wesley, 1975}} \suction{L} \ref [\LanCar] {\refauth{Lane, J. M., Carpenter, L. C., Whitted, T, and Blinn, J. F.} \reftit{Scan-line methods for displaying parametrically defined surfaces.} \refpub{Comm. ACM Vol. 23 No. 1 (Jan. 1980), 23--34} \refrem{Oddball. Computer graphics} \reftop{miscellaneous.}} \ref [\LeeI] {\refauth{Lee, D. T.} \reftit{On Finding $k$ Nearest Neighbors in the Plane {\rm (M. S. Thesis).}} \refpub{Rep. R-728, Coordinated Science Laboratory, Univ. of Illinois, Urbana, 1976}} \ref [\LeeII] {\refauth{Lee, D. T.} \reftit{Proximity and Reachability in the Plane {\rm (Ph. D. Thesis).}} \refpub{Rep. R-831, Coordinated Science Lab., Univ. of Illinois, Urbana (Nov. 1978)} \refrem{Important. Detailed discussion of Generalized Voronoi algorithms, for general $L_p$ metrics in $O(n\log n)$ time, line segment Voronoi in $O(n\log^2 n)$, Voronoi of a simple polygon in $O(n\log n)$, Voronoi of a set of circles in $O(n\log^2 n)$. Also Generalized Delaunay triangulation (with a given set of ``frozen'' edges) in $O(n\log^2 n)$ time ($O(n\log n)$ if the frozen graph is connected). Mentions Swapping rule, lexicographical ordering, and the InCircle test. Also shortest path between two points with obstacles: $O(n^2\log n)$ for line segments in general position, $O(n^2)$ if a simple polygon, $O(n\log n)$ for parallel line segments.} \reftop{Voronoi diagram, line segment Voronoi, circle Voronoi, Voronoi in $L_1$ and $L_\infty$ metrics, triangulation of a simple polygon, Delaunay triangulation, shortest path with obstacles.}} \ref [\LeeIII] {\refauth{Lee, D. T.} \reftit{Maximum Clique Problem of Rectangle Graphs.} \refpub{[Date and place unknown]}} \ref [\LeeIV] {\refauth{Lee, D. T.} \reftit{On $k$-Nearest Neighbor Voronoi Diagrams in the Plane.} \refpub{IEEE Trans. on Computers, Vol. C-31 BNo. 6 (Jun. 1982), 478--487}} \ref [\LeeV] {\refauth{Lee, D. T.} \reftit{Medial Axis Transformation of a Planar Shape.} \refpub{IEEE Trans. on Pattern Analysis and Machine Intelligence Vol. PAMI-4 No. 4 (Jul. 1982), 363--369}} \ref [\LeeVI] {\refauth{Lee, D. T.} \reftit{Two-dimensional Voronoi diagrams in the $L_p$ Metric} \refpub{J. of the ACM Vol. 27, 604--618 (1980)} \refrem{Good.}} \ref [\LeeDry] {\refauth{Lee, D. T., and Drysdale, R. L., III} \reftit{Generalization of Voronoi diagrams in the plane.} \refpub{SIAM J. on Computing Vol. 10, 73--87 (1981)} \refrem{Voronoi of line segments.}} \ref [\LeePreI] {\refauth{Lee, D. T., and Preparata, F. P.} \reftit{Location of a point in a planar subdivision and its applications.} \refpub{SIAM J. on Computing Vol. 6 No. 3 (Sep. 1977), 594--606} \refpub{Also in Proc. 8th Annual ACM Symp. on Theory of Computing (May 1976), 231--235} \refrem{A classic.} \reftop{point location, monotone polygon, planar subdivision.}} \ref [\LeePreII] {\refauth{Lee, D. T., and Preparata, F. P.} \reftit{An improved algorithm for the rectangle enclosure problem} \refpub{J. Algorithms Vol. 3 (1982), 218--224}} \ref [\LeePreIII] {\refauth{Lee, D. T., and Preparata, F. P.} \reftit{The all nearest-neighbor problem for convex polygons.} \refpub{Information Processing Letters Vol. 7, 189--192 (1978)} \refrem{Important. Computes the nearest neighbor of every vertex of a convex polygon, in linear time. Breaks the polygon into four pieces with the semi-circle property (all vertices lie inside the semicircle defined by one edge). The problem is trivial for such polygons, and merging the solutions is easy.} \reftop{closest-point problems, convex polygons, all-nearest-neighbors problem, semicircle property.}} \ref [\LeeWonI] {\refauth{Lee, D. T., and Wong, C. K.} \reftit{Voronoi diagrams in $L_1$ ($L_\infty$) metrics with 2-dimensional storage applications.} \refpub{IBM Res. Rep. RC 6848 ($\hash$29359), Nov. 1977} \refrem{More Voronoi.}} \ref [\LeeWonII] {\refauth{Lee, D. T., and Wong, C. K.} \reftit{Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees.} \refpub{IBM Res. Rep. RC 6772 ($\hash$29083), Sep. 1977}} \ref [\LeeWonIII] {\refauth{Lee, D. T., and Wong, C. K.} \reftit{Finding intersections of rectangles by range search} \refpub{J. Algorithms Vol. 2 (1981), 337--347} \refrem{Still uses O(n lg n) storage for d = 2.}} \ref [\LeeYan] {\refauth{Lee, D. T., and Yang, C. C.} \reftit{Location of multiple points in a planar subdivision.} \refpub{Information Processing Letters Vol. 9, 190--193 (1979)} \refrem{Trivial.}} \ref [\LeeYReq] {\refauth{Lee, Y. T., and Requicha, A. A. G.} \reftit{Algorithms for computing the volume and other integral properties of solids. I. Known methods and open issues. II. A family of algorithms based on representation conversion and cellular approximation.} \refpub{Comm. ACM Vol. 25, 635--650 (1982)} \refrem{Oddball.}} \ref [\Leeu] {\refauth{Leeuwen, J. van} \reftit{Graphics and computational geometry.} \refpub{To be published in ACR [Date unknown]} \refrem{Mentions several interesting results that should be looked at: (1) Willard's $O(n^{0.77}+A)$ algorithm for arbitrary polygonal queries in the plane; (2) Edelsbrunner, Kirkpatrick, and Maurer's $O(\log n +A)$ with same time but lots of storage and preprocessing; (3) Willard and Lueker's $O(\log^n+A)$ query, $O(\log^2 n)$ update for orthogonal range queries; (4) Overmars and Van Leuuwen's dinamization giving $O(\log n)$ deletion; and (5) Edelsbrunner's $O(\log^3 n+A)$ windowing of rectilinearly oriented rectangles, with $O(\log^3n)$ update.} \reftop{polygonal searching, orthogonal searching, dinamization, range searching, higher dimensions.}} \ref [\LeeuWoo] {\refauth{Leeuwen, J. van, and Wood, D.} \reftit{The measure problem for rectangular ranges in $d$-space.} \refpub{J. Algorithms Vol. 2 (1981), 282--300. Also in manuscript [Date unknown].} \refrem{Does in time $O(n^{(d-1)})$ and quadratic storage for $d > 2$.}} \ref [\Len] {\refauth{Lenstra, H. W.} \reftit{Manuscript lecture notes.} \refpub{Taken by Dolf Talman and communicated by H. Scarf. [Date and place unknown]}} \ref [\LewRob] {\refauth{Lewis, B. A., and Robinson, J. S.} \reftit{Triangulation of planar regions with applications.} \refpub{The Computer Journal Vol. 21 No. 4 (1977? [Date unknown]), 324--332} \refrem{$O(n\log n)$ algorithm for triangulation of a simple polygon witha given set of internal nodes. The basic algorithm is divide-and-conquer: the polygon is broken in two by a polygonal path with vertices on the given nodes, and each part is triangulated separately. After this algorithm finishes, the triangulation is improved by applying an ``heuristic'' which is exactly the Delaunay swapping rule, stated in terms of the minimax angle property!!! Therefore, the result is the Delaunay triangulation of the given polygon and points.\par The splitting step is extremely complex; it is not even clear that it runs in $O(n)$ time. It may improve the convergence of the edge-swapping phase, but it will not affect the result.} \reftop{triangulation, triangulation of a simple polygon, Delaunay diagram, Delaunay of a simple polygon, Delaunay minimax property, divide-and-conquer techniques, planar subdivision.}} \ref [\Lin] {\refauth{Lingas, A.} \reftit{Advances in minimum-weight triangulation.} \refpub{Link\"oping Studies in Science and Technology --- Dissertations, No. 97, Software Systems Research Center, Link\"oping University (Sweden, 1983)} \refrem{Moderately important. Some results on the problem of finding low- or minimum-cost triangulations of a set $P$ of $n$ points on the plane. Contains:\par 1. An $O(n^3)$ algorithm giving an approximation $NT(P)$ to the minimal triangulation $MT(P)$. The algorithm first computes $\hull(P)$, and then a planar forest connecting the points on the hull with all other points of $P$, with the property that the longest edge of the forest is as short as possible. The hull and forest define the boundary of a simple polygon, which can be optimally triangulated by dynamic programming. However, it is not known even if this results in a bettter triangulation than the Delauny $DT(P)$ or greedy triangulation $GT(P)$.\par 2. A statistical analysis of the approximate solutions $NT(P)$, $DT(P)$ and $GT(P)$, when $P$ is uniformly distributed in the unit square. Shows that\par $\Pr[dt(P)/mt(P)\leq O(\alpha\log n)]\geq 1-n^{1-\alpha}$\par $\Pr[gt(P)/mt(P)\leq O(\alpha\log n)]\geq 1-2n^{1-\alpha}$\par $\Pr[nt(P)/mt(P)\leq O(\alpha\log^2 n)]\geq 1-n^{1-\alpha}$\par 3. Shows the NP-completeness of deciding whether a polygonal region with holes has a triangulation with cost not exceeding a given $k$.} \reftop{minimum triangulation, Delaunay diagram, approximate solutions, average-case analysis, triangulation of a simple polygon, NP-completeness.}} \ref [\LipPreI] {\refauth{Lipski, W., and Preparata, F. P.} \reftit{Finding the contour of a union of iso-oriented rectangles.} \refpub{J. of Algorithms Vol. 1 (1980) 235--246} \refrem{Does it in time $O(m \lg m + p \lg (2m^2/p))$, where $m =$ number of rectangles, $p =$ number of edges in the contour.}} \ref [\LipPreII] {\refauth{Lipski, W., Jr., and Preparata, F. P.} \reftit{Segments, rectangles, contours.} \refpub{J. of Algorithms Vol. 2 (1981) 63--76} \refrem{For a collection of n vertical and horizontal line segments, the authors compute several kinds of contours based on a common structure.}} \ref [\LipTar] {\refauth{Lipton, R. J., and Tarjan, R. E.} \reftit{Applications of a planar separator theorem.} \refpub{SIAM J. on Computing Vol. 9, 615--627 (1980)} \refrem{Post office.}} \ref [\Llo] {\refauth{Lloyd, E. L.} \reftit{On triangulations of a set of points in the plane.} \refpub{Proc. 18th Annual IEEE Symp. on Foundations of Computer Science (Nov. 1977), 228--240} \refrem{Neither greedy nor Delaunay give the minimum length triangulation. To decide if a set of segments contains a triangulation is NP-complete.}} \ref [\LozI] {\refauth{Lozano-P\'erez, T.} \reftit{Spatial planning: a configuration space approach.} \refpub{To appear in IEEE Transactions on Computers, February 1983} \refrem{Algorithm for computing the region of admissible positions in the configuration space of polyhedral objects placed with respect to polyhedral obstacles.}} \ref [\LozII] {\refauth{Lozano-P\'erez, T.} \reftit{Automatic planning of manipulator transfer movements.} \refpub{IEEE Transactions on Systems, Man, and Cybernetics Vol SMC-11 No. 10 (October 1981), 681--698} \refrem{Discussion of configuration-space techniques for colision-free movement of polyhedral objects among polyhedral obstacles.}} \ref [\LozWes] {\refauth{Lozano-P\'erez, T., and Wesley, M. A.} \reftit{An algorithm for planning collision free paths among polyhedral obstacles.} \refpub{Comm. ACM Vol. 22, 560--570 (1979)} \refrem{Interesting high-level ideas.}} \ref [\Lue] {\refauth{Lueker, G. S.} \reftit{A data structure for orthogonal range queries.} \refpub{Proc. 20th Annual IEEE Symp. on Foundations of Computer Science (Oct, 1979), 28--34}} \ref [\LueWil] {\refauth{Lueker, G. S., and Willard, D. E.} \reftit{A data structure for dynamic range queries.} \refpub{Information Processing Letters Vol. 15, 209--213}} \suction{M} \ref [\ManaZobI] {\refauth{Manacher, G. K., and Zobrist, A. L.} \reftit{A fast, space-efficient average-case algorithm for the ``greedy'' triangulation of a point set, and a proof that the greedy triangulation is not approximately optimal.} \refpub{Allerton Conf. Proc.? [Date and issue unknown], 824--831} \refrem{Algorithm is $O(n^3)$ {\bf average} time, $O(n)$ space. ``Greedy'' indeed...}} \ref [\ManaZobII] {\refauth{Manacher, G. K., and Zobrist, A. L.} \reftit{Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation.} \refpub{Information Processing Letters Vol. 9, 31--34 (1979)} \refrem{Unbounded ratios.}} \ref [\MantSul] {\refauth{Mantyla, M. J., and Sulonen, R.} \reftit{GWB: a Solid Modeler with Euler Operators.} \refpub{IEEE Comp. Graphics and Applications, Vol. 2 N. 5 (Sep. 1982), 17--31}} \ref [\Mar] {\refauth{Marchetti-Spaccamela, A.} \reftit{The $p$-center problem in the plane is NP-complete.} \refpub{Allerton Conf. Proc. [Date and issue unknown], 31--40} \refrem{And that is it, folks.}} \ref [\MauOtt] {\refauth{Maurer, H., and Ottman, Th.} \reftit{Manipulating sets of points --- a survey.} \refpub{Proc. Workshop WG78 on graph-theoretic concepts in computer science} \refrem{Important. A suvey of data structures and algorithms for storing a set of points in $\reals^d$ so as to answer efficiently many geometrical queries, including various range queries, distance problems, diameter, convex hull, and so forth.\par Somewhat cursory and out-of-data (before Kirkpatrick's point location, for example).} \reftop{orthogonal range queries, polygon queries, closest-point problems, circle queries, incidence problems, separability, convex hull, Voronoi diagram, Delaunay diagram, simple polygons, higher dimensions, minimum spanning tree, decomposable search problems, dynamization techniques.}} \ref [\McCaAvi] {\refauth{McCallum, D., and Avis, D.} \reftit{A linear algorithm for finding the convex hull of a simple polygon.} \refpub{Information Processing Letters Vol. 9, 201--206 (1979)} \refrem{Possibly erroneous.}} \ref [\McCrI] {\refauth{McCreight, E. M.} \reftit{Efficient algorithms for enumerating intersecting intervals and rectangles.} \refpub{Tech. Rep. CSL-80-9, Xerox Palo Alto Res. Centers, 1980} \refrem{Gives a data structure for representing a set of $\leq n$ intervals with integer coordinates $\leq k$ such that we can (1) insert and delete an interval in $O(\log \max\set{n, k})$ time, and (2) list all intervals containing an integer $u$ (or intersecting a query interval $i$) in time $O(\log \max\set{n, k}+A)$ time, both using $O(n)$ space. Can be used to report rectangle intersections in $O(n\log n+A)$ time. Superseded by priority search trees?} \reftop{range search in one dimension, rectangle problems, sweeping line technique, interval problems.}} \ref [\McCrII] {\refauth{McCreight, E. M.} \reftit{Priority search trees.} \refpub{Tech. Rep. CSL-81-5, Xerox Palo Alto Res. Centers, Dec. 1981. Also SIAM J. on Computing [Date unknown]}} \ref [\McLa] {\refauth{McLain, D. H.} \reftit{Two dimensional interpolation from random data.} \refpub{The Computer Journal Vol. 19 No. 2 (1976), 178--181} \refrem{Application of Delaunay triangulation to two-dimensional data fitting. Gives an incremental algorithm for computing the Delaunay, based on the InCircle idea, attributed to Pitteway. At each step, we consider one edge $pq$ on the boundary of the region already triangulated, and find the vertex $r$ for which the circumcenter of $pqr$ is closest to $pq$. Then add the triangle $pqr$ and repeat.\par States (wrongly) that for any point $x$ in a Delaunay triangle, the closest site to $x$ is a vertex of the triangle.\par Gives ALGOL algorithms for computing a line passing through two points and the diastance from a point to that line.} \reftop{Delaunay triangulation, incremental algorithms, geometric primitives.}} \ref [\MegI] {\refauth{Megiddo, N.} \reftit{Linear-time algorithms for linear programming in $R^3$ and related problems.} \refpub{Proc. 23rd Annual IEEE Symp. on Foundations of Computer Science (Nov. 1982), 329--338} \refrem{A classic. General technique for solving in $O(n)$ time several problems related/similar to linear programming in two and three variables. The basic idea is to divide the $n$ constraints of the problem into a few groups of equal size, and then perform an $O(n)$ test that allows one of the groups to be eliminated. To defne the groups, uses random pairing and linear-time median computation. The total time then is a geometric prograssion that converges to $O(n)$.\par Considers also the problem of finding the weighted center of a tree, the minimum spanning circle of $n$ points, and quadratic programming in three variables. Also gives an algorithm for testing in $O(n)$ time whether a point is inside the convex hull of $n$ others (nothing fancy). Seems to be restricted to problems where there are only $O(n)$ ``candidate'' answers.\par By dualization, LP in two varaibles gives an algorithm for finding the intersection of a line with the hull of $n$ given points, i.e. the common tangent of two linearly separated sets of points (this is a step in Kirkpatrick's ``ultimate'' convex huller). The same holds for $\reals^3$, a non-trivial result. Can ve use it for an ``ultimate'' convex huller in 3D?} \reftop{linear pogramming, convex hull, minimum spanning circle, weighted center of a tree, higher dimensions, common tangent.}} \ref [\MegII] {\refauth{Megiddo, N.} \reftit{Solving linear programming in linear-time when the dimension is fixed.} \refpub{[Publication unknown] Statistics Department, Tel Aviv Univ. (Israel), April 1982.}} \ref [\MilI] {\refauth{Miller, G. L.} \reftit{An additivity theorem for the genus of a graph.} \refpub{Manuscript, Department of Mthematics, Massachusetts Institute of Technology [Date unknown, about 1982].}} \ref [\MilII] {\refauth{Miller, G. L.} \reftit{Isomorphism testing for graphs of bounded genus.} \refpub{Proc. 12th Annual ACM Symposyum on Theory of Computing (April 1980), 225--235.}} \ref [\MulPre] {\refauth{Muller, D. E., and Preparata, F. P.} \reftit{Finding the intersection of two convex polyhedra.} \refpub{Theoretical Comp. Science Vol. 7 (1978), 217--236} \refrem{Uses dualization.}} \ref [\Mun] {\refauth{Munro, J. I.} \reftit{A multikey search problem.} \refpub{Allerton Conf. Proc [Date and issue unknown], 241--244}} \suction{N} \ref [\NevErn] {\refauth{Nevalainen, O., Ernvall, J., and Katajainen, J.} \reftit{Finding minimal spanning trees in an Euclidean coordinate space.} \refpub{BIT 21 (1981), 46--54} \refrem{In $d$ dimensions. The algorithm is supposedly ``good in practice'' for normally distributed data points. Expected time is $\Omega(n\log n)$, propably more. Worst case is at least $\Omega(n^2)$. Some empirical analysis. The algorithm is a modification of Bentley and Friedman's multifragment MST algorithm, using $k$-$d$ trees to help locate closest points. Contains a brief survey of MST algorithms.} \reftop{minimum spanning tree, $k$-$d$ trees, closest-point problems, average-case analysis, higher dimansions.}} \ref [\NiePre] {\refauth{Nievergelt, J., and Preparata, F. P.} \reftit{Plane-sweep algorithms for intersecting geometric figures.} \refpub{Comm. ACM Vol. 25, 739--747 (1982)} \refrem{Good, we can do better.}} \ref [\NorRys] {\refauth{Nordbeck, S., and Rystedt, B.} \reftit{Computer cartography point-in-polygon programs.} \refpub{BIT 7 (1967), 39--64} \refrem{Pre-historical. Point inclusion in convex and star-shaped polygons?.}}