Fetching the paper…
Reading the bibliography…
In the Art Gallery Problem we are given a polygon $P\subset [0,L]^2$ on $n$ vertices and a number $k$.
Discrete dynamic programming and capital allocation
G. L. Nemhauser and Z. Ullmann · 1969
Earlier work this paper cites.
How good is the simplex algorithm
V. Klee and G. J. Minty · 1970
Earlier work this paper cites.
A combinatorial theorem in plane geometry
V. Chvátal · 1975
Earlier work this paper cites.
A short proof of Chvátal’s watchman theorem
S. Fisk · 1978
Earlier work this paper cites.
An optimal algorithm for finding the kernel of a polygon
D.-T. Lee and F. P. Preparata · 1979
Earlier work this paper cites.
The art gallery theorem: its variations, applications and algorithmic aspects
A. Aggarwal · 1984
Earlier work this paper cites.
Computational complexity of art gallery problems
D.-T. Lee and A. K. Lin · 1986
Earlier work this paper cites.
Art Gallery Theorems and Algorithms
J. O’Rourke · 1987
Earlier work this paper cites.
The intrinsic spread of a configuration in ℝ d \mathbb{R}^{d}
J. E. Goodman, R. Pollack, and B. Sturmfels · 1990
Earlier work this paper cites.
Computing two-covers of simple polygons
P. Belleville · 1991
Earlier work this paper cites.
String graphs requiring exponential representations
J. Kratochvíl and J. Matoušek · 1991
Earlier work this paper cites.
Stretchability of pseudolines is np-hard
P. Shor · 1991
Earlier work this paper cites.
Two-guarding simple polygons
P. Belleville · 1992
Earlier work this paper cites.
An optimal algorithm for computing visibility in the plane
P. J. Heffernan and J. S. Mitchell · 1995
Earlier work this paper cites.
Realization spaces of 4-polytopes are universal
J. Richter-Gebert and G. M. Ziegler · 1995
Earlier work this paper cites.
Two NP-hard art-gallery problems for ortho-polygons
D. Schuchardt and H. Hecker · 1995
Earlier work this paper cites.
Computational geometry in C
J. O’Rourke · 1998
Earlier work this paper cites.
Inapproximability results for guarding polygons and terrains
S. Eidenbenz, C. Stamm, and P. Widmayer · 2001
Earlier work this paper cites.
Recognizing string graphs is decidable
J. Pach and G. Tóth · 2001
Earlier work this paper cites.
Guarding galleries and terrains
A. Efrat and S. Har-Peled · 2002
Earlier work this paper cites.
Recognizing string graphs is decidable
J. Pach and G. Tóth · 2002
Earlier work this paper cites.
Recognizing string graphs in NP
M. Schaefer, E. Sedgwick, and D. Stefankovic · 2002
Earlier work this paper cites.
Random knapsack in expected polynomial time
R. Beier and B. Vöcking · 2003
Earlier work this paper cites.
Recognizing string graphs in NP
M. Schaefer, E. Sedgwick, and D. Štefankovič · 2003
Cited alongside, same era.
Visibility
J. O’Rourke · 2004
Cited alongside, same era.
Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
D. A. Spielman and S.-H. Teng · 2004
Cited alongside, same era.
Worst-case and smoothed analysis of the icp algorithm, with an application to the k-means method
D. Arthur and S. Vassilvitskii · 2006
Cited alongside, same era.
Algorithms in real algebraic geometry
S. Basu, R. Pollack, and M.-F. Roy · 2006
Cited alongside, same era.
Typical properties of winners and losers in discrete optimization
R. Beier and B. Vöcking · 2006
Cited alongside, same era.
Intersection graphs of segments and ∃ ℝ \exists\mathbb{R}
J. Matoušek · 2014
Later among the works it cites.
ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
J. Garg, R. Mehta, V. V. Vazirani, and S. Yazdanbod · 2015
Later among the works it cites.
Parameterized hardness of art gallery problems
É. Bonnet and T. Miltzow · 2016
Later among the works it cites.
Engineering art galleries
P. J. de Rezende, C. C. de Souza, S. Friedrichs, M. Hemmer, A. Kröller, and D. C. Tozoni · 2016
Later among the works it cites.
Smoothed complexity of convex hulls by witnesses and collectors
O. Devillers, M. Glisse, X. Goaoc, and R. Thomasse · 2016
Later among the works it cites.
The continuous 1.5D terrain guarding problem: Discretization, optimal solutions, and PTAS
S. Friedrichs, M. Hemmer, J. King, and C. Schmidt · 2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Guarding galleries and terrains
A. Efrat and S. Har-Peled · 2006
Cited alongside, same era.
How much precision is needed to compare two sums of square roots of integers?
J. Qian and C. A. Wang · 2006
Cited alongside, same era.
Worst case and probabilistic analysis of the 2-opt algorithm for the tsp
M. Englert, H. Röglin, and B. Vöcking · 2007
Cited alongside, same era.
A nearly optimal sensor placement algorithm for boundary coverage
A. Bottino and A. Laurentini · 2008
Cited alongside, same era.
Experimental evaluation of an exact algorithm for the orthogonal art gallery problem
M. C. Couto, C. C. De Souza, and P. J. De Rezende · 2008
Cited alongside, same era.
Locating guards for visibility coverage of polygons
Y. Amit, J. S. Mitchell, and E. Packer · 2010
Cited alongside, same era.
A universality theorem for nonnegative matrix factorizations
Y. Shitov · 2016
Later among the works it cites.
Irrational guards are sometimes needed
M. Abrahamsen, A. Adamaszek, and T. Miltzow · 2017
Later among the works it cites.
Constant approximation algorithms for guarding simple polygons using vertex guards
P. Bhattacharya, S. K. Ghosh, and S. P. Pal · 2017
Later among the works it cites.
An approximation algorithm for the art gallery problem
É. Bonnet and T. Miltzow · 2017
Later among the works it cites.
Recognition and complexity of point visibility graphs
J. Cardinal and U. Hoffmann · 2017
Later among the works it cites.
Smoothed analysis of local search for the maximum-cut problem
M. Etscheid and H. Röglin · 2017
Later among the works it cites.
Fixed points, Nash equilibria, and the existential theory of the reals
M. Schaefer and D. Štefankovič · 2017
Later among the works it cites.
The art gallery problem is ∃ ℝ \exists\mathbb{R} -complete
M. Abrahamsen, A. Adamaszek, and T. Miltzow · 2018
Closest in time.
Intersection graphs of rays and grounded segments
J. Cardinal, S. Felsner, T. Miltzow, C. Tompkins, and B. Vogtenhuber · 2018
Closest in time.
A friendly smoothed analysis of the simplex method
D. Dadush and S. Huiberts · 2018
Closest in time.
∀ ∃ ℝ \forall\exists\mathbb{R} -completeness and area-universality
M. G. Dobbins, L. Kleist, T. Miltzow, and P. Rza̧żewski · 2018
Closest in time.
The complexity of drawing a graph in a polygonal region
A. Lubiw, T. Miltzow, and D. Mondal · 2018
Closest in time.
Problem 33: Sum of square roots
J. O’Rourke · 2018
Closest in time.
Minicourse on smoothed analysis
H. Röglin · 2018
Closest in time.
Smoothed Complexity and Pseudopolynomial-Time Algorithms
T. Roughgarden · 2018
Closest in time.
Beyond worst-case analysis
T. Roughgarden · 2018
Closest in time.