Buchumschlag

The Point-Boundary Art Gallery Problem is $\exists\mathbb{R}$-hard

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Stade, Jack
Format:	Preprint
Veröffentlicht:	2022
Schlagworte:	Computational Geometry
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Two Tiling is Undecidable
von: Stade, Jack
Veröffentlicht: (2025)

The Contiguous Art Gallery Problem is Solvable in Polynomial Time
von: Merrild, Magnus Christian Ring, et al.
Veröffentlicht: (2024)

The Analytic Arc Cover Problem and its Applications to Contiguous Art Gallery, Polygon Separation, and Shape Carving
von: Robson, Eliot W., et al.
Veröffentlicht: (2024)

Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares
von: Abrahamsen, Mikkel, et al.
Veröffentlicht: (2024)

Devil's Games and $\text{Q}\mathbb{R}$: Continuous Games complete for the First-Order Theory of the Reals
von: Meijer, Lucas, et al.
Veröffentlicht: (2025)

Simpler and Faster Contiguous Art Gallery
von: de Berg, Sarita, et al.
Veröffentlicht: (2025)

The Contiguous Art Gallery Problem is in Θ(n log n)
von: de Berg, Sarita, et al.
Veröffentlicht: (2025)

Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings
von: Abrahamsen, Mikkel, et al.
Veröffentlicht: (2024)

A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
von: Hengeveld, Simon, et al.
Veröffentlicht: (2020)

NP-membership for the boundary-boundary art-gallery problem
von: Stade, Jack
Veröffentlicht: (2025)

VF-Plan: Bridging the Art Gallery Problem and Static LiDAR Scanning with Visibility Field Optimization
von: Xiong, Biao, et al.
Veröffentlicht: (2025)

A Deterministic Bicriteria Approximation Algorithm for the Art Gallery Problem
von: Elbassioni, Khaled
Veröffentlicht: (2025)

Super Guarding and Dark Rays in Art Galleries
von: MIT CompGeom Group, et al.
Veröffentlicht: (2024)

Bounding a Polygon by a Minimum Number of Vertices
von: Abrahamsen, Mikkel, et al.
Veröffentlicht: (2025)

Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems
von: Abrahamsen, Mikkel, et al.
Veröffentlicht: (2020)

Recognition of Unit Segment and Polyline Graphs is $\exists\mathbb{R}$-Complete
von: Hoffmann, Michael, et al.
Veröffentlicht: (2024)

Geometric Thickness of Multigraphs is $\exists \mathbb{R}$-complete
von: Förster, Henry, et al.
Veröffentlicht: (2023)

Online Hitting of Unit Balls and Hypercubes in $\mathbb{R}^d$ using Points from $\mathbb{Z}^d$
von: De, Minati, et al.
Veröffentlicht: (2023)

The Euclidean $k$-Matching Problem is NP-hard
von: Díaz-Báñez, José-Miguel, et al.
Veröffentlicht: (2025)

Covering and Partitioning Complex Objects with Small Pieces
von: Aamand, Anders, et al.
Veröffentlicht: (2026)

Subquadratic Approximation Algorithms for Separating Two Points with Objects in the Plane
von: Lynch, Jayson, et al.
Veröffentlicht: (2025)

Colored Points Traveling Salesman Problem
von: Asaeedi, Saeed
Veröffentlicht: (2024)

Asymmetric Separation Problem for Bichromatic Point Set
von: Maji, Sukanya, et al.
Veröffentlicht: (2024)

Coresets for Farthest Point Problems in Hyperbolic Space
von: Park, Eunku, et al.
Veröffentlicht: (2025)

Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds
von: Spalding-Jamieson, Jack, et al.
Veröffentlicht: (2025)

On the existence of $L^p$-Optimal Transport maps for norms on $\mathbb{R}^N$
von: Liu, Guoxi, et al.
Veröffentlicht: (2024)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
von: Bartlmae, Simon, et al.
Veröffentlicht: (2024)

Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications
von: Aronov, Boris, et al.
Veröffentlicht: (2019)

Filming runners with drones is hard
von: Díaz-Báñez, José-Miguel, et al.
Veröffentlicht: (2024)

Subset Selection Problems in Planar Point Sets
von: Balogh, József, et al.
Veröffentlicht: (2024)

On the hardness of finding normal surfaces
von: Burton, Benjamin A., et al.
Veröffentlicht: (2019)

Online Geometric Hitting Set and Set Cover Beyond Unit Balls in $\mathbb{R}^2$
von: De, Minati, et al.
Veröffentlicht: (2023)

Dynamic Nearest-Neighbor Searching Under General Metrics in ${\mathbb R}^3$ and Its Applications
von: Agarwal, Pankaj K., et al.
Veröffentlicht: (2026)

An Algorithm for Illuminating $n$ Nonoverlapping Circular Discs' Boundaries on the Plane with Application to Tree Stem Illumination Problem
von: Sukkasem, Phapaengmuang, et al.
Veröffentlicht: (2025)

No Infinite $(p,q)$-Theorem for Piercing Compact Convex Sets with Lines in $\mathbb{R}^3$
von: Chakraborty, Sutanoya, et al.
Veröffentlicht: (2025)

Contiguous Boundary Guarding
von: Biniaz, Ahmad, et al.
Veröffentlicht: (2024)

Isoparametric Hypersurfaces of $\mathbb H^n\times\mathbb R$ and $\mathbb S^n\times\mathbb R$
von: de Lima, Ronaldo F., et al.
Veröffentlicht: (2024)

Dominating Set, Independent Set, Discrete $k$-Center, Dispersion, and Related Problems for Planar Points in Convex Position
von: Tkachenko, Anastasiia, et al.
Veröffentlicht: (2024)

On a Traveling Salesman Problem for Points in the Unit Cube
von: Balogh, József, et al.
Veröffentlicht: (2023)

On the Reduction of the Spherical Point-in-Polygon Problem for Antipode-Excluding Spherical Polygons
von: Li, Ziqiang, et al.
Veröffentlicht: (2023)