Time-space trade-offs for triangulations and Voronoi diagrams

DOI10.1016/j.comgeo.2017.01.001zbMath1443.68205OpenAlexW2200983654MaRDI QIDQ1615777

Marcel Roeloffzen, Matias Korman, Yannik Stein, Wolfgang Mulzer, André van Renssen, Paul Seiferth

Publication date: 31 October 2018

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2017.01.001

zbMATH Keywords

triangulationrandomized algorithmVoronoi diagramtime-space trade-off

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) Randomized algorithms (68W20)

Related Items (1)

A new balanced subdivision of a simple polygon for time-space trade-off algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing a visibility polygon using few variables
• Space-time trade-offs for stack-based algorithms
• Selection from read-only memory and sorting with minimum data movement
• A deterministic view of random sampling and its use in geometry
• Multi-pass geometric algorithms
• Selection and sorting with limited storage
• Applications of random sampling in computational geometry. II
• Memory-constrained algorithms for simple polygons
• On the identification of the convex hull of a finite set of points in the plane
• Time-Space Tradeoffs for All-Nearest-Larger-Neighbors Problems
• Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem
• Shortest path in a polygon using sublinear space
• Triangulating Simple Polygons and Equivalent Problems
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Optimal Search in Planar Subdivisions
• ON COMPUTING VORONOI DIAGRAMS FOR SORTED POINT SETS
• Priority Queues and Sorting for Read-Only Data
• Towards in-place geometric algorithms and data structures

This page was built for publication: Time-space trade-offs for triangulations and Voronoi diagrams