Triangulating a simple polygon in linear time
From MaRDI portal
Publication:1176324
DOI10.1007/BF02574703zbMATH Open0753.68090WikidataQ54156617 ScholiaQ54156617MaRDI QIDQ1176324FDOQ1176324
Authors: Bernard Chazelle 
Publication date: 25 June 1992
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131172
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- Applications of a Planar Separator Theorem
- Title not available (Why is that?)
- A Separator Theorem for Planar Graphs
- Optimal Search in Planar Subdivisions
- A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- A linear time algorithm for minimum link paths inside a simple polygon
- Optimal Point Location in a Monotone Subdivision
- Visibility and intersection problems in plane geometry
- Optimal shortest path queries in a simple polygon
- Primitives for the manipulation of general subdivisions and the computation of Voronoi
- Triangulating a simple polygon
- Triangulation and shape-complexity
- Triangulating Simple Polygons and Equivalent Problems
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
- Decomposition and intersection of simple splinegons
- An optimal visibility graph algorithm for triangulated simple polygons
- Finding the intersection of two convex polyhedra
- An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
- Title not available (Why is that?)
- Sorting jordan sequences in linear time using level-linked search trees
- Title not available (Why is that?)
- A fast Las Vegas algorithm for triangulating a simple polygon
Cited In (only showing first 100 items - show all)
- Computing in linear time a chord from which a simple polygon is weakly internally visible
- Translating a convex polyhedron over monotone polyhedra
- An optimal algorithm for constructing an optimal bridge between two simple rectilinear polygons
- Illumination of Orthogonal Polygons with Orthogonal Floodlights
- Hamiltonian triangulations and circumscribing polygons of disjoint line segments
- Approximation algorithms for decomposing octilinear polygons
- Quadrangulations of planar sets
- Parallel methods for visibility and shortest-path problems in simple polygons
- A 2-approximation algorithm for the zookeeper's problem
- Simplicial mesh of an arbitrary polyhedron.
- VISIBILITY STABS AND DEPTH-FIRST SPIRALLING ON LINE SEGMENTS IN OUTPUT SENSITIVE TIME
- Triangulability of convex graphs and convex skewness
- Approximate Shortest Paths in Polygons with Violations
- An approximative solution to the Zookeeper's problem
- Computing \(L_1\) shortest paths among polygonal obstacles in the plane
- Recognizing weakly simple polygons
- ISOMORPHIC TRIANGULATIONS WITH SMALL NUMBER OF STEINER POINTS
- Stabbing information of a simple polygon
- 2-toroids and their 3-triangulation
- Finding a closet visible vertex pair between two polygons
- Lower bounds for approximate polygon decomposition and minimum gap
- A randomized algorithm for triangulating a simple polygon in linear time
- An efficient randomized algorithm for higher-order abstract Voronoi diagrams
- The geometry of carpentry and joinery
- Fast grid-free surface tracking
- Title not available (Why is that?)
- Fast segment insertion and incremental construction of constrained Delaunay triangulations
- Adaptive planar point location
- Near optimal line segment queries in simple polygons
- On the minimality of polygon triangulation
- Planar straight-line realizations of 2-trees with prescribed edge lengths
- Decompositions and boundary coverings of non-convex fat polyhedra
- Note on an art gallery problem
- Optimally computing a shortest weakly visible line segment inside a simple polygon
- A new linear algorithm for triangulating monotone polygons
- OPTIMAL VORONOI DIAGRAM CONSTRUCTION WITH n CONVEX SITES IN THREE DIMENSIONS
- Optimal parallel algorithms for rectilinear link-distance problems
- Shortest curves in planar regions with curved boundary
- An algorithm for recognizing palm polygons
- Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear-time
- Dynamic output-sensitive hidden surface removal for \(c\)-oriented polyhedra
- Special subgraphs of weighted visibility graphs
- Title not available (Why is that?)
- A linear-time algorithm for constructing a circular visibility diagram
- Finding minimal nested polygons
- Time-space trade-offs for triangulating a simple polygon
- On compatible triangulations of simple polygons
- A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation
- \(L_{1}\) shortest path queries in simple polygons
- Geometric path problems with violations
- Algorithms for Computing Diffuse Reflection Paths in Polygons
- Dynamic Trees and Dynamic Point Location
- On triangulating three-dimensional polygons
- Linear-time algorithms for weakly-monotone polygons
- Distances in benzenoid systems: Further developments
- Compressed algebraic cubature over polygons with applications to optical design
- Tiling with Squares and Packing Dominos in Polynomial Time
- Geometric classification of triangulations and their enumeration in a convex polygon
- Delaunay triangulation of imprecise points in linear time after preprocessing
- Towards a definition of higher order constrained Delaunay triangulations
- Peeling potatoes near-optimally in near-linear time
- Computing minimum length paths of a given homotopy class
- On a class of \(O(n^2)\) problems in computational geometry
- A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon
- Solving the irregular strip packing problem via guided local search for overlap minimization
- A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon
- Memory-constrained algorithms for simple polygons
- Algorithms for the decomposition of a polygon into convex polygons
- An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments
- Distance-sensitive planar point location
- Geodesic-preserving polygon simplification
- Approximate convex decomposition of polygons
- Abstract Voronoi diagrams from closed bisecting curves
- Guarding curvilinear art galleries with vertex or point guards
- Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
- Monotone drawings of graphs with fixed embedding
- Efficient generation of simple polygons for characterizing the shape of a set of points in the plane
- Adaptive density estimation on bounded domains under mixing conditions
- A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions
- Delaunay Triangulation of Imprecise Points Simplified and Extended
- New results on binary space partitions in the plane
- Maintaining visibility of a polygon with a moving point of view
- A linear-time algorithm for the geodesic center of a simple polygon
- CLEARING A POLYGON WITH TWO 1-SEARCHERS
- On geodesic properties of polygons relevant to linear time triangulation
- On a class of \(O(n^ 2)\) problems in computational geometry
- Ray shooting in polygons using geodesic triangulations
- Approximation algorithms for lawn mowing and milling
- Conformal mapping in linear time
- Computing realistic terrains from imprecise elevations
- Geometric pattern matching under Euclidean motion
- Converting triangulations to quadrangulations
- Expected asymptotically optimal planar point location
- Computing a median point of a simple rectilinear polygon
- Linear-size nonobtuse triangulation of polygons
- Minimum weight pseudo-triangulations
- Three problems about simple polygons
- Computing hereditary convex structures
- Guarding a Polygon Without Losing Touch
- Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs
This page was built for publication: Triangulating a simple polygon in linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1176324)
