@article{4088,
  abstract     = {Anarrangement ofn lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists ofO(n 2) regions, calledfaces. In this paper we study the problem of calculating and storing arrangementsimplicitly, using subquadratic space and preprocessing, so that, given any query pointp, we can calculate efficiently the face containingp. First, we consider the case of lines and show that with (n) space1 and (n 3/2) preprocessing time, we can answer face queries in (n)+O(K) time, whereK is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: (1) given a set ofn points, find a straight-edge spanning tree of these points such that any line intersects only a few edges of the tree, (2) given a simple polygonal path , form a data structure from which we can find the convex hull of any subpath of quickly, and (3) given a set of points, organize them so that the convex hull of their subset lying above a query line can be found quickly. Second, using random sampling, we give a tradeoff between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in (n 1/3)+O(K) time, given(n 4/3) space and (n 5/3) preprocessing time. Lastly, we note that our techniques allow us to computem faces in an arrangement ofn lines in time (m 2/3 n 2/3+n), which is nearly optimal.},
  author       = {Edelsbrunner, Herbert and Guibas, Leonidas and Hershberger, John and Seidel, Raimund and Sharir, Micha and Snoeyink, Jack and Welzl, Emo},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {433 -- 466},
  publisher    = {Springer},
  title        = {{Implicitly representing arrangements of lines or segments}},
  doi          = {10.1007/BF02187742},
  volume       = {4},
  year         = {1989},
}

@article{4089,
  abstract     = {Motivated by a number of motion-planning questions, we investigate in this paper some general topological and combinatorial properties of the boundary of the union ofn regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected surface can be constructed that exactly covers this union and whose boundary has combinatorial complexity that is nearly linear, even though the covered region can have quadratic complexity. In the case where our regions are delimited by Jordan acrs in the upper halfplane starting and ending on thex-axis such that any pair of arcs intersect in at most three points, we prove that the total number of subarcs that appear on the boundary of the union is only (n(n)), where(n) is the extremely slowly growing functional inverse of Ackermann's function.},
  author       = {Edelsbrunner, Herbert and Guibas, Leonidas and Hershberger, John and Pach, János and Pollack, Richard and Seidel, Raimund and Sharir, Micha and Snoeyink, Jack},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {523 -- 539},
  publisher    = {Springer},
  title        = {{On arrangements of Jordan arcs with three intersections per pair}},
  doi          = {10.1007/BF02187745},
  volume       = {4},
  year         = {1989},
}

@article{4093,
  abstract     = {This paper investigates the combinatorial and computational aspects of certain extremal geometric problems in two and three dimensions. Specifically, we examine the problem of intersecting a convex subdivision with a line in order to maximize the number of intersections. A similar problem is to maximize the number of intersected facets in a cross-section of a three-dimensional convex polytope. Related problems concern maximum chains in certain families of posets defined over the regions of a convex subdivision. In most cases we are able to prove sharp bounds on the asymptotic behavior of the corresponding extremal functions. We also describe polynomial algorithms for all the problems discussed.},
  author       = {Chazelle, Bernard and Edelsbrunner, Herbert and Guibas, Leonidas},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {139 -- 181},
  publisher    = {Springer},
  title        = {{The complexity of cutting complexes}},
  doi          = {10.1007/BF02187720},
  volume       = {4},
  year         = {1989},
}

@article{4100,
  abstract     = {This paper investigates the existence of linear space data structures for range searching. We examine thehomothetic range search problem, where a setS ofn points in the plane is to be preprocessed so that for any triangleT with sides parallel to three fixed directions the points ofS that lie inT can be computed efficiently. We also look atdomination searching in three dimensions. In this problem,S is a set ofn points inE 3 and the question is to retrieve all points ofS that are dominated by some query point. We describe linear space data structures for both problems. The query time is optimal in the first case and nearly optimal in the second.
},
  author       = {Chazelle, Bernard and Edelsbrunner, Herbert},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {113 -- 126},
  publisher    = {Springer},
  title        = {{Linear space data structures for two types of range search}},
  doi          = {10.1007/BF02187875},
  volume       = {2},
  year         = {1987},
}

@article{4108,
  abstract     = {We propose a uniform and general framework for defining and dealing with Voronoi diagrams. In this framework a Voronoi diagram is a partition of a domainD induced by a finite number of real valued functions onD. Valuable insight can be gained when one considers how these real valued functions partitionD ×R. With this view it turns out that the standard Euclidean Voronoi diagram of point sets inR d along with its order-k generalizations are intimately related to certain arrangements of hyperplanes. This fact can be used to obtain new Voronoi diagram algorithms. We also discuss how the formalism of arrangements can be used to solve certain intersection and union problems.},
  author       = {Edelsbrunner, Herbert and Seidel, Raimund},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {25 -- 44},
  publisher    = {Springer},
  title        = {{Voronoi diagrams and arrangements}},
  doi          = {10.1007/BF02187681},
  volume       = {1},
  year         = {1986},
}