Ahn, Hee-Kap; Baraldo, Nicola; Oh, Eunjin; Silvestri, Francesco 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]. Cited in 4 Documents MSC: 68W40 Analysis of algorithms 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) PDFBibTeX XMLCite \textit{H.-K. Ahn} et al., Lect. Notes Comput. Sci. 10392, 3--12 (2017; Zbl 1434.68745) Full Text: DOI Link