NP-completeness of chromatic orthogonal art gallery problem
The chromatic orthogonal art gallery problem is a well-known problem in the computational
geometry. Two points in an orthogonal polygon P see each other if there is an axis-aligned …
geometry. Two points in an orthogonal polygon P see each other if there is an axis-aligned …
Computational complexity of the chromatic art gallery problem for orthogonal polygons
C Iwamoto, T Ibusuki - International Workshop on Algorithms and …, 2020 - Springer
The art gallery problem is to find a set of guards who together can observe every point of the
interior of a polygon P. We study a chromatic variant of the problem, where each guard is …
interior of a polygon P. We study a chromatic variant of the problem, where each guard is …
[HTML][HTML] Coloring polygon visibility graphs and their generalizations
Curve pseudo-visibility graphs generalize polygon and pseudo-polygon visibility graphs and
form a hereditary class of graphs. We prove that every curve pseudo-visibility graph with …
form a hereditary class of graphs. We prove that every curve pseudo-visibility graph with …
Vertex-to-Point Conflict-Free Chromatic Guarding is NP-Hard
C Iwamoto, T Ibusuki - … Conference and Workshops on Algorithms and …, 2022 - Springer
The art gallery problem is to find a set of guards who together can observe every point of the
interior of a polygon P. We study a chromatic variant of the problem, where each guard is …
interior of a polygon P. We study a chromatic variant of the problem, where each guard is …
Computational Complexity of the Vertex-to-Point Conflict-Free Chromatic Art Gallery Problem
C Iwamoto, T Ibusuki - IEICE TRANSACTIONS on Information and …, 2023 - search.ieice.org
The art gallery problem is to find a set of guards who together can observe every point of the
interior of a polygon P. We study a chromatic variant of the problem, where each guard is …
interior of a polygon P. We study a chromatic variant of the problem, where each guard is …
[PDF][PDF] Conflict-free Colouring of Polygons
B Roy - Outline of Lectures, 2024 - events.iitbhilai.ac.in
In general, conflict-free colouring of a graph is assigning colours to vertices of that graph
such that the neighborhood of each vertex contains at least one unique colour. This problem …
such that the neighborhood of each vertex contains at least one unique colour. This problem …
[PDF][PDF] Conflict-Free Chromatic Guarding of Orthogonal Polygons with Sliding Cameras
Y Bahoo, O Cagırıcı, K Manastyrski, RI Nishat, C Kolios… - gc.cs.ryerson.ca
In conflict-free chromatic guarding of a polygon, every guard is assigned a color such that
every point in the polygon, including the points on the boundaries, must see at least one …
every point in the polygon, including the points on the boundaries, must see at least one …
[PDF][PDF] Conflict-free guarding problems in the plane
S ČEPELA - is.muni.cz
The Art gallery problem is a famous result in computational geometry, asking for the
minimum number of guards needed to guard an art gallery. In this thesis, we will focus on a …
minimum number of guards needed to guard an art gallery. In this thesis, we will focus on a …
Chromatic Art Gallery Problem with r-Visibility is NP-Complete
C Iwamoto, T Ibusuki - IEICE Transactions on Fundamentals of …, 2021 - search.ieice.org
The art gallery problem is to find a set of guards who together can observe every point of the
interior of a polygon P. We study a chromatic variant of the problem, where each guard is …
interior of a polygon P. We study a chromatic variant of the problem, where each guard is …
[PDF][PDF] Computational Aspects of Problems on Visibility and Disk Graph Representations.
O Qagirici - CoRR, 2021 - is.muni.cz
This thesis focuses on two concepts which are widely studied in the field of computational
geometry. Namely, visibility and unit disk graphs. In the field of visibility, we have studied the …
geometry. Namely, visibility and unit disk graphs. In the field of visibility, we have studied the …