Triangulating a simple polygon in linear time

DOI10.1007/BF02574703zbMath0753.68090WikidataQ54156617 ScholiaQ54156617MaRDI QIDQ1176324

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

zbMATH Keywords

triangulation simple polygon

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

SHORTEST DESCENDING PATHS: TOWARDS AN EXACT ALGORITHM, Constructing pairwise disjoint paths with few links, On condorcet and median points of simple rectilinear polygons, Reconstruction of Weakly Simple Polygons from Their Edges, Quadrangulations of planar sets, CUTTING OUT POLYGONS WITH A CIRCULAR SAW, Delaunay Triangulation of Imprecise Points Simplified and Extended, OPTIMAL TRIANGULATIONS OF POINTS AND SEGMENTS WITH STEINER POINTS, Vertex Guarding for Dynamic Orthogonal Art Galleries, Computing the Mostar index in networks with applications to molecular graphs, Reverse polish notation method, ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE, Triangulability of convex graphs and convex skewness, Peeling Potatoes Near-Optimally in Near-Linear Time, Checking the convexity of polytopes and the planarity of subdivisions (extended abstract), Guarding a Polygon Without Losing Touch, Tiling with Squares and Packing Dominos in Polynomial Time, OPTIMAL VORONOI DIAGRAM CONSTRUCTION WITH n CONVEX SITES IN THREE DIMENSIONS, Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear-time, Fast skeleton construction, Shortcut hulls: vertex-restricted outer simplifications of polygons, Optimal Area Polygonization by Triangulation and Visibility Search, Approximating the smallest $k$-enclosing geodesic disc in a simple polygon, Point enclosure problem for homothetic polygons, Unnamed Item, Unnamed Item, Optimal Triangulation with Steiner Points, Efficient and Qualified Mesh Generation for Gaussian Molecular Surface Using Adaptive Partition and Piecewise Polynomial Approximation, Approximate Shortest Paths in Polygons with Violations, Fast enumeration algorithms for non-crossing geometric graphs, Characterizing LR-visibility polygons and related problems, An addition to art galleries with interior walls, Unnamed Item, Unnamed Item, Algorithms for Computing Diffuse Reflection Paths in Polygons, Generating All Triangulations of Plane Graphs (Extended Abstract), Conformal mapping in linear time, PARETO ENVELOPES IN SIMPLE POLYGONS, Fast grid-free surface tracking, CLEARING A POLYGON WITH TWO 1-SEARCHERS, Unnamed Item, Dividing a Territory Among Several Vehicles, Point Location in Incremental Planar Subdivisions., Solving the irregular strip packing problem via guided local search for overlap minimization, Unnamed Item, Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time, Dynamic Trees and Dynamic Point Location, Unnamed Item, Adaptive Planar Point Location, Abstract Voronoi Diagrams from Closed Bisecting Curves, GEODESIC-PRESERVING POLYGON SIMPLIFICATION, Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions, VISIBILITY STABS AND DEPTH-FIRST SPIRALLING ON LINE SEGMENTS IN OUTPUT SENSITIVE TIME, Query-Points Visibility Constraint Minimum Link Paths in Simple Polygons, Illumination of Orthogonal Polygons with Orthogonal Floodlights, Determining Weak Visibility of a Polygon from an Edge in Parallel, ISOMORPHIC TRIANGULATIONS WITH SMALL NUMBER OF STEINER POINTS, Optimally computing a shortest weakly visible line segment inside a simple polygon, Simplicial mesh of an arbitrary polyhedron., Computing minimum length paths of a given homotopy class, Ray shooting in polygons using geodesic triangulations, An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments, Distance-sensitive planar point location, On compatible triangulations of simple polygons, Expected asymptotically optimal planar point location, Approximate unions of lines and Minkowski sums, Maintaining visibility of a polygon with a moving point of view, An algorithm for recognizing palm polygons, A 2-approximation algorithm for the zookeeper's problem, A linear-time algorithm for constructing a circular visibility diagram, Optimal parallel algorithms for rectilinear link-distance problems, Finding a closet visible vertex pair between two polygons, Minimum weight pseudo-triangulations, Planar straight-line realizations of 2-trees with prescribed edge lengths, On a class of $O(n^ 2)$ problems in computational geometry, Partitioning orthogonal polygons into $\leq 8$-vertex pieces, with application to an art gallery theorem, A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams, Memory-constrained algorithms for simple polygons, New results on binary space partitions in the plane, Generalized hidden surface removal, Generalized guarding and partitioning for rectilinear polygons, A multifacility location problem on median spaces, On orthogonally guarding orthogonal polygons with bounded treewidth, Optimally guarding 2-reflex orthogonal polyhedra by reflex edge guards, Converting triangulations to quadrangulations, Note on an art gallery problem, Reprint of: Memory-constrained algorithms for simple polygons, An efficient randomized algorithm for higher-order abstract Voronoi diagrams, Computing $L_1$ shortest paths among polygonal obstacles in the plane, A new balanced subdivision of a simple polygon for time-space trade-off algorithms, On triangulating three-dimensional polygons, Near optimal line segment queries in simple polygons, Adaptive density estimation on bounded domains under mixing conditions, Rectangular partitions of a rectilinear polygon, Approximation algorithms for decomposing octilinear polygons, Recognizing weakly simple polygons, On a class of $O(n^2)$ problems in computational geometry, Three problems about simple polygons, Representing a functional curve by curves with fewer peaks, Shortest paths and convex hulls in 2D complexes with non-positive curvature, Geometric path problems with violations, Preprocessing imprecise points for Delaunay triangulation: simplified and extended, On the polygonal diameter (= link diameter) of the interior, resp. exterior, of a simple closed polygon in the plane, Guarding curvilinear art galleries with vertex or point guards, Approximation algorithms for the watchman route and zookeeper's problems., Algorithms for the decomposition of a polygon into convex polygons, Efficient generation of simple polygons for characterizing the shape of a set of points in the plane, Space-time trade-offs for stack-based algorithms, Algorithms for deciding the containment of polygons, An optimal algorithm for finding the edge visibility polygon under limited visibility, Polygon triangulation in $O(n\log{}\log{}n)$ time with simple data structures, Finding a shortest diagonal of a simple polygon in linear time, LR-visibility in polygons, Geometric pattern matching under Euclidean motion, Computing the visibility polygon of an island in a polygonal domain, Dynamic output-sensitive hidden surface removal for $c$-oriented polyhedra, Linear-time algorithms for weakly-monotone polygons, Special subgraphs of weighted visibility graphs, Covering paths for planar point sets, Hamiltonian triangulations and circumscribing polygons of disjoint line segments, Minimum-link paths among obstacles in the plane, Parallel methods for visibility and shortest-path problems in simple polygons, An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains, Computing hereditary convex structures, Shortest curves in planar regions with curved boundary, The geometry of carpentry and joinery, 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, Approximate convex decomposition of polygons, Computing the $k$-visibility region of a point in a polygon, A linear-time algorithm for the geodesic center of a simple polygon, A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions, Towards a definition of higher order constrained Delaunay triangulations, Compressed algebraic cubature over polygons with applications to optical design, A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon, Finding shortest safari routes in simple polygons, An approximative solution to the Zookeeper's problem, High-order polygonal discontinuous Petrov-Galerkin (PolyDPG) methods using ultraweak formulations, Affine invariant triangulations, Checking the convexity of polytopes and the planarity of subdivisions, Stabbing information of a simple polygon, Delaunay triangulation of imprecise points in linear time after preprocessing, Decompositions and boundary coverings of non-convex fat polyhedra, Optimal placement of base stations in border surveillance using limited capacity drones, Rectilinear paths among rectilinear obstacles, Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane, Approximation algorithms for lawn mowing and milling, Distances in benzenoid systems: Further developments, Finding minimal nested polygons, Monotone drawings of graphs with fixed embedding, Translating a convex polyhedron over monotone polyhedra, Euclidean Steiner minimal trees with obstacles and Steiner visibility graphs, An optimal algorithm for constructing an optimal bridge between two simple rectilinear polygons, Lower bounds for approximate polygon decomposition and minimum gap, Computing a median point of a simple rectilinear polygon, Fast segment insertion and incremental construction of constrained Delaunay triangulations, Geometric classification of triangulations and their enumeration in a convex polygon

Cites Work