Space–Query-Time Tradeoff for Computing the Visibility Polygon

DOI10.1007/978-3-642-02270-8_14MaRDI QIDQ5321702zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Space/query-time tradeoff for computing the visibility polygon
• Visibility queries in a polygonal region
• Efficient visibility queries in simple polygons
• Time-space trade-off for finding the \(k\)-visibility region of a point in a polygon
• A space-time trade-off for computing the visibility polygon in the multi-pass model

Cites work

• scientific article; zbMATH DE number 4211552 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• An Optimal Algorithm for Computing Visibility in the Plane
• Construction of \(\epsilon\)-nets
• Cutting hyperplanes for divide-and-conquer
• Efficient computation of query point visibility in polygons with holes
• New applications of random sampling in computational geometry
• On the Zone Theorem for Hyperplane Arrangements
• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• THE VISIBILITY COMPLEX
• The power of geometric duality
• Visibility of disjoint polygons
• Visibility queries and maintenance in simple polygons

Cited in

(2)

• A space-time trade-off for computing the visibility polygon in the multi-pass model
• Space/query-time tradeoff for computing the visibility polygon

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

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