Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour

DOI10.1007/978-3-642-04397-0_10MaRDI QIDQ3648777zbMATH OpenOpenAlexFDO

Authors Xavier Provençal, Jacques-Olivier Lachaud

Publication date 1 December 2009

Published in Discrete Geometry for Computer Imagery (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-04397-0_10

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Two linear-time algorithms for computing the minimum length polygon of a digital contour
• An efficient algorithm for the optimal polygonal approximation of digitized curves
• Time-and space-optimal contour computation for a set of rectangles
• An optimal algorithm for polygonal approximation of digitized curves
• A linear time algorithm for max-min length triangulation of a convex polygon
• Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments
• scientific article; zbMATH DE number 988752
• An automatic and efficient dynamic programming algorithm for polygonal approximation of digital curves

Cites work

• A note on minimal length polygonal approximation to a digitized contour
• Certain words on the real projective line
• Combinatorics on Words
• Factorizing words over an ordered alphabet
• scientific article; zbMATH DE number 437533 (Why is no real title available?)
• scientific article; zbMATH DE number 2129318 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 2084502 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• Lyndon + Christoffel = digitally convex
• Minimum-Perimeter Polygons of Digitized Silhouettes
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• On piecewise linear approximation of planar Jordan curves
• On-line construction of the convex hull of a simple polyline
• Optimal shortest path queries in a simple polygon
• Sturmian words, Lyndon words and trees

Cited in

(13)

• Digital straight segment filter for geometric description
• A polygonal approximation for general 4-contours corresponding to weakly simple curves
• A linear time combinatorial algorithm to compute the relative orthogonal convex hull of digital objects
• Faithful polygonal representation of the convex and concave parts of a digital curve
• Tight bounds in the quadtree complexity theorem and the maximal number of pixels crossed by a curve of given length
• Combining topological maps, multi-label simple points, and minimum-length polygons for efficient digital partition model
• Dynamic minimum length polygon
• Combinatorial Image Analysis
• A linear time and space algorithm for detecting path intersection in \(\mathbb Z^d\)
• Computing the minimal perimeter polygon for digital objects in the triangular tiling
• Decomposition of rational discrete hyperplanes
• Computing the minimal perimeter polygon for sets of rectangular tiles based on visibility cones
• Two linear-time algorithms for computing the minimum length polygon of a digital contour

This page was built for publication: Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour

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