@article{4048,
  abstract     = {Given a sequence of n points that form the vertices of a simple polygon, we show that determining a closest pair requires OMEGA(n log n) time in the algebraic decision tree model. Together with the well-known O(n log n) upper bound for finding a closest pair, this settles an open problem of Lee and Preparata. We also extend this O(n log n) upper bound to the following problem: Given a collection of sets with a total of n points in the plane, find for each point a closest neighbor that does not belong to the same set.},
  author       = {Aggarwal, Alok and Edelsbrunner, Herbert and Raghavan, Prabhakar and Tiwari, Prasoon},
  issn         = {1872-6119},
  journal      = {Information Processing Letters},
  number       = {1},
  pages        = {55 -- 60},
  publisher    = {Elsevier},
  title        = {{Optimal time bounds for some proximity problems in the plane}},
  doi          = {10.1016/0020-0190(92)90133-G},
  volume       = {42},
  year         = {1992},
}

@article{4094,
  abstract     = {The visibility graph of a finite set of line segments in the plane connects two endpoints u and v if and only if the straight line connection between u and v does not cross any line segment of the set. This article proves that 5n - 4 is a lower bound on the number of edges in the visibility graph of n nonintersecting line segments in the plane. This bound is tight.},
  author       = {Edelsbrunner, Herbert and Shen, Xiaojun},
  issn         = {1872-6119},
  journal      = {Information Processing Letters},
  number       = {2},
  pages        = {61 -- 64},
  publisher    = {Elsevier},
  title        = {{A tight lower bound on the size of visibility graphs}},
  doi          = {10.1016/0020-0190(87)90038-X},
  volume       = {26},
  year         = {1987},
}

@article{4101,
  abstract     = {In a number of recent papers, techniques from computational geometry (the field of algorithm design that deals with objects in multi-dimensional space) have been applied to some problems in the area of computer graphics. In this way, efficient solutions were obtained for the windowing problem that asks for those line segments in a planar set that lie in given window (range) and the moving problem that asks for the first line segment that comes into the window when moving the window in some direction. In this paper we show that also the zooming problem, which asks for the first line segment that comes into the window when we enlarge it, can be solved efficiently. This is done by repeatedly performing range queries with ranges of varying sizes. The obtained structure is dynamic and yields a query time of O(log2n) and an insertion and deletion time of O(log2n), where n is the number of line segments in the set. The amount of storage required is O(n log n). It is also shown that the technique of repeated range search can be used to solve several other problems efficiently.},
  author       = {Edelsbrunner, Herbert and Overmars, Mark},
  issn         = {1872-6119},
  journal      = {Information Processing Letters},
  number       = {6},
  pages        = {413 -- 417},
  publisher    = {Elsevier},
  title        = {{Zooming by repeated range detection}},
  doi          = {10.1016/0020-0190(87)90120-7},
  volume       = {24},
  year         = {1987},
}

@article{4099,
  abstract     = {Let S denote a set of n points in the Euclidean plane. A halfplanar range query specifies a halfplane h and requires the determination of the number of points in S which are contained in h. A new data structure is described which stores S in O(n) space and allows us to answer a halfplanar range query in O(nlog2(1+√5)−1) time in the worst case, thus improving the best result known before. The structure can be built in O(n log n) time.},
  author       = {Edelsbrunner, Herbert and Welzl, Emo},
  issn         = {1872-6119},
  journal      = {Information Processing Letters},
  number       = {5},
  pages        = {289 -- 293},
  publisher    = {Elsevier},
  title        = {{Halfplanar range search in linear space and O(n0.695) query time}},
  doi          = {10.1016/0020-0190(86)90088-8},
  volume       = {23},
  year         = {1986},
}

@article{4111,
  abstract     = {This paper describes an optimal solution for the following geometric search problem defined for a set P of n points in three dimensions: Given a plane h with all points of P on one side and a line ℓ in h, determine a point of P that is hit first when h is rotated around ℓ. The solution takes O(n) space and O(log n) time for a query. By use of geometric transforms, the post-office problem for a finite set of points in two dimensions and certain two-dimensional point location problems are reduced to the former problem and thus also optimally solved.},
  author       = {Edelsbrunner, Herbert and Maurer, Hermann},
  issn         = {1872-6119},
  journal      = {Information Processing Letters},
  number       = {1},
  pages        = {39 -- 47},
  publisher    = {Elsevier},
  title        = {{Finding extreme-points in 3-dimensions and solving the post-office problem in the plane}},
  doi          = {10.1016/0020-0190(85)90107-3},
  volume       = {21},
  year         = {1985},
}

@article{4130,
  author       = {Edelsbrunner, Herbert and Maurer, Hermann and Kirkpatrick, David},
  issn         = {1872-6119},
  journal      = {Information Processing Letters},
  number       = {2},
  pages        = {74 -- 79},
  publisher    = {Elsevier},
  title        = {{Polygonal intersection searching}},
  doi          = {10.1016/0020-0190(82)90090-4},
  volume       = {14},
  year         = {1982},
}

@article{4131,
  author       = {Edelsbrunner, Herbert and Overmars, Mark},
  issn         = {1872-6119},
  journal      = {Information Processing Letters},
  number       = {3},
  pages        = {124 -- 127},
  publisher    = {Elsevier},
  title        = {{On the equivalence of some rectangle problems}},
  doi          = {10.1016/0020-0190(82)90068-0},
  volume       = {14},
  year         = {1982},
}