Sweeping x-monotone pseudolines

2025/07/28 by Biedl, Therese, Chambers, Erin, Kostitsyna, Irina +1
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2507.21322

Abstract

We study the problem of sweeping a pseudoline arrangement with n x-monotone curves with a rope (an x-monotone curve that connects the points at infinity). The rope can move by flipping over a face of the arrangement, replacing parts of it from the lower to the upper chain of the face. Counting as length of the rope the number of edges, what rope-length can be needed in such a sweep? We show that all such arrangements can be swept with rope-length at most 2n-2, and for some arrangements rope-length at least 7(n-2)/4+1 is required. We also discuss some complexity issues around the problem of computing a sweep with the shortest rope-length.

Citations

• NumPSLA -- An experimental research tool for pseudoline arrangements and order types
• Minimum Height Drawings of Ordered Trees in Polynomial Time: Homotopy Height of Tree Duals
• Homotopy height, grid-major height and graph-drawing height
• Typical Sequences Revisited --- Computing Width Parameters of Graphs
• On the complexity of optimal homotopies
• Constructing monotone homotopies and sweepouts

Related

• Arrangements of Approaching Pseudo-Lines
• An Improved Lower Bound on the Number of Pseudoline Arrangements
• Extending simple monotone drawings
• The unavoidable arrangements of pseudocircles
• Sweeping an oval to a vanishing point