Segment Visibility Counting Queries in Polygons

Kevin Buchin, Bram Custers, Ivor van der Hoog, Maarten Löffler, Aleksandr Popov, Marcel Roeloffzen, Frank Staals

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


Let P be a simple polygon with n vertices, and let A be a set of m points or line segments inside P. We develop data structures that can efficiently count the objects from A that are visible to a query point or a query segment. Our main aim is to obtain fast, O(polylog nm), query times, while using as little space as possible.
In case the query is a single point, a simple visibility-polygon-based solution achieves O(log nm) query time using O(nm²) space. In case A also contains only points, we present a smaller, O(n + m2+ε log n)-space, data structure based on a hierarchical decomposition of the polygon.
Building on these results, we tackle the case where the query is a line segment and A contains only points. The main complication here is that the segment may intersect multiple regions of the polygon decomposition, and that a point may see multiple such pieces. Despite these issues, we show how to achieve O(log n log nm) query time using only O(nm2+ε + n²) space. Finally, we show that we can even handle the case where the objects in A are segments with the same bounds.
Original languageEnglish
Title of host publication33rd International Symposium on Algorithms and Computation, ISAAC 2022
Subtitle of host publicationISAAC 2022
EditorsSang Won Bae, Heejin Park
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages16
ISBN (Electronic)978-3-95977-258-7
Publication statusPublished - 14 Dec 2022
Event33rd International Symposium on Algorithms and Computation - Hanyang University, Seoul, Korea, Republic of
Duration: 19 Dec 202221 Dec 2022
Conference number: 33

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference33rd International Symposium on Algorithms and Computation
Abbreviated titleISAAC 2022
Country/TerritoryKorea, Republic of
Internet address


  • visibility
  • data structure
  • polygons
  • complexity
  • Visibility
  • Data Structure
  • Complexity
  • Polygons


Dive into the research topics of 'Segment Visibility Counting Queries in Polygons'. Together they form a unique fingerprint.

Cite this