×

A time-space trade-off for triangulations of points in the plane. (English) Zbl 1434.68745

Cao, Yixin (ed.) et al., Computing and combinatorics. 23rd international conference, COCOON 2017, Hong Kong, China, August 3–5, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10392, 3-12 (2017).
Summary: 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.
For the entire collection see [Zbl 1369.68014].

MSC:

68W40 Analysis of algorithms
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI Link