2018
Embeddability in the 3-Sphere Is Decidable.
J. ACM, 2018
2016
A zero-player graph game in NP $\cap$ coNP.
CoRR, 2016
2015
Multilevel Polynomial Partitions and Simplified Range Searching.
Discret. Comput. Geom., 2015
Three-Monotone Interpolation.
Discret. Comput. Geom., 2015
Simplifying Inclusion-Exclusion Formulas.
Comb. Probab. Comput., 2015
Combinatorial Discrepancy for Boxes via the gamma_2 Norm.
Proceedings of the 31st International Symposium on Computational Geometry, 2015
2014
Lower Bounds on Geometric Ramsey Functions.
SIAM J. Discret. Math., 2014
Polynomial-Time Computation of Homotopy Groups and Postnikov Systems in Fixed Dimension.
SIAM J. Comput., 2014
Computing All Maps into a Sphere.
J. ACM, 2014
On Gromov's Method of Selecting Heavily Covered Points.
Discret. Comput. Geom., 2014
Extendability of Continuous Maps Is Undecidable.
Discret. Comput. Geom., 2014
Near-Optimal Separators in String Graphs.
Comb. Probab. Comput., 2014
Factorization Norms and Hereditary Discrepancy.
CoRR, 2014
Intersection graphs of segments and ∃ℝ.
CoRR, 2014
Curves in Rd intersecting every hyperplane at most d + 1 times.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014
String graphs and separators.
Proceedings of the Geometry, Structure and Randomness in Combinatorics, 2014
2013
On Range Searching with Semialgebraic Sets. II.
SIAM J. Comput., 2013
Polynomial-Time Homology for Simplicial Eilenberg-MacLane Spaces.
Found. Comput. Math., 2013
Computing higher homotopy groups is W[1]-hard
CoRR, 2013
String graphs and separators.
CoRR, 2013
Extending continuous maps: polynomiality and undecidability.
Proceedings of the Symposium on Theory of Computing Conference, 2013
Untangling Two Systems of Noncrossing Curves.
Proceedings of the Graph Drawing - 21st International Symposium, 2013
On Lipschitz Mappings Onto a Square.
Proceedings of the Mathematics of Paul Erdős I, 2013
2012
A Geometric Proof of the Colored Tverberg Theorem.
Discret. Comput. Geom., 2012
Simple Proofs of Classical Theorems in Discrete Geometry via the Guth-Katz Polynomial Partitioning Technique.
Discret. Comput. Geom., 2012
Unit Distances in Three Dimensions.
Comb. Probab. Comput., 2012
Reachability by paths of bounded curvature in a convex polygon.
Comput. Geom., 2012
Minimum and maximum against k lies.
Chic. J. Theor. Comput. Sci., 2012
Higher-order Erdos-Szekeres theorems.
Proceedings of the 28th ACM Symposium on Computational Geometry, 2012
2011
A Doubly Exponentially Crumbled Cake.
Electron. Notes Discret. Math., 2011
On the Nonexistence of <i>k</i>-reptile Tetrahedra.
Discret. Comput. Geom., 2011
The <i>t</i>-Pebbling Number is Eventually Linear in <i>t</i>.
Electron. J. Comb., 2011
2010
Stabbing Simplices by Points and Flats.
Discret. Comput. Geom., 2010
Distance k-sectors exist.
Comput. Geom., 2010
Minimum and Maximum against <i>k</i> Lies.
Proceedings of the Algorithm Theory, 2010
Zone diagrams in Euclidean spaces and in other normed spaces.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010
Distance <i>k</i>-sectors exist.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010
2009
Dimension Gaps between Representability and Collapsibility.
Discret. Comput. Geom., 2009
Removing Degeneracy in LP-Type Problems Revisited.
Discret. Comput. Geom., 2009
Blocking Visibility for Points in General Position.
Discret. Comput. Geom., 2009
Computing D-convex hulls in the plane.
Comput. Geom., 2009
Hardness of embedding simplicial complexes in <i>R</i><sup>d</sup>.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009
Lower bounds for weak epsilon-nets and stair-convexity.
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009
Invitation to Discrete Mathematics (2. ed.).
Oxford University Press, ISBN: 978-0-19-857042-4, 2009
2008
On variants of the Johnson-Lindenstrauss lemma.
Random Struct. Algorithms, 2008
Violator spaces: Structure and algorithms.
Discret. Appl. Math., 2008
Graph Colouring with No Large Monochromatic Components.
Comb. Probab. Comput., 2008
Hardness of embedding simplicial complexes in R<sup>d</sup>
CoRR, 2008
LC reductions yield isomorphic simplicial complexes.
Contributions Discret. Math., 2008
Inapproximability for Metric Embeddings into R^d.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
2007
Removing Degeneracy May Require a Large Dimension Increase.
Theory Comput., 2007
Quadratically Many Colorful Simplices.
SIAM J. Discret. Math., 2007
Online Conflict-Free Coloring for Intervals.
,
,
,
,
,
,
,
,
,
,
SIAM J. Comput., 2007
Zone Diagrams: Existence, Uniqueness, and Algorithmic Challenge.
SIAM J. Comput., 2007
Induced trees in triangle-free graphs.
Electron. Notes Discret. Math., 2007
Removing degeneracy may require unbounded dimension increase.
Electron. Notes Discret. Math., 2007
How many points can be reconstructed from k projections?
Electron. Notes Discret. Math., 2007
Large Monochromatic Components in Two-colored Grids.
Electron. Notes Discret. Math., 2007
Graph coloring with no large monochromatic components.
Electron. Notes Discret. Math., 2007
Packing Cones and Their Negatives in Space.
Discret. Comput. Geom., 2007
Understanding and using linear programming.
Universitext, Springer, ISBN: 978-3-540-30697-9, 2007
2006
Segmenting object space by geometric reference structures.
ACM Trans. Sens. Networks, 2006
Berge's theorem, fractional Helly, and art galleries.
Discret. Math., 2006
k-Sets in Four Dimensions.
Discret. Comput. Geom., 2006
The Minimum Independence Number of a Hasse Diagram.
Comb. Probab. Comput., 2006
Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness.
Electron. J. Comb., 2006
The Number Of Unique-Sink Orientations of the Hypercube*.
Comb., 2006
The distance trisector curve.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006
2005
The Randomized Integer Convex Hull.
Discret. Comput. Geom., 2005
Discrepancy After Adding A Single Set.
Comb., 2005
Towards asymptotic optimality in probabilistic packet marking.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005
Online conflict-free coloring for intervals.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005
2004
Low-Distortion Embeddings of Finite Metric Spaces.
Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004
Crossing number, pair-crossing number, and expansion.
J. Comb. Theory B, 2004
Triangles in random graphs.
Discret. Math., 2004
New Constructions of Weak epsilon-Nets.
Discret. Comput. Geom., 2004
Bounded VC-Dimension Implies a Fractional Helly Theorem.
Discret. Comput. Geom., 2004
No Helly Theorem for Stabbing Translates by Lines in R <sup>3</sup>.
Discret. Comput. Geom., 2004
The One-Round Voronoi Game.
Discret. Comput. Geom., 2004
A Combinatorial Proof of Kneser's Conjecture.
Comb., 2004
Expected Length of the Longest Common Subsequence for Large Alphabets.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004
Nonexistence of 2-Reptile Simplices.
Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2004
Random Edge Can Be Exponential on Abstract Cubes.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004
2003
On restricted min-wise independence of permutations.
Random Struct. Algorithms, 2003
Low-Distortion Embeddings of Trees.
J. Graph Algorithms Appl., 2003
A Lower Bound on the Size of Lipschitz Subsets in Dimension 3.
Comb. Probab. Comput., 2003
New constructions of weak epsilon-nets.
Proceedings of the 19th ACM Symposium on Computational Geometry, 2003
2002
Random lifts of graphs: Independence and chromatic number.
Random Struct. Algorithms, 2002
A Lower Bound for Weak epsilon-Nets in High Dimension.
Discret. Comput. Geom., 2002
Equipartition of Two Measures by a 4-Fan.
Discret. Comput. Geom., 2002
Separating an object from its cast.
Comput. Aided Des., 2002
Transversal numbers for hypergraphs arising in geometry.
Adv. Appl. Math., 2002
Lectures on discrete geometry.
Graduate texts in mathematics 212, Springer, ISBN: 978-0-387-95373-1, 2002
Diskrete Mathematik - eine Entdeckungsreise (korrigierter Nachdruck).
Springer-Lehrbuch, Springer, ISBN: 978-3-540-42386-7, 2002
2001
A Lower Bound for Families of Natarajan Dimension d.
J. Comb. Theory A, 2001
Transversals of hypergraphs with geometric flavor.
Electron. Notes Discret. Math., 2001
Lower bound on the minus-domination number.
Discret. Math., 2001
Lower Bounds on the Transversal Numbers of <i>d</i>-Intervals.
Discret. Comput. Geom., 2001
On Directional Convexity.
Discret. Comput. Geom., 2001
Simultaneous Partitions of Measures by <i>k</i>-Fans.
Discret. Comput. Geom., 2001
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001
2000
On the Linear and Hereditary Discrepancies.
Eur. J. Comb., 2000
On Approximate Geometric k-Clustering.
Discret. Comput. Geom., 2000
On the Signed Domination in Graphs.
Comb., 2000
Reachability by paths of bounded curvature in convex polygons.
Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000
Derandomization in Computational Geometry.
Proceedings of the Handbook of Computational Geometry, 2000
1999
Product Range Spaces, Sensitive Sampling, and Derandomization.
SIAM J. Comput., 1999
Almost-Tiling the Plane by Ellipses.
Discret. Comput. Geom., 1999
The Anatomy of a Geometric Algorithm.
Proceedings of the Graph Drawing, 7th International Symposium, 1999
1998
Computing Many Faces in Arrangements of Lines and Segments.
SIAM J. Comput., 1998
Constructing Levels in Arrangements and Higher Order Voronoi Diagrams.
SIAM J. Comput., 1998
On the <i>L</i><sub>2</sub>-Discrepancy for Anchored Boxes.
J. Complex., 1998
The Exponent of Discrepancy Is at Least 1.0669.
J. Complex., 1998
An L<sub>p</sub> Version of the Beck-Fiala Conjecture.
Eur. J. Comb., 1998
On Functional Separately Convex Hulls.
Discret. Comput. Geom., 1998
On Constants for Cuttings in the Plane.
Discret. Comput. Geom., 1998
Efficient Randomized Algorithms for the Repeated Median Line Estimator.
Algorithmica, 1998
Geometric Computation and the Art of Sampling.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998
Invitation to discrete mathematics.
Oxford University Press, ISBN: 978-0-19-850207-4, 1998
1997
A Helly-Type Theorem for Unions of Convex Sets.
Discret. Comput. Geom., 1997
1996
Note on the Colored Tverberg Theorem.
J. Comb. Theory B, 1996
Derandomization in Computational Geometry.
J. Algorithms, 1996
On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension.
J. Algorithms, 1996
A Deterministic Algorithm for the Three-dimensional Diameter Problem.
Comput. Geom., 1996
A Subexponential Bound for Linear Programming.
Algorithmica, 1996
1995
On Ramsey Sets in Spheres.
J. Comb. Theory A, 1995
Approximations and Optimal Geometric Divide-an-Conquer.
J. Comput. Syst. Sci., 1995
On Enclosing k Points by a Circle.
Inf. Process. Lett., 1995
Tight Upper Bounds for the Discrepancy of Half-Spaces.
Discret. Comput. Geom., 1995
On Geometric Optimization with Few Violated Constraints.
Discret. Comput. Geom., 1995
Vertical Decomposition of Arrangements of Hyperplanes in Four Dimensions.
Discret. Comput. Geom., 1995
An Elementary Approach to Lower Bounds in Geometric Discrepancy.
Discret. Comput. Geom., 1995
Piecewise Linear Paths Among Convex Obstacles.
Discret. Comput. Geom., 1995
Derandomizing an Output-sensitive Convex Hull Algorithm in Three Dimensions.
Comput. Geom., 1995
Dynamic Half-Space Range Reporting and Its Applications.
Algorithmica, 1995
1994
Fat Triangles Determine Linearly Many Holes.
SIAM J. Comput., 1994
Lower Bounds for a Subexponential Optimization Algorithm.
Random Struct. Algorithms, 1994
Intersection Graphs of Segments.
J. Comb. Theory B, 1994
On the Sum of Squares of Cell Complexities in Hyperplane Arrangements.
J. Comb. Theory A, 1994
Algorithms for Ham-Sandwich Cuts.
Discret. Comput. Geom., 1994
On Range Searching with Semialgebraic Sets.
Discret. Comput. Geom., 1994
Geometric Range Searching.
ACM Comput. Surv., 1994
Complexity of Projected Images of Convex Subdivisions.
Comput. Geom., 1994
1993
Ray Shooting and Parametric Search.
SIAM J. Comput., 1993
Linear Optimization Queries.
J. Algorithms, 1993
On Ray Shooting in Convex Polytopes.
Discret. Comput. Geom., 1993
Range Searching with Efficient Hiearchical Cutting.
Discret. Comput. Geom., 1993
Discrepancy and approximations for bounded VC-dimension.
Comb., 1993
On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimensions.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993
1992
Good Splitters for Counting Points in Triangles.
J. Algorithms, 1992
On the complexity of finding iso- and other morphisms for partial k-trees.
Discret. Math., 1992
Efficient Partition Trees.
Discret. Comput. Geom., 1992
On Vertical Ray Shooting in Arrangements.
Comput. Geom., 1992
Reporting Points in Halfspaces.
Comput. Geom., 1992
Relative Neighborhood Graphs in Three Dimensions.
Comput. Geom., 1992
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992
A Tail Estimate for Mulmuley's Segment Intersection Algorithm.
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992
Dynamic Half-Space Reporting, Geometric Optimization, and Minimum Spanning Trees
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992
Linear Optimization Queries.
Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992
Range Searching with Efficient Hierarchical Cuttings.
Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992
1991
Approximate Levels in Line Arrangements.
SIAM J. Comput., 1991
String graphs requiring exponential representations.
J. Comb. Theory B, 1991
Algorithms Finding Tree-Decompositions of Graphs.
J. Algorithms, 1991
Spanning trees with low crossing number.
RAIRO Theor. Informatics Appl., 1991
Randomized Optimal Algorithm for Slope Selection
Inf. Process. Lett., 1991
Computing Dominances in E^n.
Inf. Process. Lett., 1991
Cutting Hyperplane Arrangements.
Discret. Comput. Geom., 1991
Lower Bounds on the Length of Monotone Paths in Arrangement.
Discret. Comput. Geom., 1991
Farthest Neighbors, Maximum Spanning Trees and Related Problems in Higher Dimensions.
Comput. Geom., 1991
Farthest Neighbours, Maximum Spanning Trees and Related Problems in Higher Dimensions.
Proceedings of the Algorithms and Data Structures, 1991
Approximations and Optimal Geometric Divide-And-Conquer
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991
Discrepancy and epsilon-approximations for bounded VC-dimension
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991
Fat Triangles Determine Linearly Many Holes
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991
1990
Construction of epsilon-Nets.
Discret. Comput. Geom., 1990
Computing the Center of Planar Point Sets.
Proceedings of the Discrete and Computational Geometry: Papers from the DIMACS Special Year, 1990
How to Net a Lot with Little: Small epsilon-Nets for Disks and Halfspaces.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990
1989
On-Line Computation of Convolutions.
Inf. Process. Lett., 1989
1988
Line Arrangements and Range Search.
Inf. Process. Lett., 1988
