Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour
From MaRDI portal
Publication:3648777
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
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