A time-space trade-off for computing the \(k\)-visibility region of a point in a polygon

DOI10.1016/j.tcs.2018.06.017zbMath1430.68356MaRDI QIDQ2272372

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

Publication date: 10 September 2019

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

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

zbMATH Keywords

time-space trade-off; \(k\)-visibility region; limited workspace model

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

Cites Work

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