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

Alon Efrat, Günter Rote, Micha Sharir

Research output: Contribution to journalArticlepeer-review

44 Scopus citations

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 languageEnglish (US)
Pages (from-to)277-288
Number of pages12
JournalComputational Geometry: Theory and Applications
Volume3
Issue number5
DOIs
StatePublished - Nov 1993
Externally publishedYes

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'On the union of fat wedges and separating a collection of segments by a line'. Together they form a unique fingerprint.

Cite this