In this paper, we consider time-space trade-offs for reporting a triangulation of points in the plane. The goal is to minimize the amount of working space while keeping the total running time small. We present the first multi-pass algorithm on the problem that returns the edges of a triangulation with their adjacency information. This even improves the previously best known random-access algorithm.
A Time-Space Tradeoff for Triangulations of Points in the Plane
SILVESTRI, FRANCESCO
2017
Abstract
In this paper, we consider time-space trade-offs for reporting a triangulation of points in the plane. The goal is to minimize the amount of working space while keeping the total running time small. We present the first multi-pass algorithm on the problem that returns the edges of a triangulation with their adjacency information. This even improves the previously best known random-access algorithm.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
paper_68.pdf
accesso aperto
Descrizione: Pre-print of the paper
Tipologia:
Preprint (submitted version)
Licenza:
Accesso gratuito
Dimensione
449.66 kB
Formato
Adobe PDF
|
449.66 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
