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.015MaRDI QIDQ265042zbMATH OpenOpenAlexFDO

Authors Yan Gerard, Antoine Vacavant, Jean-Marie Favreau

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

digital cover cardinalitylengthquadtree complexity theoremrectifiable curve

Mathematics Subject Classification ID

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

Recommendations

• On the size of quadtrees generalized to d-dimensional binary pictures
• scientific article; zbMATH DE number 3852447
• scientific article; zbMATH DE number 3986653
• scientific article; zbMATH DE number 4114092
• A Polynomial Time Complexity Bound for Computations on Curves
• Approximating the maximum rectilinear crossing number
• On the complexity of finding circumscribed rectangles and squares for a two-dimensional domain
• On resolution complexity of plane curves
• A generalized solution to the quadtree expected complexity problem
• Bounds for rectilinear crossing numbers

Cites work

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

Cited in

(1)

• Stretch factor in a planar Poisson-Delaunay triangulation with a large intensity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q265042)