Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour
DOI10.1007/978-3-642-04397-0_10zbMATH Open1261.68137OpenAlexW1589343680MaRDI QIDQ3648777FDOQ3648777
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
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
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55)
Cites Work
- Necklaces of beads in k colors and k-ary de Bruijn sequences
- Title not available (Why is that?)
- Certain words on the real projective line
- Sturmian words, Lyndon words and trees
- On piecewise linear approximation of planar Jordan curves
- Title not available (Why is that?)
- Factorizing words over an ordered alphabet
- A note on minimal length polygonal approximation to a digitized contour
- Minimum-Perimeter Polygons of Digitized Silhouettes
- Lyndon + Christoffel = digitally convex
- Combinatorics on Words
- Title not available (Why is that?)
- Optimal shortest path queries in a simple polygon
- On-line construction of the convex hull of a simple polyline
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (11)
- 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\)
- 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
- Combining topological maps, multi-label simple points, and minimum-length polygons for efficient digital partition model
- Faithful polygonal representation of the convex and concave parts of a digital curve
- Two linear-time algorithms for computing the minimum length polygon of a digital contour
- Digital straight segment filter for geometric description
- Computing the minimal perimeter polygon for digital objects in the triangular tiling
- Dynamic minimum length polygon
- Combinatorial Image Analysis
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)
