@inproceedings{f14b85df8b2f4f31a5b0bf598c690a05,
title = "Separating and shattering long line segments",
abstract = "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.",
keywords = "BSP-trees, Computational geometry, Line-separation",
author = "Alon Efrat and Otfried Schwarzkopf",
note = "Funding Information: * Corresponding author. Email:
[email protected]. {\textquoteright} Work on this paper by the second author has been supported by the Netherlands{\textquoteright} Organization for Scientific Research (NWO), by Pohang University of Science and Technology Grant 96POO4, 1996, and partially by the nondirected research fund of the Korean Ministry of Education. * Email:
[email protected]. Publisher Copyright: {\textcopyright} 1996 Springer-Verlag. All rights reserved.; 7th International Symposium on Algorithms and Computation, ISAAC 1996 ; Conference date: 16-12-1996 Through 18-12-1996",
year = "1996",
doi = "10.1007/bfb0009479",
language = "English (US)",
isbn = "3540620486",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "36--44",
editor = "Tetsuo Asano and Yoshihide Igarashi and Hiroshi Nagamochi and Satoru Miyano and Subhash Suri",
booktitle = "Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings",
}