TY - JOUR
T1 - Separating and shattering long line segments
AU - Efrat, Alon
AU - Schwarzkopf, Otfried
N1 - Funding Information:
* Corresponding author. Email: [email protected]. ’ Work on this paper by the second author has been supported by the Netherlands’ 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].
PY - 1997/12/29
Y1 - 1997/12/29
N2 - A line l is called a separator for a set S of objects in the plane if l 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 randomized algorithm to construct the set of all separators for a given set S of n line segments in expected 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 a randomized algorithm to determine a set of lines shattering S, whose expected running time is O(n log n), improving (for this setting) the (deterministic) O(n2 log n) time algorithm of Freimer, Mitchell and Piatko.
AB - A line l is called a separator for a set S of objects in the plane if l 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 randomized algorithm to construct the set of all separators for a given set S of n line segments in expected 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 a randomized algorithm to determine a set of lines shattering S, whose expected running time is O(n log n), improving (for this setting) the (deterministic) O(n2 log n) time algorithm of Freimer, Mitchell and Piatko.
KW - BSP-trees
KW - Computational geometry
KW - Line separation
UR - http://www.scopus.com/inward/record.url?scp=0042634021&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0042634021&partnerID=8YFLogxK
U2 - 10.1016/s0020-0190(97)00188-9
DO - 10.1016/s0020-0190(97)00188-9
M3 - Article
AN - SCOPUS:0042634021
SN - 0020-0190
VL - 64
SP - 309
EP - 314
JO - Information Processing Letters
JF - Information Processing Letters
IS - 6
ER -