Tight bounds in the quadtree complexity theorem and the maximal number of pixels crossed by a curve of given length

DOI10.1016/j.tcs.2015.12.015zbMath1338.68263OpenAlexW2215369150MaRDI QIDQ265042

Antoine Vacavant, Jean-Marie Favreau, Yan Gerard

Publication date: 1 April 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.12.015

zbMATH Keywords

lengthrectifiable curvedigital cover cardinalityquadtree complexity theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (1)

Stretch factor in a planar Poisson–Delaunay triangulation with a large intensity

Cites Work

• On the size of quadtrees generalized to d-dimensional binary pictures
• Analysis of the worst case space complexity of a PR quadtree
• Quad trees: A data structure for retrieval by composite keys
• On piecewise linear approximation of planar Jordan curves
• Foundations of multidimensional and metric data structures.
• About the Maximum Cardinality of the Digital Cover of a Curve with a Given Length
• Expected and worst-case storage requirements for quadtrees
• The space efficiency of quadtrees
• Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour
• Counting regions, holes, and their nesting level in time proportional to the border
• A note on minimal length polygonal approximation to a digitized contour
• Minimum-Perimeter Polygons of Digitized Silhouettes

This page was built for publication: Tight bounds in the quadtree complexity theorem and the maximal number of pixels crossed by a curve of given length