An O(n\log \log n)-Time Algorithm for Triangulating a Simple Polygon
From MaRDI portal
An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
Recommendations
- scientific article; zbMATH DE number 619546
- Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
- A randomized algorithm for triangulating a simple polygon in linear time
- Triangulating a simple polygon in linear time
- Time-space trade-offs for triangulating a simple polygon
- Time-space trade-offs for triangulating a simple polygon
- Erratum: An O(n\log \log n)-Time Algorithm for Triangulating a Simple Polygon
- A contribution to triangulation algorithms for simple polygons
- scientific article; zbMATH DE number 3932438
- A non-recursive algorithm for polygon triangulation
Cited in
(51)- Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
- A survey of motion planning and related geometric algorithms
- Storing line segments in partition trees
- Geometric classification of triangulations and their enumeration in a convex polygon
- A fast Las Vegas algorithm for triangulating a simple polygon
- Motion planning in the presence of movable obstacles
- Optimal shortest path queries in a simple polygon
- An algorithmic approach to some problems in terrain navigation
- An efficient algorithm for finding the CSG representation of a simple polygon
- Polygon triangulation: Efficiency and minimality
- 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 Linear Time Heuristics for Trapezoidation of GIS Polygons
- Computing geodesic furthest neighbors in simple polygons
- Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
- Computing simple circuits from a set of line segments
- 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
- Triangulating a simple polygon in linear time
- Translating polygons with applications to hidden surface removal
- An efficient randomized algorithm for higher-order abstract Voronoi diagrams
- A randomized algorithm for triangulating a simple polygon in linear time
- Shortest watchman routes in simple polygons
- Graphics in flatland revisited
- Visibility and intersection problems in plane geometry
- A contribution to triangulation algorithms for simple polygons
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Finding minimum-cost flows by double scaling
- Fast algorithms for one-dimensionsal compaction with jog insertion
- On the minimality of polygon triangulation
- Tiling polygons with parallelograms
- A workbench for computational geometry
- On the correctness of a linear-time visibility polygon algorithm∗
- Dynamic convex hulls under window-sliding updates
- Computational geometry in a curved world
- Decomposition and intersection of simple splinegons
- Computing bushy and thin triangulations
- Triangulation and shape-complexity
- Triangulating Simple Polygons and Equivalent Problems
- Optimal parallel algorithms for point-set and polygon problems
- An O(log log n) algorithm to compute the kernel of a polygon
- Minimum vertex hulls for polyhedral domains
- scientific article; zbMATH DE number 753970 (Why is no real title available?)
- TRIANGULATING DISJOINT JORDAN CHAINS
- An optimal visibility graph algorithm for triangulated simple polygons
- A linear-time algorithm for constructing a circular visibility diagram
- Computing the geodesic center of a simple polygon
- Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences
- Time-space trade-offs for triangulating a simple polygon
- scientific article; zbMATH DE number 3932438 (Why is no real title available?)
- The zookeeper route problem
This page was built for publication: An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3777450)
