Segment Visibility Counting Queries in Polygons

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

Segment Visibility Counting Queries in Polygons

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

Algorithms

Research output: Contribution to conference › Paper › Academic

26 Downloads (Pure)

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 language	English
Pages	46:1–46:8
Number of pages	8
Publication status	Published - 24 Mar 2022
Event	38th European Workshop on Computational Geometry (EuroCG 2022) - University of Perugia, Perugia, Italy Duration: 14 Mar 2022 → 16 Mar 2022 Conference number: 38 https://eurocg2022.unipg.it/

Workshop

Workshop	38th European Workshop on Computational Geometry (EuroCG 2022)
Abbreviated title	EuroCG 2022
Country/Territory	Italy
City	Perugia
Period	14/03/22 → 16/03/22
Internet address	https://eurocg2022.unipg.it/

Keywords

data structure
polygons
visibility
complexity

Access to Document

pdfFinal published version, 1.83 MB

https://eurocg2022.unipg.it/booklet/EuroCG2022-Booklet.pdfLicence: Unspecified

1 Conference contribution
1 Phd Thesis 1 (Research TU/e / Graduation TU/e)

Algorithms for Imprecise Trajectories
Popov, A. A., 12 Oct 2023, Eindhoven: Eindhoven University of Technology. 259 p.
Research output: Thesis › Phd Thesis 1 (Research TU/e / Graduation TU/e)

Open Access
File
Segment Visibility Counting Queries in Polygons
Buchin, K., Custers, B., van der Hoog, I., Löffler, M., Popov, A., Roeloffzen, M. & Staals, F., 14 Dec 2022, 33rd International Symposium on Algorithms and Computation, ISAAC 2022. Bae, S. W. & Park, H. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 58:1-58:16 16 p. 58. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 248).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Open Access
File
1 Link opens in a new tab Citation (Scopus)

10 Downloads (Pure)

Cite this

@conference{6441d2add54d4720b5231aeef18dd49c,

title = "Segment Visibility Counting Queries in Polygons",

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\textasciicircum{}\{2+ε\} + n²) space.",

keywords = "data structure, polygons, visibility, complexity",

author = "Kevin Buchin and Bram Custers and \{van der Hoog\}, Ivor and Maarten L{\"o}ffler and Aleksandr Popov and Marcel Roeloffzen and Frank Staals",

year = "2022",

month = mar,

day = "24",

language = "English",

pages = "46:1{\textendash}46:8",

note = "38th European Workshop on Computational Geometry (EuroCG 2022), EuroCG 2022 ; Conference date: 14-03-2022 Through 16-03-2022",

url = "https://eurocg2022.unipg.it/",

}

TY - CONF

T1 - Segment Visibility Counting Queries in Polygons

AU - Buchin, Kevin

AU - Custers, Bram

AU - van der Hoog, Ivor

AU - Löffler, Maarten

AU - Popov, Aleksandr

AU - Roeloffzen, Marcel

AU - Staals, Frank

N1 - Conference code: 38

PY - 2022/3/24

Y1 - 2022/3/24

N2 - 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.

AB - 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.

KW - data structure

KW - polygons

KW - visibility

KW - complexity

M3 - Paper

SP - 46:1–46:8

T2 - 38th European Workshop on Computational Geometry (EuroCG 2022)

Y2 - 14 March 2022 through 16 March 2022

ER -

Segment Visibility Counting Queries in Polygons

Abstract

Workshop

Keywords

Access to Document

Fingerprint

Research output

Algorithms for Imprecise Trajectories

Segment Visibility Counting Queries in Polygons

Cite this