Polygonal path simplification with angle constraints

DOI10.1016/J.COMGEO.2004.09.003MaRDI QIDQ2571211zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Danny Z. Chen, Ovidiu Daescu, Peter M. Kogge, Ningfang Mi, John Hershberger, Jack Snoeyink

Publication date 1 November 2005

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

angle constraintcomputational geometryoff-line searchpath simplification

Mathematics Subject Classification ID

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

Review text

The authors consider simplification problems in \(\mathbb R^2\) and \(\mathbb R^3\) for paths that have angle constraints. The resulting geometric algorithms run times that are nearly a linear factor better than graph-theoretic solutions that are based on known techniques; this leads to algorithms that match the running times for unconstrained problems. A key step in the solutions, the authors formulate and solve an offline ball exclusion search problem, which may be of interest in its own right.

Recommendations

• Polygonal path approximation with angle constraints
• Computing homotopic line simplification
• Shortest polygonal paths in space
• scientific article; zbMATH DE number 2185597
• Efficiently approximating polygonal paths in three and higher dimensions

Cites work

• An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons
• APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
• APPROXIMATION OF POLYGONAL CURVES WITH MINIMUM NUMBER OF LINE SEGMENTS OR MINIMUM ERROR
• Cartographic line simplication and polygon CSG formulae in \(O(n \log^* n)\) time
• Dynamic half-space range reporting and its applications
• Efficient algorithms for approximating polygonal chains
• Efficiently approximating polygonal paths in three and higher dimensions
• Fitting polygonal functions to a set of points in the plane
• Fractional cascading. I: A data structuring technique
• scientific article; zbMATH DE number 4026646 (Why is no real title available?)
• scientific article; zbMATH DE number 4074316 (Why is no real title available?)
• scientific article; zbMATH DE number 4082817 (Why is no real title available?)
• scientific article; zbMATH DE number 177850 (Why is no real title available?)
• scientific article; zbMATH DE number 1947379 (Why is no real title available?)
• Lower bounds for off-line range searching
• Simplifying a polygonal subdivision while keeping it simple
• SPACE-EFFICIENT ALGORITHMS FOR APPROXIMATING POLYGONAL CURVES IN TWO-DIMENSIONAL SPACE

Cited in

(12)

• Straightening polygonal arcs and convexifying polygonal cycles
• Some random paths with angle constraints
• Embedding ray intersection graphs and global curve simplification
• Dynamic minimum bichromatic separating circle
• Polygonal path approximation with angle constraints
• Geodesic-preserving polygon simplification
• Dynamic minimum bichromatic separating circle
• Global Curve Simplification
• Polyline simplification has cubic complexity
• On optimal polyline simplification using the Hausdorff and Fréchet distance
• Minimum-complexity graph simplification under the Fréchet-like distance
• Distance-preserving approximations of polygonal paths

This page was built for publication: Polygonal path simplification with angle constraints

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