Jirí Matousek

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

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2015
Multilevel Polynomial Partitions and Simplified Range Searching.
Discrete & Computational Geometry, 2015

Three-Monotone Interpolation.
Discrete & Computational Geometry, 2015

Simplifying Inclusion-Exclusion Formulas.
Combinatorics, Probability & Computing, 2015

Combinatorial Discrepancy for Boxes via the gamma_2 Norm.
Proceedings of the 31st International Symposium on Computational Geometry, 2015

2014
Polynomial-Time Computation of Homotopy Groups and Postnikov Systems in Fixed Dimension.
SIAM J. Comput., 2014

On Gromov's Method of Selecting Heavily Covered Points.
Discrete & Computational Geometry, 2014

Extendability of Continuous Maps Is Undecidable.
Discrete & Computational Geometry, 2014

Near-Optimal Separators in String Graphs.
Combinatorics, Probability & Computing, 2014

Embeddability in the 3-sphere is decidable.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

Lower bounds on geometric Ramsey functions.
Proceedings of the 30th Annual Symposium on Computational Geometry, 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.
Foundations of Computational Mathematics, 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.
Discrete & Computational Geometry, 2012

Simple Proofs of Classical Theorems in Discrete Geometry via the Guth-Katz Polynomial Partitioning Technique.
Discrete & Computational Geometry, 2012

Unit Distances in Three Dimensions.
Combinatorics, Probability & Computing, 2012

Reachability by paths of bounded curvature in a convex polygon.
Comput. Geom., 2012

Minimum and maximum against k lies.
Chicago J. Theor. Comput. Sci., 2012

Computing all maps into a sphere.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

On Range Searching with Semialgebraic Sets II.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Higher-order Erdos-Szekeres theorems.
Proceedings of the Symposuim on Computational Geometry 2012, 2012

2011
A Doubly Exponentially Crumbled Cake.
Electronic Notes in Discrete Mathematics, 2011

On the Nonexistence of k-reptile Tetrahedra.
Discrete & Computational Geometry, 2011

The t-Pebbling Number is Eventually Linear in t.
Electr. J. Comb., 2011

2010
Stabbing Simplices by Points and Flats.
Discrete & Computational Geometry, 2010

Distance k-sectors exist.
Comput. Geom., 2010

Minimum and Maximum against k 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 k-sectors exist.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

2009
Dimension Gaps between Representability and Collapsibility.
Discrete & Computational Geometry, 2009

Removing Degeneracy in LP-Type Problems Revisited.
Discrete & Computational Geometry, 2009

Blocking Visibility for Points in General Position.
Discrete & Computational Geometry, 2009

Computing D-convex hulls in the plane.
Comput. Geom., 2009

Hardness of embedding simplicial complexes in Rd.
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
How Many Points Can Be Reconstructed from k Projections?
SIAM J. Discrete Math., 2008

Large Monochromatic Components in Two-Colored Grids.
SIAM J. Discrete Math., 2008

On variants of the Johnson-Lindenstrauss lemma.
Random Struct. Algorithms, 2008

Graph Colouring with No Large Monochromatic Components.
Combinatorics, Probability & Computing, 2008

Induced Trees in Triangle-Free Graphs.
Electr. J. Comb., 2008

LC reductions yield isomorphic simplicial complexes.
Contributions to Discrete Mathematics, 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 of Computing, 2007

Quadratically Many Colorful Simplices.
SIAM J. Discrete 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.
Electronic Notes in Discrete Mathematics, 2007

Removing degeneracy may require unbounded dimension increase.
Electronic Notes in Discrete Mathematics, 2007

How many points can be reconstructed from k projections?
Electronic Notes in Discrete Mathematics, 2007

Large Monochromatic Components in Two-colored Grids.
Electronic Notes in Discrete Mathematics, 2007

Graph coloring with no large monochromatic components.
Electronic Notes in Discrete Mathematics, 2007

Packing Cones and Their Negatives in Space.
Discrete & Computational Geometry, 2007

Zone diagrams: existence, uniqueness and algorithmic challenge.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006
Segmenting object space by geometric reference structures.
TOSN, 2006

Berge's theorem, fractional Helly, and art galleries.
Discrete Mathematics, 2006

k-Sets in Four Dimensions.
Discrete & Computational Geometry, 2006

The Minimum Independence Number of a Hasse Diagram.
Combinatorics, Probability & Computing, 2006

Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness.
Electr. J. Comb., 2006

The Number Of Unique-Sink Orientations of the Hypercube*.
Combinatorica, 2006

The distance trisector curve.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Violator Spaces: Structure and Algorithms.
Proceedings of the Algorithms, 2006

2005
The Randomized Integer Convex Hull.
Discrete & Computational Geometry, 2005

Discrepancy After Adding A Single Set.
Combinatorica, 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.
Discrete Mathematics, 2004

New Constructions of Weak epsilon-Nets.
Discrete & Computational Geometry, 2004

Bounded VC-Dimension Implies a Fractional Helly Theorem.
Discrete & Computational Geometry, 2004

No Helly Theorem for Stabbing Translates by Lines in R 3.
Discrete & Computational Geometry, 2004

A Combinatorial Proof of Kneser's Conjecture.
Combinatorica, 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

A Lower Bound on the Size of Lipschitz Subsets in Dimension 3.
Combinatorics, Probability & Computing, 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.
Discrete & Computational Geometry, 2002

Equipartition of Two Measures by a 4-Fan.
Discrete & Computational Geometry, 2002

The one-round Voronoi game.
Proceedings of the 18th Annual Symposium on Computational Geometry, Barcelona, 2002

2001
A Lower Bound for Families of Natarajan Dimension d.
J. Comb. Theory, Ser. A, 2001

Transversals of hypergraphs with geometric flavor.
Electronic Notes in Discrete Mathematics, 2001

Lower bound on the minus-domination number.
Discrete Mathematics, 2001

Lower Bounds on the Transversal Numbers of d-Intervals.
Discrete & Computational Geometry, 2001

On Directional Convexity.
Discrete & Computational Geometry, 2001

Simultaneous Partitions of Measures by k-Fans.
Discrete & Computational Geometry, 2001

Random lifts of graphs.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Low-Distortion Embeddings of Trees.
Proceedings of the Graph Drawing, 9th International Symposium, 2001

2000
On the Linear and Hereditary Discrepancies.
Eur. J. Comb., 2000

On Approximate Geometric k-Clustering.
Discrete & Computational Geometry, 2000

On the Signed Domination in Graphs.
Combinatorica, 2000

Reachability by paths of bounded curvature in convex polygons.
Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

1999
Product Range Spaces, Sensitive Sampling, and Derandomization.
SIAM J. Comput., 1999

Almost-Tiling the Plane by Ellipses.
Discrete & Computational Geometry, 1999

The Anatomy of a Geometric Algorithm.
Proceedings of the Graph Drawing, 7th International Symposium, 1999

1998
On the L2-Discrepancy for Anchored Boxes.
J. Complexity, 1998

The Exponent of Discrepancy Is at Least 1.0669.
J. Complexity, 1998

An Lp Version of the Beck-Fiala Conjecture.
Eur. J. Comb., 1998

On Functional Separately Convex Hulls.
Discrete & Computational Geometry, 1998

On Constants for Cuttings in the Plane.
Discrete & Computational Geometry, 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
Separating an Object from its Cast.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 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

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.
Discrete & Computational Geometry, 1995

Vertical Decomposition of Arrangements of Hyperplanes in Four Dimensions.
Discrete & Computational Geometry, 1995

An Elementary Approach to Lower Bounds in Geometric Discrepancy.
Discrete & Computational Geometry, 1995

Derandomizing an Output-sensitive Convex Hull Algorithm in Three Dimensions.
Comput. Geom., 1995

Dynamic Half-Space Range Reporting and Its Applications.
Algorithmica, 1995

A Helly-Type Theorem for Unions of Convex Sets.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 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

Algorithms for Ham-Sandwich Cuts.
Discrete & Computational Geometry, 1994

Geometric Range Searching.
ACM Comput. Surv., 1994

Complexity of Projected Images of Convex Subdivisions.
Comput. Geom., 1994

On Geometric Optimization with Few Violated Constraints.
Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

Computing Many Faces in Arrangements of Lines and Segments.
Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

Constructing Levels in Arrangements and Higher Order Voronoi Diagrams.
Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

1993
Ray Shooting and Parametric Search.
SIAM J. Comput., 1993

Linear Optimization Queries.
J. Algorithms, 1993

On Ray Shooting in Convex Polytopes.
Discrete & Computational Geometry, 1993

Range Searching with Efficient Hiearchical Cutting.
Discrete & Computational Geometry, 1993

Discrepancy and approximations for bounded VC-dimension.
Combinatorica, 1993

A deterministic algorithm for the three-dimensional diameter problem.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Piecewise linear paths among convex obstacles.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Efficient Randomized Algorithms for the Repeated Median Line Estimator.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 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

Product Range Spaces, Sensitive Sampling, and Derandomization
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

On Vertical Decomposition of Arrangements of Hyperplanes in Four Dimensions.
Proceedings of the 5th Canadian Conference on Computational Geometry, 1993

1992
On the complexity of finding iso- and other morphisms for partial k-trees.
Discrete Mathematics, 1992

On Vertical Ray Shooting in Arrangements.
Comput. Geom., 1992

Reporting Points in Halfspaces.
Comput. Geom., 1992

Ham-Sandwich Cuts in R^d
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Ray Shooting and Parametric Search
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Relative Neighborhood Graphs in Three Dimensions.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

On Range Searching with Semialgebraic Sets.
Proceedings of the Mathematical Foundations of Computer Science 1992, 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

A Subexponential Bound for Linear Programming.
Proceedings of the Eighth Annual Symposium on Computational Geometry, 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.
ITA, 1991

Randomized Optimal Algorithm for Slope Selection
Inf. Process. Lett., 1991

Computing Dominances in E^n.
Inf. Process. Lett., 1991

Lower Bounds on the Length of Monotone Paths in Arrangement.
Discrete & Computational Geometry, 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

Reporting Points in Halfspaces
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Efficient Partition Trees.
Proceedings of the Seventh Annual Symposium on Computational Geometry, 1991

On the Sum of Squares of Cell Complexities in Hyperplane Arrangements.
Proceedings of the Seventh Annual Symposium on Computational Geometry, 1991

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

Cutting Hyperplane Arrangements.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

1989
On-Line Computation of Convolutions.
Inf. Process. Lett., 1989

Good Splitters for Counting Points in Triangles.
Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

Construction of epsilon Nets.
Proceedings of the Fifth Annual Symposium on Computational Geometry, 1989

1988
Line Arrangements and Range Search.
Inf. Process. Lett., 1988


  Loading...