An Improved Constant-Factor Approximation Algorithm for Planar Visibility Counting Problem

DOI10.1007/978-3-319-42634-1_17MaRDI QIDQ2817863zbMATH OpenOpenAlexFDO

Authors Sharareh Alipour, Mohammad Ghodsi, Amir Jafari

Publication date 2 September 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

graph theoryrandomized algorithmapproximation algorithmcomputational geometryvisibility

Mathematics Subject Classification ID

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

Abstract: Given a set $S$ of $n$ disjoint line segments in $mathbb{R}^2$, the visibility counting problem (VCP) is to preprocess $S$ such that the number of segments in $S$ visible from any query point $p$ can be computed quickly. This problem can trivially be solved in logarithmic query time using $O(n^4)$ preprocessing time and space. Gudmundsson and Morin proposed a 2-approximation algorithm for this problem with a tradeoff between the space and the query time. They answer any query in $O_{epsilon}(n^{1-alpha})$ with $O_{epsilon}(n^{2+2alpha})$ of preprocessing time and space, where $alpha$ is a constant $0leqalphaleq1$, $epsilon>0$ is another constant that can be made arbitrarily small, and $O_{epsilon}(f(n))=O(f(n)n^{epsilon})$. In this paper, we propose a randomized approximation algorithm for VCP with a tradeoff between the space and the query time. We will show that for an arbitrary constants $$ and $0<delta<1$, the expected preprocessing time, the expected space, and the query time of our algorithm are $$, $$, and $$, respectively. The algorithm computes the number of visible segments from $p$, or $m_p$, exactly if $$. Otherwise, it computes a $(1+delta)$-approximation $m{\text{'}}_p$ with the probability of at least $1-frac1logn$, where $m_{p}leqm{\text{'}}_{p}leq(1+delta)m_p$.

Recommendations

• Randomized approximation algorithms for planar visibility counting problem
• An Optimal Algorithm for Computing Visibility in the Plane
• scientific article; zbMATH DE number 177568
• scientific article; zbMATH DE number 3978410
• An efficient algorithm for the 1D total visibility-index problem
• A new algorithm for computing visibility graphs of polygonal obstacles in the plane
• A unified approach to visibility representations of planar graphs
• An optimal visibility graph algorithm for triangulated simple polygons
• An efficient algorithm for the 1D total visibility-index problem and its parallelization

Cites work

• An Output-Sensitive Algorithm for Computing Visibility Graphs
• Efficient visibility queries in simple polygons
• Optimal Search in Planar Subdivisions
• Planar visibility, testing and counting
• Query point visibility computation in polygons with holes
• Space/query-time tradeoff for computing the visibility polygon
• THE VISIBILITY COMPLEX
• Visibility Algorithms in the Plane
• Visibility queries and maintenance in simple polygons
• Visibility testing and counting

Cited in

(5)

• Visibility testing and counting
• Randomized approximation algorithms for planar visibility counting problem
• Planar visibility, testing and counting
• Visibility testing and counting for uncertain segments
• Visibility testing and counting

This page was built for publication: An Improved Constant-Factor Approximation Algorithm for Planar Visibility Counting Problem

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