Separating and shattering long line segments

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 ail 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(n(2) log n) time algorithm of Freimer, Mitchell and Piatko. (C) 1997 Published by Elsevier Science B.V.
Publisher
ELSEVIER SCIENCE BV
Issue Date
1997-12
Language
ENG
Keywords

COMPUTATIONAL GEOMETRY

Citation

INFORMATION PROCESSING LETTERS, v.64, no.6, pp.309 - 314

ISSN
0020-0190
DOI
10.1016/S0020-0190(97)00188-9
URI
http://hdl.handle.net/10203/324
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
es-sslls-97.pdf(186.4 kB)Download
  • Hit : 430
  • Download : 345
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 2 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0