2021/05/22 by Har-Peled, Sariel, Zhou, Timothy · 1 voice
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.57717/cgt.v4i1.65
The congestion of a curve is a measure of how much it zigzags around locally. More precisely, a curve p is c-packed if the length of the curve lying inside any ball is at most c times the radius of the ball, and its congestion is the minimum c forwhich pi is c-packed. This paper presents a randomized 42-approximation algorithm for computing the congestion of a curve (or any set of segments in the plane). It runs in O( n log2 n) time and succeeds with high probability. Although the approximation factor is large, the running time improves over the previous fastest constant approximation algorithm, which took soft-O(n4/3) time. We carefully combine new ideas with known techniques to obtain our new near-linear time algorithm.