A Low Arithmetic-Degree Algorithm for Computing Proximity Graphs
| Autor: | Fabrizio d'Amore, Paolo Giulio Franciosa |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Spanning tree
Degree (graph theory) Applied Mathematics Relative neighborhood graph robust computation geometric graphs euclidean minimum spanning tree arithmetic degree 0102 computer and information sciences 02 engineering and technology Minimum spanning tree 01 natural sciences Theoretical Computer Science Euclidean distance Computational Mathematics Asymptotically optimal algorithm Computational Theory and Mathematics Nearest neighbor graph 010201 computation theory & mathematics Euclidean minimum spanning tree 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Geometry and Topology Arithmetic Algorithm Mathematics |
| Zdroj: | International Journal of Computational Geometry & Applications. 28:227-253 |
| ISSN: | 1793-6357 0218-1959 |
| DOI: | 10.1142/s021819591850005x |
| Popis: | In this paper, we study the problem of designing robust algorithms for computing the minimum spanning tree, the nearest neighbor graph, and the relative neighborhood graph of a set of points in the plane, under the Euclidean metric. We use the term “robust” to denote an algorithm that can properly handle degenerate configurations of the input (such as co-circularities and collinearities) and that is not affected by errors in the flow of control due to round-off approximations. Existing asymptotically optimal algorithms that compute such graphs are either suboptimal in terms of the arithmetic precision required for the implementation, or cannot handle degeneracies, or are based on complex data structures. We present a unified approach to the robust computation of the above graphs. The approach is a variant of the general region approach for the computation of proximity graphs based on Yao graphs, first introduced in Ref. 43 (A. C.-C. Yao, On constructing minimum spanning trees in [Formula: see text]-dimensional spaces and related problems, SIAM J. Comput. 11(4) (1982) 721–736). We show that a sparse supergraph of these geometric graphs can be computed in asymptotically optimal time and space, and requiring only double precision arithmetic, which is proved to be optimal. The arithmetic complexity of the approach is measured by using the notion of degree, introduced in Ref. 31 (G. Liotta, F. P. Preparata and R. Tamassia, Robust proximity queries: An illustration of degree-driven algorithm design, SIAM J. Comput. 28(3) (1998) 864–889) and Ref. 3 (J. D. Boissonnat and F. P. Preparata, Robust plane sweep for intersecting segments, SIAM J. Comput. 29(5) (2000) 1401–1421). As a side effect of our results, we solve a question left open by Katajainen27 (J. Katajainen, The region approach for computing relative neighborhood graphs in the [Formula: see text] metric, Computing 40 (1987) 147–161) about the existence of a subquadratic algorithm, based on the region approach, that computes the relative neighborhood graph of a set of points [Formula: see text] in the plane under the [Formula: see text] metric. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|