Jirí Matousek

Affiliations:
  • Charles University, Prague, Czech Republic


According to our database1, Jirí Matousek authored at least 179 papers between 1988 and 2018.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

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 $\exists\mathbb{R}$.
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
Vectors in a box.
Math. Program., 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, Ser. 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, Ser. 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

Random lifts of graphs.
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, Ser. 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, Ser. 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, Ser. B, 1994

On the Sum of Squares of Cell Complexities in Hyperplane Arrangements.
J. Comb. Theory, Ser. 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

Ham-Sandwich Cuts in R^d
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, Ser. 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


  Loading...