scientific article; zbMATH DE number 7236415
From MaRDI portal
Publication:5115778
DOI10.4230/LIPIcs.SoCG.2018.11zbMath1489.68341arXiv1710.00386MaRDI QIDQ5115778
Édouard Bonnet, Panos Giannopoulos
Publication date: 18 August 2020
Full work available at URL: https://arxiv.org/abs/1710.00386
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for maximum independent set of pseudo-disks
- Improved approximations for guarding 1.5-dimensional terrains
- Improved results on geometric hitting set problems
- Improved approximation for guarding simple galleries from the perimeter
- Guarding galleries and terrains
- Improved approximation algorithms for geometric set cover
- Which problems have strongly exponential complexity?
- An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
- Approximate guarding of monotone and rectilinear polygons
- Guarding terrains via local search
- Terrain Guarding is NP-Hard
- A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
- A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
- Planar Formulae and Their Uses
- Finding Small Hitting Sets in Infinite Range Spaces of Bounded VC-Dimension
- Parameterized Hardness of Art Gallery Problems
- A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
- On the complexity of \(k\)-SAT
- Inapproximability results for guarding polygons and terrains
This page was built for publication:
