Spanning trees crossing few barriers

We consider the problem of finding low-cost spanning trees for sets of n points in the plane, where the cost of a spanning tree is defined as the total number of intersections of tree edges with a given set of m barriers. We obtain the following results: (i) if the barriers are possibly intersecting line segments, then there is always a spanning tree of cost O(min(m(2), mrootn)) (ii) if the barriers are disjoint line segments, then there is always a spanning tree of cost 0(m); (iii) if the barriers are disjoint convex objects, then there is always a spanning tree of cost 0 (n + m). All our bounds are worst-c se optimal, up to multiplicative constants.
Publisher
SPRINGER-VERLAG
Issue Date
2003-12
Language
ENG
Keywords

BINARY SPACE PARTITIONS

Citation

DISCRETE COMPUTATIONAL GEOMETRY, v.30, no.4, pp.591 - 606

ISSN
0179-5376
DOI
10.1007/s00454-003-2853-5
URI
http://hdl.handle.net/10203/307
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
2002-012.pdf(208.43 kB)Download
  • Hit : 557
  • Download : 289
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 7 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0