Near optimal line segment queries in simple polygons

DOI10.1016/J.JDA.2015.10.002zbMATH Open1344.68261OpenAlexW2186787857MaRDI QIDQ891822FDOQ891822

Authors Mojtaba Nouri Bygi, Mohammad Ghodsi 

Publication date 17 November 2015

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.7803

zbMATH Keywords

computational geometryvisibilityline segment visibility

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: This paper considers the problem of computing the weak visibility polygon (WVP) of any query line segment pq (or WVP(pq)) inside a given simple polygon P. We present an algorithm that preprocesses P and creates a data structure from which WVP(pq) is efficiently reported in an output sensitive manner. Our algorithm needs O(n^2 log n) time and O(n^2) space in the preprocessing phase to report WVP(pq) of any query line segment pq in time O(log^2 n + |WVP(pq)|). We improve the preprocessing time and space of current results for this problem at the expense of more query time.

Recommendations

• Weak visibility queries of line segments in simple polygons and polygonal domains
• Weak visibility counting in simple polygons
• Efficient visibility queries in simple polygons

Cites work

• A linear-time algorithm for solving the strong hidden-line problem in a simple polygon
• Efficient visibility queries in simple polygons
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Optimal Search in Planar Subdivisions
• Triangulating a simple polygon in linear time
• Visibility Algorithms in the Plane
• Visibility and intersection problems in plane geometry
• Visibility queries and maintenance in simple polygons
• Weak visibility queries of line segments in simple polygons and polygonal domains

Cited in

(8)

• Weak visibility queries of line segments in simple polygons and polygonal domains
• Efficient visibility queries in simple polygons
• Cartographic line simplification and polygon CSG formulae in \(O(n\log^* n)\) time
• Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments
• Extremal point queries with lines and line segments and related problems
• Simplified linear-time Jordan sorting and polygon clipping
• Optimal window queries on line segments using the trapezoidal search DAG
• A Probabilistic Analysis of Trie-Based Sorting of Large Collections of Line Segments in Spatial Databases

This page was built for publication: Near optimal line segment queries in simple polygons

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