DC Field | Value | Language |
---|---|---|
dc.contributor.author | Asano, T | ko |
dc.contributor.author | de Berg, M | ko |
dc.contributor.author | Cheong, Otfried | ko |
dc.contributor.author | Guibas, LJ | ko |
dc.contributor.author | Snoeyink, J | ko |
dc.contributor.author | Tamaki, H | ko |
dc.date.accessioned | 2007-05-23T09:43:07Z | - |
dc.date.available | 2007-05-23T09:43:07Z | - |
dc.date.created | 2012-02-06 | - |
dc.date.created | 2012-02-06 | - |
dc.date.issued | 2003-12 | - |
dc.identifier.citation | DISCRETE COMPUTATIONAL GEOMETRY, v.30, no.4, pp.591 - 606 | - |
dc.identifier.issn | 0179-5376 | - |
dc.identifier.uri | http://hdl.handle.net/10203/307 | - |
dc.description.abstract | 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. | - |
dc.description.sponsorship | Grant in Aid for Scientific Research of the Ministry of Education, Science and Cultures of Japan, NSF grants 9988742 and 0076984, National Science and Engineering Research Council of Canada | en |
dc.language | English | - |
dc.language.iso | en | en |
dc.publisher | SPRINGER-VERLAG | - |
dc.subject | BINARY SPACE PARTITIONS | - |
dc.title | Spanning trees crossing few barriers | - |
dc.type | Article | - |
dc.identifier.wosid | 000186370900005 | - |
dc.identifier.scopusid | 2-s2.0-0346753520 | - |
dc.type.rims | ART | - |
dc.citation.volume | 30 | - |
dc.citation.issue | 4 | - |
dc.citation.beginningpage | 591 | - |
dc.citation.endingpage | 606 | - |
dc.citation.publicationname | DISCRETE COMPUTATIONAL GEOMETRY | - |
dc.identifier.doi | 10.1007/s00454-003-2853-5 | - |
dc.embargo.liftdate | 9999-12-31 | - |
dc.embargo.terms | 9999-12-31 | - |
dc.contributor.localauthor | Cheong, Otfried | - |
dc.contributor.nonIdAuthor | Asano, T | - |
dc.contributor.nonIdAuthor | de Berg, M | - |
dc.contributor.nonIdAuthor | Guibas, LJ | - |
dc.contributor.nonIdAuthor | Snoeyink, J | - |
dc.contributor.nonIdAuthor | Tamaki, H | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordPlus | BINARY SPACE PARTITIONS | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.