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. The general case is an 'n2-hard' problem, in the sense defined in [10] (see also [8]). Our algorithm is based on the recent results of [15], concerning the union of 'fat' triangles, but we also include an analysis which improves the bounds obtained in [15].
Original language | English (US) |
---|---|
Pages (from-to) | 277-288 |
Number of pages | 12 |
Journal | Computational Geometry: Theory and Applications |
Volume | 3 |
Issue number | 5 |
DOIs | |
State | Published - Nov 1993 |
Externally published | Yes |
ASJC Scopus subject areas
- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics