Robotic Research Technical Report (Classic Reprint): On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottman Line Sweeping Algorithm - Couverture souple

Pach, Janos

Couverture souple

ISBN 10 : 1332092306 ISBN 13 : 9781332092307

Editeur : Forgotten Books, 2018

Synopsis

Discover how a classic line-sweeping method stays efficient in practice. This technical report analyzes vertical visibility in segment arrangements and the queue size in the Bentley-Ottman algorithm, offering new bounds and practical insights for computational geometry.

Written like a focused study, the work revisits the original Bentley-Ottman approach and examines how many queue updates are truly needed. It shows that, even with complex intersections, the queue size stays near linear in many cases. The paper covers both the general case and special scenarios, such as segments sharing a common projection, and explains the impact on running time and storage.

• New upper bounds on the queue size for line segments and lines, under various conditions


• Detailed analysis of the hammock case and general arrangements in the Bentley-Ottman framework


• Discussion of near-linear storage requirements and practical implications for implementations


• Connections to related problems and open questions in vertical visibility and line sweeping

Ideal for readers of advanced computational geometry, algorithm design, and those applying line-sweeping techniques in practice.

Détails de l'édition

• Éditeur: Forgotten Books
• Date d'édition: 2018
• Langue: anglais
• ISBN 10: 1332092306
• ISBN 13: 9781332092307
• Reliure: Broché
• Nombre de pages: 24
• Coordonnées du fabricant: FB &c Ltd; info@forgottenbooks.org; ; Dalton House; 60 Windsor Avenue; London; SW19 2RR; Royaume-Uni
• Personne responsable: Buchpark GmbH; gpsr@buchpark.de; ; Krügerweg 1; Trebbin; Brandenburg; 14959; Allemagne