Triangulating a simple polygon

DOI10.1016/0020-0190(78)90062-5zbMath0384.68040OpenAlexW1983487792MaRDI QIDQ1249042

Michael R. Garey, Franco P. Preparata, Robert Endre Tarjan, David S. Johnson

Publication date: 1978

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(78)90062-5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polyhedra and polytopes; regular figures, division of spaces (51M20) Algorithms in computer science (68W99)

Related Items

Generalized Delaunay triangulation for planar graphs, The power of geometric duality, Computing the intersection-depth to polyhedra, On compatible triangulations of simple polygons, Visibility of disjoint polygons, Visibility between two edges of a simple polygon, Nonobtuse triangulation of polygons, 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, Finding a closet visible vertex pair between two polygons, Hidden-surface removal in polyhedral cross-sections, Computing the link center of a simple polygon, Unnamed Item, Memory-constrained algorithms for simple polygons, An optimal visibility graph algorithm for triangulated simple polygons, On the geodesic Voronoi diagram of point sites in a simple polygon, On geodesic properties of polygons relevant to linear time triangulation, Computing conforming partitions of orthogonal polygons with minimum stabbing number, Reprint of: Memory-constrained algorithms for simple polygons, On Taxicab Distance Mean Functions and their Geometric Applications: Methods, Implementations and Examples, Approximation algorithms for decomposing octilinear polygons, Shortcut hulls: vertex-restricted outer simplifications of polygons, Rectangularization of digital objects and its relation with straight skeletons, Some chain visibility problems in a simple polygon, Minimum k-partitioning of rectilinear polygons, REGION INTERVISIBILITY IN TERRAINS, A new triangulation-linear class of simple polygons, Triangulating a simple polygon in linear time, Space-time trade-offs for stack-based algorithms, COMPUTATIONAL AND STRUCTURAL ADVANTAGES OF CIRCULAR BOUNDARY REPRESENTATION, Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures, Computing bushy and thin triangulations, Geometric pattern matching under Euclidean motion, Linear-time algorithms for weakly-monotone polygons, Parallel methods for visibility and shortest-path problems in simple polygons, The furthest-site geodesic Voronoi diagram, Reprint of: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, THREE-DIMENSIONAL TOPOLOGICAL SWEEP FOR COMPUTING ROTATIONAL SWEPT VOLUMES OF POLYHEDRAL OBJECTS, Computing the geodesic center of a simple polygon, Two algorithms for constructing a Delaunay triangulation, Approximation algorithms for partitioning a rectangle with interior points, On the minimality of polygon triangulation, Affine invariant triangulations, A simple linear algorithm for intersecting convex polygons, A unifying approach for a class of problems in the computational geometry of polygons, Computing geodesic furthest neighbors in simple polygons, A fast Las Vegas algorithm for triangulating a simple polygon, Dynamic Trees and Dynamic Point Location, Applications of a two-dimensional hidden-line algorithm to other geometric problems, Triangulation algorithms for generating as-is floor plans, A decision procedure for optimal polyhedron partitioning, Visible surface calculation for complex unstructured polygonal scenes, On partitioning rectilinear polygons into star-shaped polygons, A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, EDGE GUARDS IN STRAIGHT WALKABLE POLYGONS, A workbench for computational geometry, Geometric classification of triangulations and their enumeration in a convex polygon

Cites Work