We present 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 L 2 metric. Our algorithms are asymptotically optimal, and use only double precision arithmetic. As a side effect of our results, we solve a question left open by Katajainen [11] about the computation of relative neighborhood graphs.
A Robust Region Approach to the Computation of Geometric Graphs / D'Amore, Fabrizio; Franciosa, Paolo Giulio; G., Liotta. - STAMPA. - 1461:(1998), pp. 320-333. (Intervento presentato al convegno Algorithms - {ESA} '98, 6th Annual European Symposium tenutosi a Venice; Italy nel 24--26 August 1998) [10.1007/3-540-68530-8_15].
A Robust Region Approach to the Computation of Geometric Graphs
D'AMORE, Fabrizio
Co-primo
Membro del Collaboration Group
;FRANCIOSA, Paolo GiulioCo-primo
Membro del Collaboration Group
;
1998
Abstract
We present 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 L 2 metric. Our algorithms are asymptotically optimal, and use only double precision arithmetic. As a side effect of our results, we solve a question left open by Katajainen [11] about the computation of relative neighborhood graphs.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
