Space–Query-Time Tradeoff for Computing the Visibility Polygon

DOI10.1007/978-3-642-02270-8_14zbMath1248.68527OpenAlexW1920319052MaRDI QIDQ5321702

Mostafa Nouri, Mohammad Ghodsi

Publication date: 14 July 2009

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02270-8_14

zbMATH Keywords

visibility polygonlogarithmic query time\((1/r)\)-cuttingspace-query-time tradeoff

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Unnamed Item
• Unnamed Item
• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• Construction of \(\epsilon\)-nets
• The power of geometric duality
• Visibility of disjoint polygons
• Cutting hyperplanes for divide-and-conquer
• Visibility queries and maintenance in simple polygons
• New applications of random sampling in computational geometry
• On the Zone Theorem for Hyperplane Arrangements
• An Optimal Algorithm for Computing Visibility in the Plane
• Efficient computation of query point visibility in polygons with holes
• THE VISIBILITY COMPLEX

This page was built for publication: Space–Query-Time Tradeoff for Computing the Visibility Polygon