Near optimal line segment queries in simple polygons

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

Authors: Mojtaba Nouri Bygi, Mohammad Ghodsi 

Publication date: 17 November 2015

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

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.

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

Recommendations

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

zbMATH Keywords

computational geometryvisibilityline segment visibility

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

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

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)