Given a set of n points in the plane, any β-skeleton and [γtO,γ1] graph can be computed in quadratic time. The presented algorithms are optimal for β values that are less than 1 and [γtO,γ1] values that result in non-planar graphs. For β = 1, we show a numerically robust algorithm that computes Gabriel graphs in quadratic time and degree 2. We finally show how a β-spectrum can be computed in optimal O(n^2) time.
Optimal, Suboptimal, and Robust Algorithms for Proximity Graphs
LIOTTA, Giuseppe;
2001
Abstract
Given a set of n points in the plane, any β-skeleton and [γtO,γ1] graph can be computed in quadratic time. The presented algorithms are optimal for β values that are less than 1 and [γtO,γ1] values that result in non-planar graphs. For β = 1, we show a numerically robust algorithm that computes Gabriel graphs in quadratic time and degree 2. We finally show how a β-spectrum can be computed in optimal O(n^2) time.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.
