7 citations · 11 across the 5 of their papers we have counts for
7 papers
Covering points by hyperplanes and related problems
Zuzana Patáková, Micha Sharir
For a set of points in , for any , a hyperplane is called -rich with respect to if it contains at least points of . Answering and gen…
Shellability is NP-complete
Xavier Goaoc, Pavel Paták, Zuzana Patáková +2
We prove that for every , deciding if a pure, -dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Dan…
On Generalized Heawood Inequalities for Manifolds: a van Kampen--Flores-type Nonembeddability Result
Xavier Goaoc, and Isaac Mabillard, Pavel Paták +3
The fact that the complete graph does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood proble…
A Direct Proof of the Strong Hanani-Tutte Theorem on the Projective Plane
Éric Colin de Verdière, Vojtěch Kaluža, Pavel Paták +2
We reprove the strong Hanani-Tutte theorem on the projective plane. In contrast to the previous proof by Pelsmajer, Schaefer and Stasi, our method is constructive and does not rely…
On the nonexistence of -reptile simplices in and
Jan Kynčl, Zuzana Patáková
A -dimensional simplex is called a -reptile (or a -reptile simplex) if it can be tiled by simplices with disjoint interiors that are all mutually congruent and sim…
Multilevel polynomial partitions and simplified range searching
Jiri Matousek, Zuzana Patakova
The polynomial partitioning method of Guth and Katz [arXiv:1011.4105] has numerous applications in discrete and computational geometry. It partitions a given -point set $P\subse…
Bounds for Pach's selection theorem and for the minimum solid angle in a simplex
Roman Karasev, Jan Kynčl, Pavel Paták +2
We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer there is a constant such that whenever $X_1,..., X…