Time-Space Trade-off Algorithms for Triangulating a Simple Polygon

2015/09/25 by Boris Aronov, Matias Korman, Aronov, Boris +7
Computer Science · Engineering · #3D Modeling in Geospatial Applications #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Computer Graphics and Visualization Techniques #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1509.07669

openalex publication_date 2015/09/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

An s-workspace algorithm is an algorithm that has read-only access to the values of the input, write-only access to the output, and only uses O(s) additional words of space. We present a randomized s-workspace algorithm for triangulating a simple polygon P of n vertices that runs in O(n²/s+n log n log⁵ (n/s)) expected time using O(s) variables, for any s ≤ n. In particular, when s ≤ \fracnlog nlog⁵log n the algorithm runs in O(n²/s) expected time.

Related

• A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-off Algorithms
• Space-Time Trade-offs for Stack-Based Algorithms
• A Time-space Trade-off for Computing the Geodesic Center of a Simple Polygon
• Matrix Chain Multiplication and Polygon Triangulation Revisited and Generalized
• A Time-Optimal Delaunay Refinement Algorithm in Two Dimensions