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

DOI10.1007/978-3-642-04397-0_10zbMath1261.68137MaRDI QIDQ3648777

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

52B55: Computational aspects related to convexity

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

Related Items

Tight bounds in the quadtree complexity theorem and the maximal number of pixels crossed by a curve of given length, A linear time and space algorithm for detecting path intersection in \(\mathbb Z^d\), Two linear-time algorithms for computing the minimum length polygon of a digital contour, 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, Combining Topological Maps, Multi-Label Simple Points, and Minimum-Length Polygons for Efficient Digital Partition Model, Dynamic Minimum Length Polygon

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lyndon + Christoffel = digitally convex
• On-line construction of the convex hull of a simple polyline
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• Certain words on the real projective line
• Sturmian words, Lyndon words and trees
• Optimal shortest path queries in a simple polygon
• On piecewise linear approximation of planar Jordan curves
• Factorizing words over an ordered alphabet
• Combinatorics on Words
• A note on minimal length polygonal approximation to a digitized contour
• Minimum-Perimeter Polygons of Digitized Silhouettes