DC Field | Value | Language |
---|---|---|
dc.contributor.author | AGARWAL, PK | ko |
dc.contributor.author | EDELSBRUNNER, H | ko |
dc.contributor.author | Cheong, Otfried | ko |
dc.contributor.author | WELZL, E | ko |
dc.date.accessioned | 2013-02-27T06:11:10Z | - |
dc.date.available | 2013-02-27T06:11:10Z | - |
dc.date.created | 2012-02-06 | - |
dc.date.created | 2012-02-06 | - |
dc.date.issued | 1991 | - |
dc.identifier.citation | DISCRETE COMPUTATIONAL GEOMETRY, v.6, no.5, pp.407 - 422 | - |
dc.identifier.issn | 0179-5376 | - |
dc.identifier.uri | http://hdl.handle.net/10203/66905 | - |
dc.description.abstract | We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of N points in E(d) in time O(T(d)(N, N) log(d) N), where T(d)(n, m) is the time required to compute a bichromatic closest pair among n red and m green points in E(d). If T(d)(N, N) = OMEGA-(N 1 + epsilon), for some fixed epsilon > 0, then the running time improves to O(T(d)(N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected time O(nm log n log m)2/3 + m log2 n + n log2 m) in E3, which yields an O(N4/3 log4/3 N) expected time algorithm for computing a Euclidean minimum spanning tree of N points in E3. In d greater-than-or-equal-to 4 dimensions we obtain expected time O(nm)1-1/([d/2] + 1) + epsilon + m log n + n log m) for the bichromatic closest pair problem and O(N2-2/([d/2] + 1) + epsilon) for the Euclidean minimum spanning tree problem, for any positive epsilon. | - |
dc.language | English | - |
dc.publisher | SPRINGER VERLAG | - |
dc.subject | POINT LOCATION | - |
dc.subject | SEARCH | - |
dc.title | EUCLIDEAN MINIMUM SPANNING-TREES AND BICHROMATIC CLOSEST PAIRS | - |
dc.type | Article | - |
dc.identifier.wosid | A1991GG29700003 | - |
dc.identifier.scopusid | 2-s2.0-51249179376 | - |
dc.type.rims | ART | - |
dc.citation.volume | 6 | - |
dc.citation.issue | 5 | - |
dc.citation.beginningpage | 407 | - |
dc.citation.endingpage | 422 | - |
dc.citation.publicationname | DISCRETE COMPUTATIONAL GEOMETRY | - |
dc.identifier.doi | 10.1007/BF02574698 | - |
dc.contributor.localauthor | Cheong, Otfried | - |
dc.contributor.nonIdAuthor | AGARWAL, PK | - |
dc.contributor.nonIdAuthor | EDELSBRUNNER, H | - |
dc.contributor.nonIdAuthor | WELZL, E | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordPlus | POINT LOCATION | - |
dc.subject.keywordPlus | SEARCH | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.