Two linear-time algorithms for computing the minimum length polygon of a digital contour
The minimum length polygon (MLP) is used for approaching the geometry of a digital object. One of the possible definitions is to call it the polygon of minimum perimeter which stays in the band of one-pixel wide centered on the digital contour. Several algorithms for computing the MLP have been published but their time complexity is not linear or the used data structure is very complex. The authors of the article under review show that MLP has strong arithmetic and combinatorial properties. They present two new definitions related to the digital contour and new optimal time integer-only algorithms for computing it. One of these new definitions says that the arithmetic MLP of a digital contour is a polygon defined by so-called zones. The combinatorial MLP of a digital contour is defined using a simple algorithm based on computation vertices, which can be found in this paper. This paper contains the full theoretical background for understanding the main problems of the minimal length polygon of digital contours. Some illustrations of the results complete the paper.
- 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
- A note on minimal length polygonal approximation to a digitized contour
- An Approach for the Estimation of the Precision of a Real Object from its Digitization
- Certain words on the real projective line
- Combinatorics on Words
- Digital Deformable Model Simulating Active Contours
- Discrete images, objects, and functions in \(Z^ n\)
- Factorizing words over an ordered alphabet
- Geometric properties for incomplete data.
- 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 3533716 (Why is no real title available?)
- scientific article; zbMATH DE number 1241781 (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?)
- scientific article; zbMATH DE number 1436417 (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
- Some combinatorial properties of Sturmian words
- Sturmian words, Lyndon words and trees
- Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour
- What does digital straightness tell about digital convexity?
- A polygonal approximation for general 4-contours corresponding to weakly simple curves
- Euclidean farthest-point Voronoi diagram of a digital edge
- Dynamic minimum length polygon
- Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour
- scientific article; zbMATH DE number 2084497 (Why is no real title available?)
- Discrete Geometry for Computer Imagery
- Combinatorial Image Analysis
- Computing the minimal perimeter polygon for digital objects in the triangular tiling
- Computing the minimal perimeter polygon for sets of rectangular tiles based on visibility cones
- Fast and exact convex and concave decomposition of digitized shapes
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 Q765322)
