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: Contribution to conferencePaperAcademic


Let P be a simple polygon with n vertices, and let A be a set of m points or line segments in P. We develop data structures that efficiently count the objects in A that are visible to a query point or segment. We obtain fast, O(polylog nm), query times, while using as little space as possible, for all combinations of settings. In this abstract, we focus on the result where the query is a line segment and A contains only points, obtaining O(log n log nm) query time using only O(nm^{2+ε} + n²) space.
Original languageEnglish
Number of pages8
Publication statusPublished - 24 Mar 2022
EventThe 38th European Workshop on Computational Geometry - University of Perugia, Perugia, Italy
Duration: 14 Mar 202216 Mar 2022
Conference number: 38


ConferenceThe 38th European Workshop on Computational Geometry
Abbreviated titleEuroCG 2022
Internet address


  • data structure
  • polygons
  • visibility
  • complexity


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

Cite this