Separating and shattering long line segments

Alon Efrat, Otfried Schwarzkopf

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A line I is called a separator for a set S of objects in the plane if I avoids all the objects and partitions S into two non-empty subsets, lying on both sides of l. A set L of lines is said to shatter S if each line of L is a separator for S, and every two objects of S are separated by at least one line of L. We give a simple algorithm to construct the set of all separators for a given set S of n line segments in time O(n log n), provided the ratio between the diameter of S and the length of the shortest line segment is bounded by a constant. We also give an O(n log n)-time algorithm to determine a set of lines shattering S, improving (for this setting) the O(n2 log n) time algorithm of Freimer, Mitchell and Piatko.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings
EditorsTetsuo Asano, Yoshihide Igarashi, Hiroshi Nagamochi, Satoru Miyano, Subhash Suri
Number of pages9
ISBN (Print)3540620486, 9783540620488
StatePublished - 1996
Event7th International Symposium on Algorithms and Computation, ISAAC 1996 - Osaka, Japan
Duration: Dec 16 1996Dec 18 1996

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other7th International Symposium on Algorithms and Computation, ISAAC 1996


  • BSP-trees
  • Computational geometry
  • Line-separation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Separating and shattering long line segments'. Together they form a unique fingerprint.

Cite this