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 about the computation of relative neighborhood graphs.
Robust Region Approach to the Computation of Geometric Graphs
LIOTTA, Giuseppe
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 about the computation of relative neighborhood graphs.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
