Alon Efrat, Günter Rote, and Micha Sharir:
On the union of fat wedges and separating a collection of segments by a
line

In: Proceedings of the Fifth Canadian Conference on Computational Geometry,
Waterloo, August 5–9, 1993. Editor: A. Lubiw, J. Urrutia;
pp. 115–120.
→BibTeX

Computational Geometry: Theory and Applications 3
(1993), 277–288, (Zbl 801.68167). doi:10.1016/09257721(93)900182 →BibTeX
Abstract
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.
Last update: August 16, 2004.