Three problems about simple polygons

DOI10.1016/J.COMGEO.2005.11.002zbMATH Open1102.65021OpenAlexW2010416098MaRDI QIDQ2432735FDOQ2432735

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

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

zbMATH Keywords

algorithmsconvex hullgeometric optimizationpolygon triangulation

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Packing two disks in a polygon
• Searching for empty convex polygons
• Common tangents of two disjoint polygons in linear time and constant workspace
• Computing hereditary convex structures
• Linear programming in \({\mathbb{R}}^ 3\) and the skeleton and largest incircle of a convex polygon
• Title not available (Why is that?)

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)