Fetching the paper…
Reading the bibliography…
In the MINIMUM CONVEX COVER (MCC) problem, we are given a simple polygon $\mathcal P$ and an integer $k$, and the question is if there exist $k$ convex polygons whose union is $\mathcal P$.
“A Universality Theorem for Nested Polytopes” Preprint, arxiv.org/abs/1908.02213 , 2019
Michael Dobbins, Andreas Holmsen and Tillmann Miltzow · 1908
Earlier work this paper cites.
“The Complexity of Positive Semidefinite Matrix Factorization”
Yaroslav Shitov · 1909
Earlier work this paper cites.
“Analysis of set patterns”
Theodosios Pavlidis · 1968
Earlier work this paper cites.
“Representation of figures by labeled graphs”
Theodosios Pavlidis · 1972
Earlier work this paper cites.
“Structural pattern recognition: Primitives and juxtaposition relations”
Theodosios Pavlidis · 1972
Earlier work this paper cites.
“Decomposition of polygons into simpler components: Feature generation for syntactic pattern recognition”
Hou-Yuan. Feng and Theodosios Pavlidis · 1975
Earlier work this paper cites.
“Structural Pattern Recognition” 1
Theodosios Pavlidis · 1977
Earlier work this paper cites.
“A review of algorithms for shape analysis”
Theodosios Pavlidis · 1978
Earlier work this paper cites.
“Computers and intractability: A Guide to the Theory of NP-Completeness”
Michael. Garey and David. Johnson · 1979
Earlier work this paper cites.
“The NP-completeness column: An ongoing guide”
David. Johnson · 1982
Earlier work this paper cites.
“The complexity of computing minimum convex covers for polygons”
Joseph O’Rourke · 1982
Earlier work this paper cites.
“Some NP-hard polygon decomposition problems”
Joseph O’Rourke and Kenneth. Supowit · 1983
Earlier work this paper cites.
“The art gallery theorem: Its variations, applications and algorithmic aspects”, 1984
Alok Aggarwal · 1984
Earlier work this paper cites.
“Field Extensions and Galois Theory”, Encyclopedia of Mathematics and its Applications
Julio. Bastida and Roger Lyndon · 1984
Earlier work this paper cites.
“Optimal convex decompositions”
Bernard Chazelle and David. Dobkin · 1985
Earlier work this paper cites.
“Minimum Decompositions of Polygonal Objects”
J. Keil and J“”org-R. Sack · 1985
Earlier work this paper cites.
“Computational complexity of art gallery problems”
D.. Lee and Arthur. Lin · 1986
Earlier work this paper cites.
“Approximation and decomposition of shapes”
Bernard Chazelle · 1987
Earlier work this paper cites.
“Art Gallery Theorems and Algorithms”
Joseph O’Rourke · 1987
Cited alongside, same era.
“Some Algebraic and Geometric Computations in PSPACE”
John Canny · 1988
Cited alongside, same era.
“The universality theorems on the classification problem of configuration varieties and convex polytopes varieties”
Nicolai Mn“”ev · 1988
Cited alongside, same era.
“Some provably hard crossing number problems”
Daniel Bienstock · 1991
Cited alongside, same era.
“Stretchability of pseudolines is NP-hard”
Peter. Shor · 1991
Cited alongside, same era.
“Recent results in art galleries”
Thomas. Shermer · 1992
Cited alongside, same era.
“Decomposition algorithms in geometry”
Jir“’ Matousek · 2014
Later among the works it cites.
“Computational Geometry Column 62”
Jean Cardinal · 2015
Later among the works it cites.
“Who Needs Crossings? Hardness of Plane Graph Rigidity”
Zachary Abel, Erik. Demaine, Martin. Demaine, Sarah Eisenstat, Jayson Lynch and Tao. Schardl · 2016
Later among the works it cites.
Yaroslav Shitov · 2016
Later among the works it cites.
“Recognition and complexity of point visibility graphs”
Jean Cardinal and Udo Hoffmann · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Bernard Chazelle and Leonidas Palios · 1994
Cited alongside, same era.
“Covering polygons is hard”
Joseph. Culberson and Robert. Reckhow · 1994
Cited alongside, same era.
“Realization spaces of 4-polytopes are universal”
J“”urgen Richter-Gebert and G“”unter. Ziegler · 1995
Cited alongside, same era.
“Polygon decomposition”
J. Keil · 1999
Cited alongside, same era.
“An approximation algorithm for minimum convex cover with logarithmic performance guarantee”
Stephan. Eidenbenz and Peter Widmayer · 2003
Cited alongside, same era.
“Complexity of some geometric and topological problems”
Marcus Schaefer · 2009
Cited alongside, same era.
Marcus Schaefer and Daniel Stefankovic · 2017
Later among the works it cites.
“Intersection Graphs of Rays and Grounded Segments”
Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins and Birgit Vogtenhuber · 2018
Later among the works it cites.
“ ∀ \forall ∃ \exists ℝ \mathbb{R} -Completeness and Area-Universality”
Michael Dobbins, Linda Kleist, Tillmann Miltzow and Pawel Rzazewski · 2018
Later among the works it cites.
“ ∃ \exists R-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria”
Jugal Garg, Ruta Mehta, Vijay. Vazirani and Sadra Yazdanbod · 2018
Later among the works it cites.
“The Complexity of Drawing a Graph in a Polygonal Region”
Anna Lubiw, Tillmann Miltzow and Debajyoti Mondal · 2018
Later among the works it cites.
“Polygons”
Joseph O’Rourke, Subash Suri and Csaba. T“’oth · 2018
Later among the works it cites.
“Part-Based Mesh Segmentation: A Survey”
Rui S.. Rodrigues, Jos“’e F.. Morgado and Abel Jo“˜ao“˜ao Gomes · 2018
Later among the works it cites.
“On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria”
Marie Louisalbll Berthelsen and Kristoffer Hansen · 2019
Later among the works it cites.
Jeff Erickson · 2019
Later among the works it cites.
“Framework for ∃ ℝ \exists\mathbb{R} -Completeness of Two-Dimensional Packing Problems”
Mikkel Abrahamsen, Tillmann Miltzow and Nadja Seiferth · 2020
Later among the works it cites.
“Smoothing the gap between NP and ER”
Jeff Erickson, Ivor van der Hoog and Tillmann Miltzow · 2020
Later among the works it cites.
“The Art Gallery Problem is ∃ ℝ \exists\mathbb{R} -Complete” To appear. Preliminary versions presented at STOC 2018 and SoCG 2017
Mikkel Abrahamsen, Anna Adamaszek and Tillmann Miltzow · 2021
Closest in time.