Triangulating a simple polygon
From MaRDI portal
Publication:1249042
DOI10.1016/0020-0190(78)90062-5zbMATH Open0384.68040OpenAlexW1983487792MaRDI QIDQ1249042FDOQ1249042
Authors: M. R. Garey, D. S. Johnson, F. P. Preparata, Robert E. Tarjan 
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
Analysis of algorithms and problem complexity (68Q25) Polyhedra and polytopes; regular figures, division of spaces (51M20) Algorithms in computer science (68W99)
Cites Work
Cited In (57)
- The furthest-site geodesic Voronoi diagram
- Dynamic Trees and Dynamic Point Location
- Linear-time algorithms for weakly-monotone polygons
- Two algorithms for constructing a Delaunay triangulation
- Geometric classification of triangulations and their enumeration in a convex polygon
- A fast Las Vegas algorithm for triangulating a simple polygon
- Approximation algorithms for decomposing octilinear polygons
- Hidden-surface removal in polyhedral cross-sections
- Parallel methods for visibility and shortest-path problems in simple polygons
- Memory-constrained algorithms for simple polygons
- Generalized Delaunay triangulation for planar graphs
- On the geodesic Voronoi diagram of point sites in a simple polygon
- Reprint of: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
- A simple linear algorithm for intersecting convex polygons
- Applications of a two-dimensional hidden-line algorithm to other geometric problems
- Computing geodesic furthest neighbors in simple polygons
- Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
- The power of geometric duality
- Finding a closet visible vertex pair between two polygons
- A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
- On geodesic properties of polygons relevant to linear time triangulation
- A unifying approach for a class of problems in the computational geometry of polygons
- Triangulating a simple polygon in linear time
- Computing the link center of a simple polygon
- EDGE GUARDS IN STRAIGHT WALKABLE POLYGONS
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Geometric pattern matching under Euclidean motion
- Nonobtuse triangulation of polygons
- On the minimality of polygon triangulation
- A workbench for computational geometry
- Visibility between two edges of a simple polygon
- Computing conforming partitions of orthogonal polygons with minimum stabbing number
- Computing the intersection-depth to polyhedra
- Computational and structural advantages of circular boundary representation
- Some chain visibility problems in a simple polygon
- Minimum k-partitioning of rectilinear polygons
- Computing bushy and thin triangulations
- A new triangulation-linear class of simple polygons
- Affine invariant triangulations
- Space-time trade-offs for stack-based algorithms
- Visible surface calculation for complex unstructured polygonal scenes
- An optimal visibility graph algorithm for triangulated simple polygons
- A decision procedure for optimal polyhedron partitioning
- On partitioning rectilinear polygons into star-shaped polygons
- Computing the geodesic center of a simple polygon
- On compatible triangulations of simple polygons
- Triangulation algorithms for generating as-is floor plans
- Approximation algorithms for partitioning a rectangle with interior points
- Visibility of disjoint polygons
- Reprint of: Memory-constrained algorithms for simple polygons
- Method for finding and storing optimal triangulations based on square matrix
- Rectangularization of digital objects and its relation with straight skeletons
- REGION INTERVISIBILITY IN TERRAINS
- On Taxicab Distance Mean Functions and their Geometric Applications: Methods, Implementations and Examples
- THREE-DIMENSIONAL TOPOLOGICAL SWEEP FOR COMPUTING ROTATIONAL SWEPT VOLUMES OF POLYHEDRAL OBJECTS
- A linear-time construction of the relative neighborhood graph within a histogram
- Shortcut hulls: vertex-restricted outer simplifications of polygons
This page was built for publication: Triangulating a simple polygon
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1249042)
