Robot Motion Planning

• Smoothed Analysis of Probabilistic Roadmaps, Computational Geometry: Theory and Applications, to appear (with Siddhartha Chaudhuri). Also in 4th SIAM Workshop on Analytic Algorithms and Combinatorics, 2007. Also in 23rd European Workshop on Computational Geometry, 2007
• Pianos are not Flat: Rigid Motion Planning in Three Dimensions, 16th ACM-SIAM Symposium on Discrete Algorithms, 505-514, 2005

Overlays of Envelopes

• On Overlays and Minimization Diagrams, 22nd ACM Symposium on Computational Geometry, 395-401, 2006 (with Micha Sharir)
• Matching Polyhedral Terrains Using Overlays of Envelopes, Algorithmica 41, 159-183, 2005 (with Carola Wenk). Also in 9th Scandinavian Workshop on Algorithm Theory, 114-126, 2004
• The Partition Technique for Overlays of Envelopes, SIAM Journal on Computing 32, 841-863, 2003 (with Micha Sharir). Also in 43rd IEEE Symposium on Foundations of Computer Science, 637-646, 2002
• On the Overlay of Envelopes in Four Dimensions, 13th ACM-SIAM Symposium on Discrete Algorithms, 810-819, 2002 (with Micha Sharir)

Voronoi Diagrams

• Ready, Set, Go! -- The Voronoi Diagram of Moving Points that Start from a Line, Information Processing Letters 89, 233-235, 2004
• Polyhedral Voronoi Diagrams of Polyhedra in Three Dimensions, Discrete and Computational Geometry 31, 83-124, 2004 (with Micha Sharir). Also in 18th ACM Symposium on Computational Geometry, 227-236, 2002
• 3-Dimensional Euclidean Voronoi Diagrams of Lines with a Fixed Number of Orientations, SIAM Journal on Computing 32, 616-642, 2003 (with Micha Sharir). Also in 18th ACM Symposium on Computational Geometry, 217-226, 2002. Also in 18th European Workshop on Computational Geometry, 1-3, 2002

Vertical Decompositions

• Almost Tight Upper Bounds for Vertical Decompositions in Four Dimensions, Journal of the ACM 51, 699-730, 2004. Also in 42nd IEEE Symposium on Foundations of Computer Science, 56-65, 2001
• Sharp Bounds for Vertical Decompositions of Linear Arrangements in Four Dimensions, Discrete and Computational Geometry 31, 435-460, 2004. Also in 7th Workshop on Algorithms and Data Structures, 99-110, 2001

Arrangements and Discrete Geometry

• On Lines Avoiding Unit Balls in Three Dimensions, Discrete and Computational Geometry, 34, 231-250, 2005 (with Pankaj K. Agarwal, Boris Aronov, and Micha Sharir). Also in 20th ACM Symposium on Computational Geometry, 36-45, 2004
• On the Union of Kappa-Round Objects in Three and Four Dimensions, Discrete and Computational Geometry, to appear (with Boris Aronov, Alon Efrat, and Micha Sharir). Also in 20th ACM Symposium on Computational Geometry, 383-390, 2004
• Incidences Between Points and Circles in Three Dimensions, Discrete and Computational Geometry 33, 185-206, 2005 (with Boris Aronov and Micha Sharir). Also in 18th ACM Symposium on Computational Geometry, 116-122, 2002

Miscellaneous Geometric Algorithms

• Separability with Outliers, 16th International Symposium on Algorithms and Computation, 28-39, 2005 (with Sariel Har-Peled)
• Efficient Algorithms for Bichromatic Separability, ACM Transactions on Algorithms, to appear (with Pankaj K. Agarwal and Boris Aronov). Also in 15th ACM-SIAM Symposium on Discrete Algorithms, 675-683, 2004
• Segment Intersection Searching Problems in General Settings, Discrete and Computational Geometry 30, 25-44, 2003. Also in 17th ACM Symposium on Computational Geometry, 197-206, 2001. Also in 17th European Workshop on Computational Geometry, 89-92, 2001

Cutting Things

• Curve-Sensitive Cuttings, SIAM Journal on Computing 34, 863-878, 2005 (with Micha Sharir). Also in 19th ACM Symposium on Computational Geometry, 136-143, 2003
• Cutting Triangular Cycles of Lines in Space, Discrete and Computational Geometry, 33, 231-247, 2005 (with Boris Aronov and Micha Sharir). Also in 35th ACM Symposium on Theory of Computing, 547-555, 2003. Also in 19th European Workshop on Computational Geometry, 93-96, 2003

Geometric Computing in the Wild

• Near-Optimal Pricing in Near-Linear Time, 9th Workshop on Algorithms and Data Structures, 422-431, 2005 (with Jason Hartline)
• Approximately Dominating Representatives, Theoretical Computer Science, to appear (with Christos H. Papadimitriou). Also in 10th International Conference on Database Theory, 204-214, 2005
• Hardware-Assisted Natural Neighbor Interpolation, 7th Workshop on Algorithm Engineering and Experiments, 2005 (with Quanfu Fan, Alon Efrat, Shankar Krishnan, and Suresh Venkatasubramanian)
• Efficient Algorithms for Shared Camera Control, 19th ACM Symposium on Computational Geometry, 68-77, 2003 (with Sariel Har-Peled, Dezhen Song, and Ken Goldberg)

Visibility Processing

• Hardware-Accelerated From-Region Visibility Using a Dual Ray Space, 12th Eurographics Workshop on Rendering, 204-214, 2001 (with Daniel Cohen-Or and Yiorgos Chrysanthou)
• Virtual Occluders: an Efficient Intermediate PVS Representation, 11th Eurographics Workshop on Rendering, 59-70, 2000 (with Daniel Cohen-Or and Yiorgos Chrysanthou)
• Selecting Effective Occluders for Visibility Culling, Eurographics 2000 (short presentations track), 165-169, 2000 (with Daniel Cohen-Or)