Three problems about simple polygons

DOI10.1016/J.COMGEO.2005.11.002MaRDI QIDQ2432735zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan

Publication date 25 October 2006

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2005.11.002

zbMATH Keywords

algorithmsconvex hullgeometric optimizationpolygon triangulation

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• Packing two disks in a polygon
• Finding the convex hull of a simple polygon
• Packing two disks into a polygonal environment.
• Linear algorithm to find the largest intriangles of a planar convex polygon
• On finding the convex hull of a simple polygon

Cites work

• scientific article; zbMATH DE number 1629820 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• A fast Las Vegas algorithm for triangulating a simple polygon
• A linear algorithm for finding the convex hull of a simple polygon
• A new linear convex hull algorithm for simple polygons (Corresp.)
• A randomized algorithm for triangulating a simple polygon in linear time
• A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• An Output-Sensitive Convex Hull Algorithm for Planar Objects
• Applications of random sampling in computational geometry. II
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Cartographic line simplification and polygon CSG formulae in O(n^* n) time
• Fast skeleton construction
• Finding the convex hull of a simple polygon
• Finding the medial axis of a simple polygon in linear time
• Geometric applications of a randomized optimization technique
• Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
• On finding the convex hull of a simple polygon
• On-line construction of the convex hull of a simple polyline
• Optimal Search in Planar Subdivisions
• Packing two disks in a polygon
• Packing two disks into a polygonal environment.
• Placing two disks in a convex polygon
• Planar separators and parallel polygon triangulation.
• Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
• RANDOMIZATION YIELDS SIMPLE O(n log^⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS
• Simplified linear-time Jordan sorting and polygon clipping
• Sorting jordan sequences in linear time using level-linked search trees
• Splitting a Delaunay triangulation in linear time
• TRIANGULATING DISJOINT JORDAN CHAINS
• Triangulating a simple polygon in linear time

Cited in

(6)

• Packing two disks in a polygon
• Searching for empty convex polygons
• Computing hereditary convex structures
• Common tangents of two disjoint polygons in linear time and constant workspace
• Linear programming in \({\mathbb{R}}^ 3\) and the skeleton and largest incircle of a convex polygon
• scientific article; zbMATH DE number 665700 (Why is no real title available?)

This page was built for publication: Three problems about simple polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2432735)