Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Reconfiguring Triangulations with Edge Flips and Point Moves
verfasst von : Greg Aloupis, Prosenjit Bose, Pat Morin
Erschienen in: Graph Drawing
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
We examine reconfigurations between triangulations and near-triangulations of point sets, and give new bounds on the number of
point moves
and
edge flips
sufficient for any reconfiguration. We show that with
O
(
n
log
n
) edge flips and point moves, we can transform any geometric near-triangulation on
n
points to any other geometric near-triangulation on
n
possibly different points. This improves the previously known bound of
O
(
n
2
) edge flips and point moves.