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

Abstract

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
Pages46:1–46:8
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
https://eurocg2022.unipg.it/

Conference

ConferenceThe 38th European Workshop on Computational Geometry
Abbreviated titleEuroCG 2022
Country/TerritoryItaly
CityPerugia
Period14/03/2216/03/22
Internet address

Keywords

  • data structure
  • polygons
  • visibility
  • complexity

Fingerprint

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

Cite this