Randomized approximation algorithms for planar visibility counting problem

DOI10.1016/j.tcs.2017.10.009zbMath1383.68088OpenAlexW2767016274MaRDI QIDQ1685962

Mohammad Ghodsi, Sharareh Alipour, A. H. Jafari

Publication date: 20 December 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.10.009

zbMATH Keywords

approximation algorithmgraph theoryrandomized algorithmvisibilitycomputational geometry

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Visibility testing and counting for uncertain segments

Cites Work

• Visibility queries and maintenance in simple polygons
• Efficient visibility queries in simple polygons
• Space/query-time tradeoff for computing the visibility polygon
• An Improved Constant-Factor Approximation Algorithm for Planar Visibility Counting Problem
• Visibility Testing and Counting
• Optimal Search in Planar Subdivisions
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• Graphics in flatland revisited
• The visibility diagram: A data structure for visibility problems and motion planning
• Efficient computation of query point visibility in polygons with holes
• Planar visibility
• Visibility Algorithms in the Plane
• THE VISIBILITY COMPLEX