Alon Efrat, Günter Rote, and Micha Sharir:

On the union of fat wedges and separating a collection of segments by a line

  1. In: Proceedings of the Fifth Canadian Conference on Computational Geometry, Waterloo, August 5–9, 1993. Editor: A. Lubiw, J. Urrutia; pp. 115–120.  →BibTeX
  2. Computational Geometry: Theory and Applications 3 (1993), 277–288, (Zbl 801.68167). doi:10.1016/0925-7721(93)90018-2  →BibTeX


We call a line l a separator for a set S of objects in the plane if l avoids all the objects and partitions S into two nonempty subsets, one consisting of objects lying above l and the other of objects lying below l. In this paper we present an O(n log n)-time algorithm for finding a separator line for a set of n segments, provided the ratio between the diameter of the set of segments and the length of the smallest segment is bounded. No subquadratic algorithms are known for the general case. Our algorithm is based on the recent results of Matousek, Pach, Sharir, Sifrony, and Welzl (1994) concerning the union of “fat” triangles, but we also include an analysis which improves the bounds obtained by Matoušek, Pach, Sharir, Sifrony and Welzl.

other papers about this subject
Last update: August 16, 2004.