Triangulating Simple Polygons and Equivalent Problems
From MaRDI portal
Publication:3721847
DOI10.1145/357337.357341zbMath0592.68084OpenAlexW2073058919WikidataQ29301848 ScholiaQ29301848MaRDI QIDQ3721847
Delfin Y. Montuno, Alain Fournier
Publication date: 1984
Published in: ACM Transactions on Graphics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/357337.357341
triangulationdecompositioncomputer graphicscomputational geometrygeometric algorithmpolygons with holesscan conversionedge-vertex visibilitytrapezoidization
Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99)
Related Items
Time-space trade-offs for triangulations and Voronoi diagrams, Computing minimum length paths of a given homotopy class, Time-Space Trade-offs for Triangulations and Voronoi Diagrams, Quadrangulations of planar sets, A linear-time construction of the relative neighborhood graph within a histogram, Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons, Parallel triangulation of a polygon in two calls to the trapezoidal map, Decomposition and intersection of simple splinegons, Optimum watchman routes, Memory-constrained algorithms for simple polygons, Reprint of: Memory-constrained algorithms for simple polygons, Characterizing and efficiently computing quadrangulations of planar point sets, On \(k\)-convex polygons, Computational geometry in a curved world, Some chain visibility problems in a simple polygon, A new triangulation-linear class of simple polygons, Triangulating a simple polygon in linear time, External-memory algorithms for processing line segments in geographic information systems, Tiling polygons with parallelograms, Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures, Computing the shortest diagonal of a monotone polygon in linear time, Linear-time algorithms for weakly-monotone polygons, Minimum vertex hulls for polyhedral domains, An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains, Triangulating input-constrained planar point sets, Reprint of: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, On the minimality of polygon triangulation, A fast Las Vegas algorithm for triangulating a simple polygon, A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, A workbench for computational geometry, Monotone path systems in simple regions
