Time-space trade-off for finding the k-visibility region of a point in a polygon

DOI10.1007/978-3-319-53925-6_24zbMATH Open1430.68355arXiv1603.02853OpenAlexW2950036238MaRDI QIDQ2980918FDOQ2980918

Authors: Yeganeh Bahoo, Bahareh Banyassady, Prosenjit Bose, Stephane Durocher, Wolfgang Mulzer 

Publication date: 5 May 2017

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Abstract: Let $P$ be a simple polygon with $n$ vertices, and let $qinP$ be a point in $P$. Let $kin0,dots,n-1$. A point $pinP$ is $k$-visible from $q$ if and only if the line segment $pq$ crosses the boundary of $P$ at most $k$ times. The $k$-visibility region of $q$ in $P$ is the set of all points that are $k$-visible from $q$. We study the problem of computing the $k$-visibility region in the limited workspace model, where the input resides in a random-access read-only memory of $O(n)$ words, each with $Omega(logn)$ bits. The algorithm can read and write $O(s)$ additional words of workspace, where $sinmathbbN$ is a parameter of the model. The output is written to a write-only stream. Given a simple polygon $P$ with $n$ vertices and a point $qinP$, we present an algorithm that reports the $k$-visibility region of $q$ in $P$ in $O(cn/s+clogs+minlceilk/sceiln,nloglo{g}_{s}n)$ expected time using $O(s)$ words of workspace. Here, $cin1,dots,n$ is the number of critical vertices of $P$ for $q$ where the $k$-visibility region of $q$ may change. We generalize this result for polygons with holes and for sets of non-crossing line segments.

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

Recommendations

• A time-space trade-off for computing the \(k\)-visibility region of a point in a polygon
• Computing the \(k\)-visibility region of a point in a polygon
• Space/query-time tradeoff for computing the visibility polygon
• A space-time trade-off for computing the visibility polygon in the multi-pass model
• Computing the visibility polygon using few variables

zbMATH Keywords

time-space trade-off\(k\)-visibility regionmemory-constrained model

Mathematics Subject Classification ID

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

Cites Work

• Intersecting convex sets by rays
• Visibility Algorithms in the Plane
• Comparison-based time-space lower bounds for selection
• Selection from read-only memory and sorting with minimum data movement
• Multi-pass geometric algorithms
• Corrections to Lee's visibility polygon algorithm
• Further Results on Bar k-Visibility Graphs
• Computing a visibility polygon using few variables
• Parameters of Bar k-Visibility Graphs
• Modem illumination of monotone polygons
• Coverage with \(k\)-transmitters in the presence of obstacles
• Memory-constrained algorithms for simple polygons
• Space-time trade-offs for stack-based algorithms
• Guard placement for efficient point-in-polygon proofs
• Recognizing polygons, or how to spy
• Graph Drawing
• A hybrid metaheuristic strategy for covering with wireless devices

Cited In (7)

• A time-space trade-off for computing the \(k\)-visibility region of a point in a polygon
• Computing the visibility polygon using few variables
• Computing the \(k\)-visibility region of a point in a polygon
• Space–Query-Time Tradeoff for Computing the Visibility Polygon
• A space-time trade-off for computing the visibility polygon in the multi-pass model
• Computing the \(k\)-crossing visibility region of a point in a polygon
• Space/query-time tradeoff for computing the visibility polygon

This page was built for publication: Time-space trade-off for finding the \(k\)-visibility region of a point in a polygon

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