Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Kinetic Euclidean Minimum Spanning Tree in the Plane
verfasst von : Zahed Rahmati, Alireza Zarei
Erschienen in: Combinatorial Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper presents the first kinetic data structure (
KDS
) for maintenance of the Euclidean minimum spanning tree (
EMST
) on a set of
n
moving points in 2-dimensional space. We build a
KDS
of size
O
(
n
) in
O
(
n
log
n
) preprocessing time by which their
EMST
is maintained efficiently during the motion. In terms of the
KDS
performance parameters, our
KDS
is
responsive
,
local
, and
compact
.