Micha Sharir

According to our database1, Micha Sharir
  • authored at least 547 papers between 1979 and 2017.
  • has a "Dijkstra number"2 of three.

Awards

ACM Fellow

ACM Fellow 1997, "Algorithmic motion planning; properties of Davenport-Schinzel sequences and their applications in computiational geometry; arrangements of surfaces and their relevance to geometric algorithms; subexpotential randomized (combinatorial) algorithm for linear programming.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications.
ACM Trans. Algorithms, 2017

Computational Geometry Column 65.
SIGACT News, 2017

Cutting algebraic curves into pseudo-segments and applications.
J. Comb. Theory, Ser. A, 2017

Incidences Between Points and Lines in $${\mathbb {R}}^4$$.
Discrete & Computational Geometry, 2017

Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n5/3) time.
CoRR, 2017

On the number of unit-area triangles spanned by convex grids in the plane.
Comput. Geom., 2017

Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distances.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Eliminating Depth Cycles among Triangles in Three Dimensions.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

The Algebraic Revolution in Combinatorial and Computational Geometry: State of the Art (Invited Talk).
Proceedings of the 33rd International Symposium on Computational Geometry, 2017

A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM.
Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016
Generalizations of the Szemerédi-Trotter Theorem.
Discrete & Computational Geometry, 2016

Distinct Distances from Three Points.
Combinatorics, Probability & Computing, 2016

Cutting Algebraic Curves into Pseudo-segments and Applications.
CoRR, 2016

The Elekes-Szabó Theorem in four dimensions.
CoRR, 2016

Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications.
CoRR, 2016

Approximating the $k$-Level in Three-Dimensional Plane Arrangements.
CoRR, 2016

Dynamic Time Warping: Breaking the Quadratic Barrier.
CoRR, 2016

Dominance Products and Faster Algorithms for High-Dimensional Closest Pair under L.
CoRR, 2016

The Decision Tree Complexity for k-SUM is at most Nearly Quadratic.
CoRR, 2016

Eliminating Depth Cycles among Triangles in Three Dimensions.
CoRR, 2016

Incidences with Curves in $\mathbb{R}^d$.
Electr. J. Comb., 2016

Almost tight bounds for eliminating depth cycles in three dimensions.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Approximating the k-Level in Three-Dimensional Plane Arrangements.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015
The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection.
ACM Trans. Algorithms, 2015

Finding the largest disk containing a query point in logarithmic time with linear storage.
JoCG, 2015

Sets with few distinct distances do not have heavy lines.
Discrete Mathematics, 2015

On Triple Intersections of Three Families of Unit Circles.
Discrete & Computational Geometry, 2015

Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions.
Discrete & Computational Geometry, 2015

Stable Delaunay Graphs.
Discrete & Computational Geometry, 2015

Improved Bounds for Incidences Between Points and Circles.
Combinatorics, Probability & Computing, 2015

The number of unit-area triangles in the plane: Theme and variations.
CoRR, 2015

Delaunay Triangulations of Degenerate Point Sets.
CoRR, 2015

Improved Bounds for 3SUM, K-SUM, and Linear Degeneracy.
CoRR, 2015

A faster algorithm for the discrete Fréchet distance under translation.
CoRR, 2015

Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions.
CoRR, 2015

Stable Delaunay Graphs.
CoRR, 2015

Incidences between Points and Lines in R^4.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Incidences with Curves in ℝ d.
Proceedings of the Algorithms - ESA 2015, 2015

Incidences between Points and Lines in Three Dimensions.
Proceedings of the 31st International Symposium on Computational Geometry, 2015

Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited.
Proceedings of the 31st International Symposium on Computational Geometry, 2015

The Number of Unit-Area Triangles in the Plane: Theme and Variations.
Proceedings of the 31st International Symposium on Computational Geometry, 2015

2014
Improved Bounds for the Union of Locally Fat Objects in the Plane.
SIAM J. Comput., 2014

Reporting Neighbors in High-Dimensional Euclidean Space.
SIAM J. Comput., 2014

Computing the Discrete Fréchet Distance in Subquadratic Time.
SIAM J. Comput., 2014

A note on distinct distances in rectangular lattices.
Discrete Mathematics, 2014

Union of Random Minkowski Sums and Network Vulnerability Analysis.
Discrete & Computational Geometry, 2014

Polynomials vanishing on grids: The Elekes-Rónyai problem revisited.
CoRR, 2014

Epsilon-Nets for Halfspaces Revisited.
CoRR, 2014

Partial-Matching and Hausdorff RMS Distance Under Translation: Combinatorics and Algorithms.
CoRR, 2014

Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions.
CoRR, 2014

Minimum Partial-Matching and Hausdorff RMS-Distance under Translation: Combinatorics and Algorithms.
Proceedings of the Algorithms - ESA 2014, 2014

Incidences between points and lines in R4: Extended Abstract.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

Polynomials vanishing on grids: The Elekes-Rónyai problem revisited.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

On triple intersections of three families of unit circles.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

Finding the Largest Disk Containing a Query Point in Logarithmic Time with Linear Storage.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013
On Range Searching with Semialgebraic Sets. II.
SIAM J. Comput., 2013

Counting plane graphs: Perfect matchings, spanning cycles, and Kasteleyn's technique.
J. Comb. Theory, Ser. A, 2013

Distinct distances on two lines.
J. Comb. Theory, Ser. A, 2013

Finding the largest Empty Disk containing a Query Point.
Int. J. Comput. Geometry Appl., 2013

Counting Plane Graphs: Cross-Graph Charging Schemes.
Combinatorics, Probability & Computing, 2013

Distinct distances on two lines
CoRR, 2013

Output-Sensitive Tools for Range Searching in Higher Dimensions.
CoRR, 2013

Finding the Largest Disk Containing a Query Point in Logarithmic Time with Linear Storage.
CoRR, 2013

On lattices, distinct distances, and the Elekes-Sharir framework.
CoRR, 2013

The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection Techniques.
CoRR, 2013

Union of Random Minkowski Sums and Network Vulnerability Analysis.
CoRR, 2013

The 2-center problem in three dimensions.
Comput. Geom., 2013

On the Union Complexity of Diametral Disks.
Electr. J. Comb., 2013

Reporting neighbors in high-dimensional Euclidean spaces.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Computing the Discrete Fréchet Distance in Subquadratic Time.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Improved bounds for incidences between points and circles.
Proceedings of the Symposuim on Computational Geometry 2013, 2013

Union of random minkowski sums and network vulnerability analysis.
Proceedings of the Symposuim on Computational Geometry 2013, 2013

2012
Improved Bounds for Geometric Permutations.
SIAM J. Comput., 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

Counting Plane Graphs: Cross-Graph Charging Schemes
CoRR, 2012

On Range Searching with Semialgebraic Sets II
CoRR, 2012

Incidences between points and non-coplanar circles
CoRR, 2012

Computing the Discrete Fréchet Distance in Subquadratic Time
CoRR, 2012

Near-Linear Approximation Algorithms for Geometric Hitting Sets.
Algorithmica, 2012

Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Counting Plane Graphs: Cross-Graph Charging Schemes.
Proceedings of the Graph Drawing - 20th International Symposium, 2012

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

Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique.
Proceedings of the Symposuim on Computational Geometry 2012, 2012

Finding the maximal empty disk containing a query point.
Proceedings of the Symposuim on Computational Geometry 2012, 2012

2011
Semialgebraic Range Reporting and Emptiness Searching with Applications.
SIAM J. Comput., 2011

Optimal Cover of Points by Disks in a Simple Polygon.
SIAM J. Comput., 2011

On degrees in random triangulations of point sets.
J. Comb. Theory, Ser. A, 2011

On lines, joints, and incidences in three dimensions.
J. Comb. Theory, Ser. A, 2011

The Overlay of Minimization Diagrams in a Randomized Incremental Construction.
Discrete & Computational Geometry, 2011

Range Minima Queries with Respect to a Random Permutation, and Approximate Range Counting.
Discrete & Computational Geometry, 2011

Relative (p, ε)-Approximations in Geometry.
Discrete & Computational Geometry, 2011

An Improved Bound for k-Sets in Four Dimensions.
Combinatorics, Probability & Computing, 2011

Incidences in Three Dimensions and Distinct Distances in the Plane.
Combinatorics, Probability & Computing, 2011

Non-Degenerate Spheres in Three Dimensions.
Combinatorics, Probability & Computing, 2011

Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn's Technique
CoRR, 2011

Finding the Maximal Empty Rectangle Containing a Query Point
CoRR, 2011

Kinetic Stable Delaunay Graphs
CoRR, 2011

A kinetic triangulation scheme for moving points in the plane.
Comput. Geom., 2011

Counting Triangulations of Planar Point Sets.
Electr. J. Comb., 2011

Counting Plane Graphs: Flippability and Its Applications.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Improved Bound for the Union of Fat Triangles.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010
Constructing Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes in Space.
Trans. Computational Science, 2010

Hausdorff distance under translation for points and balls.
ACM Trans. Algorithms, 2010

Line Transversals of Convex Polyhedra in R3.
SIAM J. Comput., 2010

Approximate Halfspace Range Counting.
SIAM J. Comput., 2010

Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes.
SIAM J. Comput., 2010

On Lines and Joints.
Discrete & Computational Geometry, 2010

An Improved Bound on the Number of Unit Area Triangles.
Discrete & Computational Geometry, 2010

The 2-Center Problem in Three Dimensions
CoRR, 2010

Counting Plane Graphs: Flippability and its Applications
CoRR, 2010

Improved Bounds for Geometric Permutations
CoRR, 2010

Incidences in Three Dimensions and Distinct Distances in the Plane
CoRR, 2010

A Kinetic Triangulation Scheme for Moving Points in The Plane
CoRR, 2010

An Improved Bound on the Number of Unit Area Triangles
CoRR, 2010

Guarding a Terrain by Two Watchtowers.
Algorithmica, 2010

Improved Bounds for Geometric Permutations.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Optimal Cover of Points by Disks in a Simple Polygon.
Proceedings of the Algorithms, 2010

On degrees in random triangulations of point sets.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

A kinetic triangulation scheme for moving points in the plane.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

Incidences in three dimensions and distinct distances in the plane.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

Kinetic stable Delaunay graphs.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

The 2-center problem in three dimensions.
Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

Algorithm Derivation by Transformations (reprint).
General Books, ISBN: 978-1-154-60684-3, 2010

Combinatorial Complexity Bounds for Arrangements of Curves and Surfaces (reprint).
General Books, ISBN: 978-1-153-46242-6, 2010

2009
Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles.
ACM Trans. Algorithms, 2009

Eppstein's bound on intersecting triangles revisited.
J. Comb. Theory, Ser. A, 2009

Extremal problems on triangle areas in two and three dimensions.
J. Comb. Theory, Ser. A, 2009

On the union of fat tetrahedra in three dimensions.
J. ACM, 2009

On Overlays and Minimization Diagrams.
Discrete & Computational Geometry, 2009

On Regular Vertices of the Union of Planar Convex Objects.
Discrete & Computational Geometry, 2009

Counting Triangulations of Planar Point Sets
CoRR, 2009

Relative (p,epsilon)-Approximations in Geometry
CoRR, 2009

Semi-algebraic Range Reporting and Emptiness Searching with Applications
CoRR, 2009

On lines and Joints
CoRR, 2009

On Lines, Joints, and Incidences in Three Dimensions
CoRR, 2009

Linear Data Structures for Fast Ray-Shooting amidst Convex Polyhedra.
Algorithmica, 2009

Small-size epsilon-nets for axis-parallel rectangles and boxes.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Line transversals of convex polyhedra in R3.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Constructing Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes in Space.
Proceedings of the Sixth International Symposium on Voronoi Diagrams, 2009

An improved bound on the number of unit area triangles.
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

Near-linear approximation algorithms for geometric hitting sets.
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009

2008
Algorithms for center and Tverberg points.
ACM Trans. Algorithms, 2008

Kinetic and dynamic data structures for closest pair and all nearest neighbors.
ACM Trans. Algorithms, 2008

Efficient Colored Orthogonal Range Counting.
SIAM J. Comput., 2008

On planar intersection graphs with forbidden subgraphs.
Journal of Graph Theory, 2008

Weak ε-nets and interval chains.
J. ACM, 2008

An Optimal-Time Algorithm for Shortest Paths on a Convex Polytope in Three Dimensions.
Discrete & Computational Geometry, 2008

Efficient Algorithms for Maximum Regression Depth.
Discrete & Computational Geometry, 2008

Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles in 2D and 3D.
Discrete & Computational Geometry, 2008

Line Transversals of Convex Polyhedra in R3
CoRR, 2008

Eppstein's bound on intersecting triangles revisited
CoRR, 2008

On the performance of the ICP algorithm.
Comput. Geom., 2008

Weak ε-nets and interval chains.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Stabbing Convex Polygons with a Segment or a Polygon.
Proceedings of the Algorithms, 2008

Extremal problems on triangle areas in two and three dimensions.
Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

The complexity of the outer face in arrangements of random segments.
Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

2007
Large Complete Bipartite Subgraphs In Incidence Graphs Of Points And Hyperplanes.
SIAM J. Discrete Math., 2007

Online Conflict-Free Coloring for Intervals.
SIAM J. Comput., 2007

Solution of Scott's Problem on the Number of Directions Determined by a Point Set in 3-Space.
Discrete & Computational Geometry, 2007

A Single Cell in an Arrangement of Convex Polyhedra in \Bbb R3.
Discrete & Computational Geometry, 2007

Kinetic and dynamic data structures for convex hulls and upper envelopes.
Comput. Geom., 2007

Counting colors in boxes.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Arrangements in Geometry: Recent Advances and Challenges.
Proceedings of the Algorithms, 2007

Linear Data Structures for Fast Ray-Shooting Amidst Convex Polyhedra.
Proceedings of the Algorithms, 2007

Bi-criteria linear-time approximations for generalized k-mean/median/center.
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

On regular vertices on the union of planar objects.
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

On approximate halfspace range counting and relative epsilon-approximations.
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

Computing the volume of the union of cubes.
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

Similar simplices in a d-dimensional point set.
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

2006
On the Number of Crossing-Free Matchings, Cycles, and Partitions.
SIAM J. Comput., 2006

Computing Maximally Separated Sets in the Plane.
SIAM J. Comput., 2006

On empty convex polygons in a planar point set.
J. Comb. Theory, Ser. A, 2006

Minkowski Sums of Monotone and General Simple Polygons.
Discrete & Computational Geometry, 2006

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

On the Union of kappa-Round Objects in Three and Four Dimensions.
Discrete & Computational Geometry, 2006

On the number of crossing-free matchings, (cycles, and partitions).
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Computing a Center-Transversal Line.
Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006

Coresets forWeighted Facilities and Their Applications.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Random triangulations of planar point sets.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

An optimal-time algorithm for shortest paths on a convex polytope in three dimensions.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

On overlays and minimization diagrams.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

Colored intersection searching via sparse rectangular matrix multiplication.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

On the ICP algorithm.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

2005
Repeated Angles in Three and Four Dimensions.
SIAM J. Discrete Math., 2005

Top-Down Analysis of Path Compression.
SIAM J. Comput., 2005

Curve-Sensitive Cuttings.
SIAM J. Comput., 2005

Output-Sensitive Construction of the Union of Triangles.
SIAM J. Comput., 2005

Pseudo-Line Arrangements: Duality, Algorithms, and Applications.
SIAM J. Comput., 2005

Crossing patterns of semi-algebraic sets.
J. Comb. Theory, Ser. A, 2005

Topological Graphs with No Large Grids.
Graphs and Combinatorics, 2005

An Improved Bound for Joints in Arrangements of Lines in Space.
Discrete & Computational Geometry, 2005

Cutting Triangular Cycles of Lines in Space.
Discrete & Computational Geometry, 2005

Incidences between Points and Circles in Three and Higher Dimensions.
Discrete & Computational Geometry, 2005

Lines Avoiding Unit Balls in Three Dimensions.
Discrete & Computational Geometry, 2005

Ray shooting and stone throwing with near-linear storage.
Comput. Geom., 2005

Counting and representing intersections among triangles in three dimensions.
Comput. Geom., 2005

On Graphs That Do Not Contain The Cube And Related Problems.
Combinatorica, 2005

Kinetic and Dynamic Data Structures for Convex Hulls and Upper Envelopes.
Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

Ray shooting amid balls, farthest point from a line, and range emptiness searching.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

The interface between computational and combinatorial geometry.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Online conflict-free coloring for intervals.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004
Algorithmic motion planning.
Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004

The Simplex Algorithm in Dimension Three.
SIAM J. Comput., 2004

On the number of directions determined by a three-dimensional points set.
J. Comb. Theory, Ser. A, 2004

Lenses in arrangements of pseudo-circles and their applications.
J. ACM, 2004

Polyhedral Voronoi Diagrams of Polyhedra in Three Dimensions.
Discrete & Computational Geometry, 2004

Binary Space Partitions for Axis-Parallel Segments, Rectangles, and Hyperrectangles.
Discrete & Computational Geometry, 2004

Cell Complexities in Hyperplane Arrangements.
Discrete & Computational Geometry, 2004

Selecting Points that are Heavily Covered by Pseudo-Circles, Spheres or Rectangles.
Combinatorics, Probability & Computing, 2004

Point-Line Incidences in Space.
Combinatorics, Probability & Computing, 2004

Distinct Distances in Three and Higher Dimensions.
Combinatorics, Probability & Computing, 2004

Speeding up the incremental construction of the union of geometric objects in practice.
Comput. Geom., 2004

On the number of views of translates of a cube and related problems.
Comput. Geom., 2004

Output-sensitive construction of the union of triangles.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Geometrically aware communication in random wireless networks.
Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

On empty convex polygons in a planar point set.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

Solution of Scott's problem on the number of directions determined by a point set in 3-space.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

New results on shortest paths in three dimensions.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

Counting and representing intersections among triangles in three dimensions.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

On the union of kapa-round objects.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

Algorithms for center and Tverberg points.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

On lines avoiding unit balls in three dimensions.
Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

2003
The Partition Technique for Overlays of Envelopes.
SIAM J. Comput., 2003

3-Dimensional Euclidean Voronoi Diagrams of Lines with a Fixed Number of Orientations.
SIAM J. Comput., 2003

The Minkowski sum of a simple polygon and a segment.
Inf. Process. Lett., 2003

On neighbors in geometric permutations.
Discrete Mathematics, 2003

The Union of Congruent Cubes in Three Dimensions.
Discrete & Computational Geometry, 2003

The Clarkson-Shor Technique Revisited And Extended.
Combinatorics, Probability & Computing, 2003

Extremal Configurations and Levels in Pseudoline Arrangements.
Proceedings of the Algorithms and Data Structures, 8th International Workshop, 2003

Distinct distances in three and higher dimensions.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Cutting triangular cycles of lines in space.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Ray Shooting and Stone Throwing.
Proceedings of the Algorithms, 2003

A tight bound for the number of different directions in three dimensions.
Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

Curve-sensitive cuttings.
Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

Hausdorff distance under translation for points and balls.
Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

2002
The 2-Center Problem with Obstacles.
J. Algorithms, 2002

Cutting Circles into Pseudo-Segments and Improved Bounds for Incidences% and Complexity of Many Faces.
Discrete & Computational Geometry, 2002

Reporting intersecting pairs of convex polytopes in two and three dimensions.
Comput. Geom., 2002

On Neighbors in Geometric Permutations.
Proceedings of the Algorithm Theory, 2002

On the overlay of envelopes in four dimensions.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Pseudo-line arrangements: duality, algorithms, and applications.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

The Partition Technique for Overlays of Envelopes.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Speeding Up the Incremental Construction of the Union of Geometric Objects in Practice.
Proceedings of the Algorithms, 2002

Translating a Planar Object to Maximize Point Containment.
Proceedings of the Algorithms, 2002

Point-line incidences in space.
Proceedings of the 18th Annual Symposium on Computational Geometry, Barcelona, 2002

Lenses in arrangements of pseudo-circles and their applications.
Proceedings of the 18th Annual Symposium on Computational Geometry, Barcelona, 2002

Polyhedral Voronoi diagrams of polyhedra in three dimensions.
Proceedings of the 18th Annual Symposium on Computational Geometry, Barcelona, 2002

Three dimensional euclidean Voronoi diagrams of lines with a fixed number of orientations.
Proceedings of the 18th Annual Symposium on Computational Geometry, Barcelona, 2002

Incidences between points and circles in three and higher dimensions.
Proceedings of the 18th Annual Symposium on Computational Geometry, Barcelona, 2002

2001
Radial Points in the Plane.
Eur. J. Comb., 2001

An Improved Bound for k-Sets in Three Dimensions.
Discrete & Computational Geometry, 2001

Online Point Location in Planar Arrangements and Its Applications.
Discrete & Computational Geometry, 2001

On the Number of Regular Vertices of the Union of Jordan Regions.
Discrete & Computational Geometry, 2001

On the Complexity of Arrangements of Circles in the Plane.
Discrete & Computational Geometry, 2001

Exact and Approximation Algorithms for Minimum-Width Cylindrical Shells.
Discrete & Computational Geometry, 2001

Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

Online point location in planar arrangements and its applications.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

On the Complexity of Many Faces in Arrangements of Circles.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Balanced lines, halving triangles, and the generalized lower bound theorem.
Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

The Clarkson-Shor technique revisited and extended.
Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

The union of congruent cubes in three dimensions.
Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles.
Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

On the number of congruent simplices in a point.
Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

2000
Penetration Depth of Two Convex Polytopes in 3D.
Nord. J. Comput., 2000

Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls in Rd.
Discrete & Computational Geometry, 2000

On the Complexity of the Union of Fat Convex Objects in the Plane.
Discrete & Computational Geometry, 2000

Pipes, Cigars, and Kreplach: the Union of Minkowski Sums in Three Dimensions.
Discrete & Computational Geometry, 2000

Approximation Algorithms for Minimum-Width Annuli and Shells.
Discrete & Computational Geometry, 2000

Dynamic data structures for fat objects and their applications.
Comput. Geom., 2000

Computing the Penetration Depth of Two Convex Polytopes in 3D.
Proceedings of the Algorithm Theory, 2000

Exact and approximation algorithms for minimum-width cylindrical shells.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

An Improved Bound for k-Sets in Three Dimensions.
EuroCG, 2000

An improved bound for k-sets in three dimensions.
Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

The 2-center problem with obstacles.
Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

1999
Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications.
SIAM J. Comput., 1999

On the Boundary of the Union of Planar Convex Sets.
Discrete & Computational Geometry, 1999

Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions.
Discrete & Computational Geometry, 1999

Motion Planning for a Convex Polygon in a Polygonal Environment.
Discrete & Computational Geometry, 1999

Partial surface matching by using directed footprints.
Comput. Geom., 1999

Motion Planning of a Ball Amid Segments in Three Dimensions.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Recent Developments in the Theory of Arrangements of Surfaces.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1999

Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls inRd.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

Efficient Algorithms for Maximum Regression Depth.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

Pipes, Cigars, and Kreplach: The Union of Minkowski Sums in Three Dimensions.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

Approximation and Exact Algorithms for Minimum-Width Annuli and Shells.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

1998
Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions.
J. Algorithms, 1998

Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions.
Discrete & Computational Geometry, 1998

The Discrete 2-Center Problem.
Discrete & Computational Geometry, 1998

Largest Placement of One Convex Polygon Inside Another.
Discrete & Computational Geometry, 1998

On Levels in Arrangements of Lines, Segments, Planes, and Triangles%.
Discrete & Computational Geometry, 1998

Efficient Algorithms for Geometric Optimization.
ACM Comput. Surv., 1998

On the Number of Incidences Between Points and Curves.
Combinatorics, Probability & Computing, 1998

On the Number of Regular Vertices of the Union of Jordan Regions.
Proceedings of the Algorithm Theory, 1998

1997
Ray Shooting Amidst Spheres in Three Dimensions and Related Problems.
SIAM J. Comput., 1997

An Expander-Based Approach to Geometric Optimization.
SIAM J. Comput., 1997

The Union of Convex Polyhedra in Three Dimensions.
SIAM J. Comput., 1997

On Translational Motion Planning of a Convex Polyhedron in 3-Space.
SIAM J. Comput., 1997

Computing Envelopes in Four Dimensions with Applications.
SIAM J. Comput., 1997

Approximating shortest paths on a convex polytope in three dimensions.
J. ACM, 1997

A Near-Linear Algorithm for the Planar 2-Center Problem.
Discrete & Computational Geometry, 1997

Vertical Decomposition of a Single Cell in a Three-Dimensional Arrangement of Surfaces.
Discrete & Computational Geometry, 1997

On Critical Orientations in the Kedem-Sharir Motion Planning Algorithm.
Discrete & Computational Geometry, 1997

The Common Exterior of Convex Polygons in the Plane.
Comput. Geom., 1997

Quasi-Planar Graphs Have a Linear Number of Edges.
Combinatorica, 1997

Optimized-motion planning - theory and implementation by Cherif Ahrikencheikh and Ali Seireg : John Wiley & Sons Inc., Chichester (1994) 366 pp, ISBN 0-471-01903-8.
Computer-Aided Design, 1997

Dynamic Data Structures for Fat Objects and Their Applications.
Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

Line Traversals of Balls and Smallest Enclosing Cylinders in Three Dimensions.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

On the Complexity of the Union of Fat Objects in the Plane.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

The Discrete 2-Center Problem.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

On Levels in Arrangements of Lines, Segments, Planes, and Triangles.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

1996
Ray Shooting amidst Convex Polyhedra and Polyhedral Terrains in Three Dimensions.
SIAM J. Comput., 1996

Ray Shooting Amidst Convex Polygons in 2D.
J. Algorithms, 1996

Excess in Arrangements of Segments.
Inf. Process. Lett., 1996

A Near-Quadratic Algorithm for Planning the Motion of a Polygon in a Polygonal Environment.
Discrete & Computational Geometry, 1996

A Near-Linear Algorithm for the Planar Segment-Center Problem.
Discrete & Computational Geometry, 1996

The Overlay of Lower Envelopes and Its Applications.
Discrete & Computational Geometry, 1996

Efficient Randomized Algorithms for Some Geometric. Optimization Problems.
Discrete & Computational Geometry, 1996

Piecewise-Linear Interpolation between Polygonal Slices.
Computer Vision and Image Understanding, 1996

A Subexponential Bound for Linear Programming.
Algorithmica, 1996

Lines in Space: Combinatorics and Algorithms.
Algorithmica, 1996

Efficient Generation of k-Directional Assembly Sequences.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Arrangements of Curves and Surfaces in Computational Geometry.
Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

Rectilinear and Polygonal p-Piercing and p-Center Problems.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

A Near-Linear Algorithm for the Planar 2-Center Problem.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

Vertical Decomposition of a Single Cell in a Three-Dimensional Arrangement of Surfaces and Its Applications.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

Approximating Shortest Paths on a Convex Polytope in Three Dimensions.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

Partial Surface Matching by Using Directed Footprints.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

1995
Reaching a Goal with Directional Uncertainty.
Theor. Comput. Sci., 1995

Almost Tight Upper Bounds for the Single Cell and Zone Problems in Three Dimensions.
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

Improved Bounds on Weak epsilon-Nets for Convex Sets.
Discrete & Computational Geometry, 1995

Computing Depth Orders for Fat Objects and Related Problems.
Comput. Geom., 1995

Filling gaps in the boundary of a polyhedron.
Computer Aided Geometric Design, 1995

Arrangements in Higher Dimensions: Voronoi Diagrams, Motion Planning, and Other Applications.
Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Quasi-Planar Graphs Have a Linear Number of Edges.
Proceedings of the Graph Drawing, Symposium on Graph Drawing, GD '95, Passau, 1995

Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

The Overlay of Lower Envelopes in Three Dimensions and Its Applications.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

Efficient Randomized Algorithms for Some Geometric Optimization Problems.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

Algorithmic Techniques for Geometric Optimization.
Proceedings of the Computer Science Today: Recent Trends and Developments, 1995

Davenport-Schinzel sequences and their geometric applications.
Cambridge University Press, ISBN: 978-0-521-47025-4, 1995

1994
Fat Triangles Determine Linearly Many Holes.
SIAM J. Comput., 1994

Selecting Heavily Covered Points.
SIAM J. Comput., 1994

On Joints in Arrangements of Lines in Space and Related Problems.
J. Comb. Theory, Ser. A, 1994

On the Sum of Squares of Cell Complexities in Hyperplane Arrangements.
J. Comb. Theory, Ser. A, 1994

Applications of Parametric Searching in Geometric Optimization.
J. Algorithms, 1994

Motion Planning in the Presence of Moving Obstacles.
J. ACM, 1994

On Disjoint Concave Chains in Arrangements of (Pseudo) Lines.
Inf. Process. Lett., 1994

Almost Tight Upper Bounds for Lower Envelopes in Higher Dimensions.
Discrete & Computational Geometry, 1994

New Bounds for Lower Envelopes in Three Dimensions, with Applications to Visbility in Terrains.
Discrete & Computational Geometry, 1994

Castles in the Air Revisited.
Discrete & Computational Geometry, 1994

On the Number of Views of Polyhedral Terrains.
Discrete & Computational Geometry, 1994

External Polygon Containment Problems.
Comput. Geom., 1994

Computing the Smallest K-enclosing Circle and Related Problems.
Comput. Geom., 1994

An Improved Technique for Output-Sensitive Hidden Surface Removal.
Algorithmica, 1994

Algorithms for Bichromatic Line-Segment Problems Polyhedral Terrains.
Algorithmica, 1994

Ray Shooting in Polygons Using Geodesic Triangulations.
Algorithmica, 1994

Planar Geometric Location Problems.
Algorithmica, 1994

Computing Depth Orders and Related Problems.
Proceedings of the Algorithm Theory, 1994

A Near-Linear Algorithm for the Planar Segment Center Problem.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Almost Tight Upper Bounds for the Single Cell and Zone Problems in Three Dimensions.
Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

Piecewise-Linear Interpolation Between Polygonal Slices.
Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

On Translational Motion Planning in 3-Space.
Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

Computing Envelopes in Four Dimensions with Applications.
Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

1993
On the Zone Theorem for Hyperplane Arrangements.
SIAM J. Comput., 1993

Computing a Face in an Arrangement of Line Segments and Related Problems.
SIAM J. Comput., 1993

Counting Circular Arc Intersections.
SIAM J. Comput., 1993

Circle Shooting in a Simple Polygon.
J. Algorithms, 1993

Computing a Segment Center for a Planar Point Set.
J. Algorithms, 1993

Optimal Slope Selection via Expanders.
Inf. Process. Lett., 1993

Circular visibility of a simple polygon from a fixed point.
Int. J. Comput. Geometry Appl., 1993

The Upper Envelope of voronoi Surfaces and Its Applications.
Discrete & Computational Geometry, 1993

Diameter, Width, Closest Line Pair, and Parametric Searching.
Discrete & Computational Geometry, 1993

On the Zone of a Surface in a Hyperplane Arrangement.
Discrete & Computational Geometry, 1993

An Invariant Property of Balls in Arrangements of Hyperplanes.
Discrete & Computational Geometry, 1993

Applications of a New Space-Partitioning Technique.
Discrete & Computational Geometry, 1993

Tail Estimates for the Efficiency of Randomized Incremental Algorithms for Line Segment Intersection.
Comput. Geom., 1993

On the Union of Fat Wedges and Separating a Collection of Segments By a Line.
Comput. Geom., 1993

k-sets and random hulls.
Combinatorica, 1993

Selecting Distances in the Plane.
Algorithmica, 1993

Computing the Smallest k-Enclosing Circle and Related Problems.
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Improved bounds on weak epsilon-nets for convex sets.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Ray Shooting Amidst Convex Polytopes in Three Dimensions.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Reaching a Goal with Directional Uncertainty.
Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

Almost Tight Upper Bounds for Lower Envelopes in Higher Dimensions
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Near-Quadratic Bounds for the Motion Planning Problem for a Polygon in a Polygonal Environment
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

The Union of Convex Polyhedra in Three Dimensions
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Implementation of a Motion Planning System in Three Dimensions.
Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

An Expander-Based Approach to Geometric Optimization.
Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

The Power of Geometric Duality and Minkowski Sums in Optical Computational Geometry.
Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

New Bounds for Lower Envelopes in Three Dimensions, with Applications to Visibility in Terrains.
Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

Arrangements of Surfaces in Higher Dimensions: Envelopes Single Cells and Other Recent Developments.
Proceedings of the 5th Canadian Conference on Computational Geometry, 1993

On Critical Orientations in the Kedem-Sharir Motion Planning Algorithm for a Convex Polygon in the Plane.
Proceedings of the 5th Canadian Conference on Computational Geometry, 1993

Optimal Slope Selection Via Expanders.
Proceedings of the 5th Canadian Conference on Computational Geometry, 1993

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

On the Union of Fat Wedges and Separating a Collection of Segments By a Line.
Proceedings of the 5th Canadian Conference on Computational Geometry, 1993

Finding Maximally Consistent Sets of Halfspaces.
Proceedings of the 5th Canadian Conference on Computational Geometry, 1993

On the Number of Views of Polyhedral Terrains.
Proceedings of the 5th Canadian Conference on Computational Geometry, 1993

1992
A Simple Output-Sensitive Algorithm for Hidden Surface Removal.
ACM Trans. Graph., 1992

Arrangements of Curves in the Plane - Topology, Combinatorics and Algorithms.
Theor. Comput. Sci., 1992

Efficient Motion Planning for an L-Shaped Object.
SIAM J. Comput., 1992

Repeated Angles in the Plane and Related Problems.
J. Comb. Theory, Ser. A, 1992

Efficient Hidden Surface Removal for Objects with Small Union Size.
Comput. Geom., 1992

The number of edges of many faces in a line segment arrangement.
Combinatorica, 1992

Finding Effective "Force Targets" for Two-Dimensional Multifinger Frictional Grips.
Algorithmica, 1992

Randomized Incremental Construction of Delaunay and Voronoi Diagrams.
Algorithmica, 1992

Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems.
Algorithmica, 1992

A Combinatorial Bound for Linear Programming and Related Problems.
Proceedings of the STACS 92, 1992

Tail Estimates for the Space Complexity of Randomized Incremental Algorithms.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Applications of Parametric Searching in Geometric Optimization.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

A Subexponential Bound for Linear Programming.
Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992

Optical Computational Geometry.
Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992

Diameter, Width, Closest Line Pair, and Parametric Searching.
Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992

Castles in the Air Revisited.
Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992

1991
A Singly Exponential Stratification Scheme for Real Semi-Algebraic Varieties and its Applications.
Theor. Comput. Sci., 1991

On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm.
SIAM J. Comput., 1991

On Disjoint Concave Chains in Arrangements of (Pseudo) Lines.
Inf. Process. Lett., 1991

Tight bounds on a problem of lines and intersections.
Discrete Mathematics, 1991

On k-Sets in Arrangement of Curves and Surfaces.
Discrete & Computational Geometry, 1991

Merging Visibility Maps.
Comput. Geom., 1991

Improved Combinatorial Bounds and Efficient Techniques for Certain Motion Planning Problems with Three Degrees of Freedom.
Comput. Geom., 1991

Counting and Cutting Cycles of Lines and Rods in Space.
Comput. Geom., 1991

Off-line Dynamic Maintenance of the Width of a Planar Point Set.
Comput. Geom., 1991

Coordinated Motion Planning for Two Independent Robots.
Ann. Math. Artif. Intell., 1991

On the Zone of a Surface in a Hyperplane Arrangement.
Proceedings of the Algorithms and Data Structures, 1991

Applications of a New Space Partitioning Technique.
Proceedings of the Algorithms and Data Structures, 1991

Computing a Face in an Arrangement of Line Segments.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Planar Geometric Location Problems and Maintaining the Width of a Planar Set.
Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Ray Shooting in Polygons Using Geodesic Triangulations.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Fat Triangles Determine Linearly Many Holes
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Efficient Hidden Surface Removal for Objects with small Union Size.
Proceedings of the Seventh Annual Symposium on Computational Geometry, 1991

The Upper Envelope of Voronoi Surfaces and Its Applications.
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

Counting Circular Arc Intersections.
Proceedings of the Seventh Annual Symposium on Computational Geometry, 1991

On the Zone Theorem for Hyperplane Arrangements.
Proceedings of the New Results and New Trends in Computer Science, 1991

1990
Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection.
SIAM J. Comput., 1990

On the Two-Dimensional Davenport Schinzel Problem.
J. Symb. Comput., 1990

An Algorithm for Generalized Point Location and its Applications.
J. Symb. Comput., 1990

An Efficient Motion-planning Algorithm for a Convex Polygonal Object in Two Dimensional Polygonal Space.
Discrete & Computational Geometry, 1990

The Maximum Number of Ways To Stab n Convex Nonintersecting Sets in the Plane Is 2n-2.
Discrete & Computational Geometry, 1990

The Complexity of Many Cells in Arrangements of Planes and Related Problems.
Discrete & Computational Geometry, 1990

The Complexity and Construction of Many Faces in Arrangement of Lines and of Segments.
Discrete & Computational Geometry, 1990

Combinatorial Complexity Bounds for Arrangement of Curves and Spheres.
Discrete & Computational Geometry, 1990

The Caratheodory number for the k-core.
Combinatorica, 1990

Triangles in space or building (and analyzing) castles in the air.
Combinatorica, 1990

Storing Line Segments in Partition Trees.
BIT, 1990

A Hyperplane Incidence Problem with Applications to Counting Distances.
Proceedings of the Algorithms, 1990

Randomized Incremental Construction of Delaunay and Voronoi Diagrams.
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

Counting and Cutting Cycles of Lines and Rods in Space
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

A Hyperplane Incidence Problem with Applications to Counting Distances.
Proceedings of the Applied Geometry And Discrete Mathematics, 1990

Merging Visibility Maps.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

Slimming Down by Adding: Selecting Heavily Covered Points.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

The Combinatorial Complexity of Hyperplane Transversals.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

Points and Triangles in the Plane and Halving Planes in Space.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

Selecting Distances in the Plane.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

Algorithmic Motion Planning in Robotics.
Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), 1990

1989
Visibility Problems for Polyhedral Terrains.
J. Symb. Comput., 1989

Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences.
J. Comb. Theory, Ser. A, 1989

A Note on the Papadimitriou-Silverberg Algorithm for Planning Optimal Piecewise-Linear Motion of a Ladder.
Inf. Process. Lett., 1989

Computing the Geodesic Center of a Simple Polygon.
Discrete & Computational Geometry, 1989

The Upper Envelope of Piecewise Linear Functions and the Boundary of a Region Enclosed by Convex Plates: Combinatorial Analysis.
Discrete & Computational Geometry, 1989

On the General Motion-Planning Problem with Two Degrees of Freedom.
Discrete & Computational Geometry, 1989

The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.
Discrete & Computational Geometry, 1989

Implicitly Representing Arrangements of Lines or Segments.
Discrete & Computational Geometry, 1989

On Arrangement of Jordan Arcs with Three Intersection per Pair.
Discrete & Computational Geometry, 1989

Algorithmic Motion Planning in Robotics.
IEEE Computer, 1989

Lines in Space-Combinatorics, Algorithms and Applications
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

A Singly-Expenential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications.
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

Output-Sensitive Hidden Surface Removal
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988
On the shortest paths between two convex polyhedra.
J. ACM, 1988

The Shortest Watchtower and Related Problems for Polyhedral Terrains.
Inf. Process. Lett., 1988

Planar Realizations of Nonlinear Davenport-Schnitzel Sequences by Segments.
Discrete & Computational Geometry, 1988

Separating Two Simple Polygons by a Sequence of Translations.
Discrete & Computational Geometry, 1988

Computing the Link Center of a Simple Polygon.
Discrete & Computational Geometry, 1988

Improved lower bounds on the length of Davenport - Schinzel sequences.
Combinatorica, 1988

A Survey of Motion Planning and Related Geometric Algorithms.
Artif. Intell., 1988

Intersecting Line Segments, Ray Shooting, and Other Applications of Geometric Partitioning Techniques.
Proceedings of the SWAT 88, 1988

Theoretical and experimental studies using a multifinger planar manipulator.
Proceedings of the 1988 IEEE International Conference on Robotics and Automation, 1988

Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms.
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

Combinatorial Complexity Bounds for Arrangements of Curves and Surfaces
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

Coordinated Motion Planning for Two Independent Robots.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

An Automatic Motion Planning System for a Convex Polygonal Mobile Robot in 2-Dimensional Polygonal Space.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

On the General Motion Planning Problem with Two Degrees of Freedom.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

The Complexity of Many Faces in Arrangements of Lines of Segments.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

Implicitly Representing Arrangements of Lines or Segments.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

On Arrangements of Jordan Arcs with Three Intersections per Pair.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

Triangles in Space or Building (and Analyzing) Castles in the Air.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

1987
On Shortest Paths Amidst Convex Polyhedra.
SIAM J. Comput., 1987

On k-Hulls and Related Problems.
SIAM J. Comput., 1987

An Efficient and Simple Motion Planning Algorithm for a Ladder Amidst Polygonal Barriers.
J. Algorithms, 1987

On the Number of Critical Free Contacts of a Convex Polygonal Object Moving in Two-Dimensional Polygonal Space.
Discrete & Computational Geometry, 1987

Planning a Purely Translational Motion for a Convex Object in Two-Dimensional Space Using Generalized Voronoi Diagrams.
Discrete & Computational Geometry, 1987

Almost linear upper bounds on the length of general Davenport-Schinzel sequences.
Combinatorica, 1987

A New Efficient Motion-Planning Algorithm for a Rod in Two-Dimensional Polygonal Space.
Algorithmica, 1987

Generalized Voronoi Diagrams for a Ladder: II. Efficient Construction of the Diagram.
Algorithmica, 1987

On the Existence and Synthesis of Multifinger Positive Grips.
Algorithmica, 1987

Linear-Time Algorithms for Visibility and Shortest Path Problems Inside Triangulated Simple Polygons.
Algorithmica, 1987

Efficient algorithms for planning purely translational collision-free motion in two and three dimensions.
Proceedings of the 1987 IEEE International Conference on Robotics and Automation, Raleigh, North Carolina, USA, March 31, 1987

On the Bivariate Function Minimization Problem And Its Applications to Motion Planning.
Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

On the Lower Envelope of Bivariate Functions and its Applications
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

Computing the Link Center of a Simple Polygon.
Proceedings of the Third Annual Symposium on Computational Geometry, 1987

1986
On Shortest Paths in Polyhedral Spaces.
SIAM J. Comput., 1986

Object recognition by three-dimensional curve matching.
Int. J. Intell. Syst., 1986

Probabilistic Propositional Temporal Logics
Information and Control, 1986

On the Union of Jordan Regions and Collision-Free Translational Motion Amidst Polygonal Obstacles.
Discrete & Computational Geometry, 1986

Nonlinearity of Davenport - Schinzel sequences and of generalized path compression schemes.
Combinatorica, 1986

Geometric Applications of Davenport-Schinzel Sequences
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

A New Efficient Motion-Planning Algorithm for a Rod in Polygonal Space.
Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, 1986

On Shortest Paths Amidst Convex Polyhedra.
Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, 1986

Linear Time Algorithms for Visibility and Shortest Path Problems Inside Simple Polygons.
Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, 1986

1985
Intersection and Closest-Pair Problems for a Set of Planar Discs.
SIAM J. Comput., 1985

Concurrent Probabilistic Programs, Or: How to Schedule if You Must.
SIAM J. Comput., 1985

On Minima of Functions, Intersection Patterns of Curves, and Davenport-Schinzel Sequences
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Motion Planning in the Presence of Moving Obstacles
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

An efficient and simple motion planning algorithm for a ladder moving in two-dimensional space amidst polygonal barriers (extended abstract).
Proceedings of the First Annual Symposium on Computational Geometry, 1985

An efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles.
Proceedings of the First Annual Symposium on Computational Geometry, 1985

1984
Verification of Probabilistic Programs.
SIAM J. Comput., 1984

On Shortest Paths in Polyhedral Spaces
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Probabilistic Temporal Logics for Finite and Bounded Models
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

On k-hulls and Related Problems
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Nonlinearity of Davenport-Schinzel Sequences and of a Generalized Path Compression Scheme
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
Termination of Probabilistic Concurrent Program.
ACM Trans. Program. Lang. Syst., 1983

Experience with the SETL Optimizer.
ACM Trans. Program. Lang. Syst., 1983

Retraction: A New Approach to Motion-Planning (Extended Abstract)
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Concurrent Probabilistic Program, or: How to Schedule if You Must.
Proceedings of the Automata, 1983

1982
Some Observations Concerning Formal Differentiation of Set Theoretic Expressions.
ACM Trans. Program. Lang. Syst., 1982

Transformational Derivation of a Garbage Collection Algorithm.
ACM Trans. Program. Lang. Syst., 1982

Fast Composition of Sparse Maps.
Inf. Process. Lett., 1982

Some Modified Algorithms for Dijkstra's Longest Upsequence Problem.
Acta Inf., 1982

Termination of Probabilistic Concurrent Programs.
Proceedings of the Conference Record of the Ninth Annual ACM Symposium on Principles of Programming Languages, 1982

1981
An Automatic Technique for Selection of Data Structures in SETL Programs.
ACM Trans. Program. Lang. Syst., 1981

Formal Integration: A Program Transformation Technique.
Comput. Lang., 1981

Data Flow Analysis of Applicative Programs.
Proceedings of the Automata, 1981

1980
Structural Analysis: A New Approch to Flow Analysis in Optimizing Compilers.
Comput. Lang., 1980

1979
The design of a global optimizer.
Proceedings of the 1979 SIGPLAN Symposium on Compiler Construction, 1979

Automatic Data Structure Selection in SETL.
Proceedings of the Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, 1979


  Loading...