Separating and shattering long line segments

Alon Efrat; Otfried Schwarzkopf

doi:10.1007/bfb0009479

Separating and shattering long line segments

Alon Efrat, Otfried Schwarzkopf

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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(n² log n) time algorithm of Freimer, Mitchell and Piatko.

Original language	English (US)
Title of host publication	Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings
Editors	Tetsuo Asano, Yoshihide Igarashi, Hiroshi Nagamochi, Satoru Miyano, Subhash Suri
Publisher	Springer-Verlag
Pages	36-44
Number of pages	9
ISBN (Print)	3540620486, 9783540620488
DOIs	https://doi.org/10.1007/bfb0009479
State	Published - 1996
Event	7th International Symposium on Algorithms and Computation, ISAAC 1996 - Osaka, Japan Duration: Dec 16 1996 → Dec 18 1996

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1178

Other

Other	7th International Symposium on Algorithms and Computation, ISAAC 1996
Country/Territory	Japan
City	Osaka
Period	12/16/96 → 12/18/96

Keywords

BSP-trees
Computational geometry
Line-separation

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/bfb0009479

Cite this

Efrat, A., & Schwarzkopf, O. (1996). Separating and shattering long line segments. In T. Asano, Y. Igarashi, H. Nagamochi, S. Miyano, & S. Suri (Eds.), Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings (pp. 36-44). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1178). Springer-Verlag. https://doi.org/10.1007/bfb0009479

Separating and shattering long line segments. / Efrat, Alon; Schwarzkopf, Otfried.
Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings. ed. / Tetsuo Asano; Yoshihide Igarashi; Hiroshi Nagamochi; Satoru Miyano; Subhash Suri. Springer-Verlag, 1996. p. 36-44 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1178).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Efrat, A & Schwarzkopf, O 1996, Separating and shattering long line segments. in T Asano, Y Igarashi, H Nagamochi, S Miyano & S Suri (eds), Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1178, Springer-Verlag, pp. 36-44, 7th International Symposium on Algorithms and Computation, ISAAC 1996, Osaka, Japan, 12/16/96. https://doi.org/10.1007/bfb0009479

Efrat A, Schwarzkopf O. Separating and shattering long line segments. In Asano T, Igarashi Y, Nagamochi H, Miyano S, Suri S, editors, Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings. Springer-Verlag. 1996. p. 36-44. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0009479

Efrat, Alon ; Schwarzkopf, Otfried. / Separating and shattering long line segments. Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings. editor / Tetsuo Asano ; Yoshihide Igarashi ; Hiroshi Nagamochi ; Satoru Miyano ; Subhash Suri. Springer-Verlag, 1996. pp. 36-44 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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",

}

TY - GEN

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]. Publisher Copyright: © 1996 Springer-Verlag. All rights reserved.

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

KW - BSP-trees

KW - Computational geometry

KW - Line-separation

UR - http://www.scopus.com/inward/record.url?scp=84990231580&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84990231580&partnerID=8YFLogxK

U2 - 10.1007/bfb0009479

DO - 10.1007/bfb0009479

M3 - Conference contribution

SN - 3540620486

SN - 9783540620488

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 36

EP - 44

BT - Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings

A2 - Asano, Tetsuo

A2 - Igarashi, Yoshihide

A2 - Nagamochi, Hiroshi

A2 - Miyano, Satoru

A2 - Suri, Subhash

PB - Springer-Verlag

T2 - 7th International Symposium on Algorithms and Computation, ISAAC 1996

Y2 - 16 December 1996 through 18 December 1996

ER -

Separating and shattering long line segments

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this