Shape Matching & Analysis / Clustering & Classification / Proximity / Kinetic Algorithms / Computational Molecular Biology / GIS & Global Change  / Robotics / Computer Graphics & Visualization / Data Structures / Arrangements / Combinatorial Geometry
 Shape Matching and Analysis
"Computing a segment-center for a planar point set," with A. Efrat, M. Sharir, and S. Toledo, J. Algorithms, 15 (1993), 314-323.
"Approximation algorithms for bipartite and nonbipartite matchings in the plane," with K. R. Varadarajan, in 10th ACM-SIAM Symp. Discrete Algorithms, 1999.  
"Exact and approximation algorithms for the minimum width annuli and shells," with B. Aronov, S. Har-Peled and M. Sharir, Discrete Comput. Geom., 24 (2000), 687-705.  
"Approximation algorithms for layered manufacturing," with P. K. Desikan, in 11th ACM-SIAM Symp. Discrete Algorithms, 2000.  
"Exact and approximation algorithms for minimum-width cylindrical shells," with B. Aronov and M. Sharir, Discrete Comput. Geom., 26 (2001), 307-320.  
"On the numbers of congruent simplices in a point set," with M. Sharir, Geometry, 28 (2002), 123–150.  
"Computing the detour of polygonal curves," with R. Klein, C. Knauer, and M. Sharir, submitted for publication.  
“Computing the writhing number of a polygonal knot,” with H. Edelsbrunner and Y.Wang, Discrete Comp. Geom., 32 (2004), 37–54.  
"Hausdorff distance under translation for points, and balls," with S. Har-Peled, M. Sharir, and Y. Wang, in 17th Annual Sympos. Comput. Geom., 2003.  
"Streaming geometric optimization using graphics hardware," with Krishnan, N. H. Mustafa, and S. Venkatasubramanian, in 11th Annual European Sympos. Algorithms, 2003.  
"Approximating extent measures of points," with S. Har-Peled and K.R. Varadarajan, J. ACM, 51 (2004), 606–635  
“Practical methods for shape fitting and kinetic data structures using core sets,” with R. Poreddy, K. Varadarajan, and H. Yu, 20th Annual Sympos. on Comput. Geom., 2004.  
“Efficient algorithms for bichromatic separability,” with B. Aronov and V. Koltun, in 15th Annual ACM-SIAM Sympos. Discrete Algorithms, 2004.  
“Extreme Elevation on a 2-Manifold,” with H. Edelsbrunner, J. Harer, and Y.Wang, 20th Annual Sympos. Comput. Geom., 2004.  
“A near-linear algorithm for Euclidean bipartite matching,” with K. R. Varadarajan, in 20th Annual Symp. on Comput. Geom., 2004.
 Clustering and Classification
"Planar geometric location problems," with M. Sharir, Algorithmica, 11 (1994), 185-195.
"Applications of parametric searching in geometric optimization," with M. Sharir and S. Toledo, J. Algorithms, 17 (1994), 292-318.  
"Efficient randomized algorithms for some geometric optimization problems," with M. Sharir, Discrete Comp. Geom., 16 (1996), 317-337.  
"Linear approximation of convex objects," with K. Varadarajan, Inform. Process. Letts., 62 (1997), 89-94.  

"The discrete 2-center problem," with M. Sharir and E. Welzl, Discrete Comp. Geom., 20 (1998), 287–306.

  

“Exact and approximation algorithms for clustering,” with C. M. Procopiuc, Algorithmica, 33 (2002), 201–226.

  

“Output-sensitive algorithms for uniform partitions of points,” with B. Bhattacharya and S. Sen, Algorithmica, 32 (2002), 521–539.

  
“Classification using projective clustering,” with C. M. Procopiuc, M. Jones, and T.M. Murali, in ACM SIGMOD Int. Conf. Management Data, 2002.  
"A Monte Carlo Algorithm for Fast Projective Clustering," with C. M. Procopiuc, M. Jones, and T. M. Murali, in ACM SIGMOD Conf. Data Management, 2002.  

“Approximation algorithms for projective clustering,” with C. M. Procopiuc, Journal of Algorithms, 46 (2003), 115–139.

 
"An approximation algorithm for computing the two-line center," with C. M. Procopiuc and K. R. Varadarajan, Computat. Geom.: Theory and Appls., 26 (2003), 119-28.  
“k-means projective clustering,” with N. H. Mustafa, in 23rd Annual Sympos. Principles of Database Systems, 2004.  

"Approximation algorithms for k-line center," with C. M. Procopiuc and K. Varadarajan, to appear in Algorithmica.

  
“Object space segmentation by geometric reference structures,” with D. Brady and J. Matousek, submitted to ACM Transacations on Sensor Networks
 Proximity
"Algorithms for special cases of rectilinear Steiner trees: I. Points on the boundary of a rectangle," with M. T. Shing, Networks, 20 (1990), 453-485.
"Computing all external-farthest neighbors for a simple polygon," with A. Aggarwal, B. Aronov, S. Kosaraju, B. Shieber, and S. Suri, Discrete and Applied Math, 31 (1991), 97-111.  
"Euclidean minimum spanning tree and bichromatic closest pairs," with H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, Discrete Comp. Geom. 6 (1991), 407-422.  
"Off-line dynamic maintenance of the width of a planar point set," with M. Sharir, Computational Geometry: Theory and Appls, 1 (1991), 65-78.  
"Oriented aligned rectangle packing problem," with M. T. Shing, European J. Operations Research, 62 (1992), 210-220.  
"Farthest neighbors, maximum spanning trees and related problems in higher dimensions," with J. Matousek and S. Suri, Comput. Geom.: Theory & Appls, 1 (1992), 189-201.  
"Relative neighborhood graphs in three dimensions," with J. Matousek, Computational Geometry: Theory and Appls, 2 (1992), 1-15.  
"Selecting distances in the plane," with B. Aronov, M. Sharir, and S. Suri, Algorithmica, 9 (1993), 495-514.  
"Selection in monotone matrices and k-th nearest neighbors," with S. Sen, J. Algorithms, 20 (1996), 581-601.  
"Translating a planar object to maximize point containment," with T. Hagerup, R. Ray, M. Sharir, M. Smid, and E. Welzl, in 10th Annual European Sympos. Algorithms, 2002.  
“Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks,” with M. Overmars and M. Sharir, in 15th Annual ACM-SIAM Sympos. Discrete Algorithms, 2004.  
“Algorithms for center and Tverberg points,” with M. Sharir and E. Welzl, in 20th Annual Sympos. Comput. Geom., 2004.  
“A lower bound on weighted spanners,” with Y. Wang, to appear in 16th Annual ACM-SIAM Sympos. Discrete Algorithms, 2005.
 Kinetic Algorithms
"Cylindrical static and kinetic binary space partitions," with L. Guibas, T.M. Murali, and J.S. Vitter, Comput. Geom: Theory & Appls., 16 (2000), 103-127.
"Kinetic binary space partitions for intersecting segments and disjoint triangles," with J. Erickson and L. Guibas, in 9th ACM-SIAM Symp. Discrete Algorithms, 1998.  
"Parametric and kinetic minimum spanning trees," with D. Eppstein, L.J. Guibas, and M. Henzinger, in 39th Annu. Sympos. on Foundations of Computer Science, 1998.  
"Lower bounds for kinetic planar subdivisions," with J. Basch, M. de Berg, L. J. Guibas, and J. Hershberger, Discrete Comput. Geom., 24 (2000), 721-733.  
"Indexing moving points," with L. Arge and J. Erickson, in 19th ACM Symp. on Principles of Database Systems, 2000.  
"Maintaining the approximate extent measures of moving points," with S. Har-Peled, in 12th ACM-SIAM Symp. Discrete Algorithms,, 2001.  
"Deformable free space tiling for kinetic collision detection," with J. Basch, L. J. Guibas, J. Hershberger, and L. Zhang, Intl. J. Robotics Research, 21 (2002), 179–197.  

“Maintaining structures for moving points,” with L. Guibas, J. Hershberger, and E. Veach, Discrete and Computational Geometry, 26 (2001), 253–374.

 
"Time responsive indexing schemes for moving points," with L. Arge and J. Vahrenhold, in 7th Workshop on Algorithms and Data Structures, 2001.  

 

 "STAR-tree: An efficent self-adjusting index for moving points," with C. M. Procopiuc and S. Har-Peled, in 4th Workshop on Algorithms Engineering and Experiments, 2002.  
“Kinetic medians and kd-trees,” with J. Gao and L. J. Guibas, in 10th European Sympos. Algorithms, 2002.  
“Collision detection for deforming necklaces,” with L. J. Guibas, A. Nguyen, D. Russel, and L. Zhang, Comput. Geom.: Theory & Appls, 28 (2004), 137–163.  
“Efficient tradeoff schemes in data structures for querying moving objects,” with L. Arge, J. Erickson, and H. Yu, in 12th European Sympos. Algorithms, 2004.  

“A 2D Triangulation with near-quadratic topological changes,” with Y. Wang and H. Yu, in 20th Annual Sympos. Comput. Geom., 2004.

 
“Staying in the middle: Exact and approximate medians in R1 and R2 for moving points,” with M. de Berg, J. Gao, L. Guibas, and S. Har-Peled, submitted for publication.
 Computational Molecular Biology
“Computing the writhing number of a polygonal knot,” with H. Edelsbrunner and Y.Wang, Discrete Comp. Geom., 32 (2004), 37–54.
“Collision detection for deforming necklaces,” with L. J. Guibas, A. Nguyen, D. Russel, and L. Zhang, Comput. Geom.: Theory & Appls, 28 (2004), 137–163.  
“Local search heuristic for rigid protein docking,” with V. Choi, H. Edelsbrunner, and J. Rudolph, in Proc. 4th Workshop on Algorithms in Bioinformatics, 2004.  
“Near-linear time approximation algorithms for curve simplification,” with S. Har-Peled, N. Mustafa, and Y. Wang, to appear in Algorithmica.  
“Coarse and reliable geometric alignment for protein docking,” with Y.Wang, P. Brown, H. Edelsbrunner, and J. Rudolph, to appear in Pacific Sympos. on Biocomput., 2005.  

“Extreme elevation on a 2-manifold,” with H. Edelsbrunner, J. Harer, and Y. Wang, in 20th Annual Sympos. Comput. Geom., 2004.

 
“Faster approximation algorithm for computing the contact-map overlap,” with N. Mustafa and Y.Wang, submitted to J. Comput. Biol.  
“Faster algorithms for optimal multiple sequence alignment based on pairwise comparisons,” with Y. Bilu and R. Kolodny, submitted to 9th Annual Conf. Res. in Comput. Mol. Biol., 2005.
 GIS and Global Change
"KBGIS-II: A knowledge-based geographic information system," with T. Smith, D. Peuquet, and S. Menon, Intl. J. GIS, 1 (1987), 149-172.
"Polygon and connected component intersection searching," with M. van Kreveld, Algorithmica, 15 (1996), 626-660.  
"An Efficient Algorithm for Terrain Simplification," with P. K. Desikan, in 8th ACM-SIAM Symp. Discrete Algorithms, 1997.  
"Approximating Shortest Paths on a Convex Polytope in Three Dimensions," with S. Har-Peled, M. Sharir, and K. Varadarajan, J. ACM, 44 (1997), 567-584.  
"Label placement by maximum independent set in rectangles," with M. van Kreveld and S. Suri, Comput. Geom.: Theory & Appls., 11 (1998), 209-218.  
"I/O-Efficient algorithms for contour line extraction and planar graph blocking," with L. Arge, T.M. Murali, K. Varadarajan, and J.S. Vitter, in 9th ACM-SIAM Symp. Discrete Algorithms, 1998.  
"A simple and efficient algorithm for high quality line labeling," with L. Knipping, M. van Kreveld, T. Strijk, and A. Wolff, in Innovations in GIS VII: GeoComputation, (P. M. Atkinson and D. Martin, eds.), Taylor and Francis, London, 2000, pp. 147-159.  
"Efficient algorithms for polygon simplification," with K. R. Varadarajan, Discrete and Comput. Geom., 23 (2000), 273-291.  
"Approximating shortest paths on a nonconvex polyhedron," with K. Varadarajan, SIAM J. Comput. 30 (2001), 1321-1340.  
"The extinction debt revisited: Population dynamics in a continuous space model," with M. Dietze, S. Govindarajan, and J. Clark, in Ecological Society of America Annual Meeting, 2001.  

“Computing approximate shortest paths on convex polytopes,” with S. Har-Peled and M. Karia, Algorithmica, 33 (2002), 227–242.

  
"Reporting all intersecting pairs of polytopes in two and three dimensions," with M. de Berg, S. Har-Peled, M. Overmars, M. Sharir, and J. Vahrenhold, Comput. Geom. 23 (2002), 195-208.  
“The paradox of species diversity,” with J. Clark, M. Dietze, and S. Govindarajan, in Ecological Society of America Annual Meeting, 2003.  
“A scalable simulator for forest dynamics,” with S. Govindrajan, M. Dietze, and J. Clark, in 20th Annual Sympos. Comput. Geom., 2004.  

"Near-linear time approximation algorithms for curve simplification," with S. Har-Peled, N. Mustafa, and Y. Wang, to appear in Algorithmica.

  
"A scalable algorithm for dispersing population," with S. Govindarajan, M. Dietze, and J. Clark, to appear in J. Intelligent Information Systems.
 Robotics
"Red-blue intersection detection algorithms, with applications to motion planning and collision detection," with M. Sharir, SIAM J. Comput., 19 (1990), 297-322.
"Motion planning for a steering-constrained robot through moderate obstacles," with P. Raghavan and H. Tamaki, in 27th ACM Symp. Theory of Computing, 1995.  
"Computing depth orders in multiple directions," with M. de Berg, D. Halperin, and M. Sharir, in 7th ACM-SIAM Symp. Discrete Algorithms, 1996.  
"Approximation algorithms for shortest paths with bounded curvature," with H. Wang, SIAM J. Comput., 30 (2001), 1739-1772.  
"Largest Placements and Motion Planning of a Convex Polygon," with N. Amenta, B. Aronov, and M. Sharir, in 2nd International Workshop on Algorithmic Foundation of Robotics, 1996.  
"Star unfolding of a polytope with applications," with B. Aronov, J. O'Rourke, and C. Schevon, SIAM J. Comput., 26 (1997), 1689-1713.  
"Nonholonomic Path Planning for Pushing a Disk Among Obstacles," with J.-C. Latombe, R. Motwani, and P. Raghavan, in IEEE Conf. on Robotics and Automation, 1997.  
"Motion planning of a ball amid segments in three dimensions," with M. Sharir, in 10th ACM-SIAM Symp. Discrete Algorithms, 1999.  
"Motion Planning for a Convex Polygon in a Polygonal Environment," with B. Aronov and M. Sharir, Discrete and Comput. Geom., 22 (1999), 201-221.  
"Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions," with M. Sharir, Discrete Comput. Geom., 24 (2000), 645-685.  
"Computing the penetration depth of two convex polytopes in 3D," with L. J. Guibas, S. Har-Peled, A. Rabinovitch, and M. Sharir, Nordic J. Computing, 7(2000), 227-240.  

"Curvature-constrained shortest paths in a convex polygon," with T. Biedl, S. Lazard, S. Robbins, S. Suri, and S. Whitesides, SIAM Journal on Computing, 31 (2002), 1814–1852.

  

"Deformable free space tiling for kinetic collision detection," with J. Basch, L. J. Guibas, J. Hershberger, and L. Zhang, Intl. J. Robotics Research, 21 (2002), 179–197.

  
"Polygon decomposition for efficient construction of Minkowski sums," with E. Flato and D. Halperin, Comput. Geom.: Theory & Appls., 21 (2002), 21-38.  
"Minimal trap design," with A. Collins and J. Harer, in IEEE Conference on Robotics and Automation, 2001  
"HPRM: A hierarchical PRM," with A. Collins and J. Harer in Proc. Intl Conf. Robotics and Automation , 2003.  

“A near-quadratic algorithm for fence design,” with R.-P. Berretty and A. D. Collins, to appear in Discrete and Computational Geometry.
 Computer Graphics and Visualization
"On the number of views of polyhedral terrains," with M. Sharir, Discrete and Comput. Geom., 12 (1994), 177-182.
"Computing depth orders and related problems," with M. Katz and M. Sharir, Comput. Geom: Theory & Appls., 5 (1995), 187-206.  
"Simplification envelopes," with J. Cohen, A. Varshney, D. Manocha, G. Turk, F. Brooks, H. Weber, and W. Wright, in SIGGRAPH, 1996.  
"Practical techniques for constructing binary space partition for orthogonal rectangles," with T.M. Murali and J.S. Vitter, in 13th ACM Symp. Comput. Geom., 1997.  
"Surface approximation and geometric partitions," with S. Suri, SIAM J. Comput. 27 (1998), 1016-1035.  
"Kinetic binary space partitions for intersecting segments and disjoint triangles," with J. Erickson and L. Guibas, in 9th ACM-SIAM Symp. Discrete Algorithms, 1998.  
"Binary space partitions for fat rectangles," with E. Grove, T.M. Murali, and J.S. Vitter, SIAM J. Comput., 29 (2000), 1422-1448.  
"Cylindrical static and kinetic binary space partitions," with L. Guibas, T.M. Murali, and J.S. Vitter, Comput. Geom: Theory & Appls., 16 (2000), 103-127.  
"Lower bounds for kinetic planar subdivisions," with J. Basch, M. de Berg, L. J. Guibas, and J. Hershberger, Discrete Comput. Geom., 24 (2000), 721-733.  
"Occlusion culling for fast walkthrough in urban areas," with S. Har-Peled and Y. Wang, in Eurographics, 2001.
 Data Structures
"Ray shooting and other applications of spanning trees with low stabbing number," SIAM J. Comput. 22 (1992), 540-570.
"Intersection queries in sets of discs," with M. van Kreveld and M. Overmars, BIT 32 (1992), 268-279.  
"Circle shooting in a simple polygon," with M. Sharir, J. Algorithms 14 (1993), 68-87.  
"Ray shooting and parametric search," SIAM J. Comput. 22 (1993), 794-806.  
"Intersection queries in curved objects," with M. van Kreveld and M. Overmars, J. Algorithms 15 (1993), 229--266.  
"Range searching with semialgebraic sets," with J. Matousek, Discrete Comput. Geom., 11 (1994), 393-418.  
"Dynamic half-space searching and its applications," with J. Matousek, Algorithmica, 14 (1995), 325-345.  
"Polygon and connected component intersection searching," with M. van Kreveld, Algorithmica, 15 (1996), 626-660.  
"Ray shooting among convex polytopes in 3D," with M. Sharir, SIAM J. Comput., 25 (1996), 100-116.  
"Ray shooting amidst convex polygons in 2D," with M. Sharir, J. Algorithms, 21 (1996), 508-519.  
"Parametric and kinetic minimum spanning trees," with D. Eppstein, L.J. Guibas, and M. Henzinger, in 39th Annual Sympos. on Foundations of Computer Science, 1998.  
"I/O efficient dynamic point location in monotone planar subdivisions," with L. Arge, G. S. Brodal, and J. S. Vitter, in 10th ACM-SIAM Symp. Discrete Algorithms, 1999.  
"Efficient searching with linear constraints," with L. Arge, J. Erickson, P. G. Franciosa, and J. S. Vitter, J. Computer and Systems Sciences, 61 (2000), 194-216.  
"A framework for index bulk loading and dynamization," with L. Arge, O. Procopiuc, and J. S. Vitter, in 28th Intl. Conf. on Automata, Languages, and Programming, 2001.  

“Box-trees and R-trees with near-optimal query time,” with M. de Berg, J. Gudmundsson, M. Hammar, and H. J. Haverkort, Discrete and Computational Geometry, 28 (2002), 291–312.

 
"STAR-tree: An efficent self-adjusting index for moving points," with C. M. Procopiuc and S. Har-Peled, in 4th Workshop on Algorithms Engineering and Experiments, 2002.  
"Kinetic medians and kd-trees," with J. Gao and L. Guibas, in 10th Annual European Sympos. Algorithms, 2002.  
"Range searching in categorical data: Colored range searching on grid-trees," with S. Govindarajan and S. Muthukrishnan, in 10th Annual European Sympos. Algorithms, 2002.  
"CRB-tree: An efficient indexing scheme for range aggregate queries," with S. Govindarajan and L. Arge, in 9th Intl. Conf. on Database Theory, 2003.  

“Indexing moving points,” with L. Arge and J. Erickson, Journal of Computer and Systems Sciences, 66 (2003), 207–243.

  
"On cache-oblivious multidimensional range searching ," with L. Arge, A. Danner , and B. Holland-Minkley, in 17th Annual Sympos. Comput. Geom., 2003.  
"Bkd-tree: A dynamic scalable kd-tree," with O. Procopiuc, L. Arge, and J. S. Vitter, in 8th Annual Sympos. Spatio Temporal Databases, 2003.  
"I/O-Efficient structures for orthogonal range max and stabbing max queries," with L. Arge, J. Yang, and K. Yi, in 11th Annual European Sympos. Algorithms, 2003.  
“Collision detection for deforming necklaces,” with L. J. Guibas, A. Nguyen, D. Russel, and L. Zhang, Comput. Geom.: Theory & Appls, 28 (2004), 137–163.  
“An optimal dynamic interval stabbing-max data structure?” with L. Arge and K. Yi, to appear in 16th Annual ACM-SIAM Sympos. Discrete Algorithms, 2005.
 Arrangements
"Partitioning arrangements of lines: I. A deterministic algorithm," Discrete Comp. Geom., 5 (1990), 449-483.
"Partitioning arrangements of lines: II. Applications," Discrete Comp. Geom., 5 (1990), 533-573.  
"Counting facets and incidences,"` with B. Aronov, Discrete Comp. Geom., 7 (1992), 359-369.  
"Applications of a new space partitioning technique," with M. Sharir, Discrete Comp. Geom., 9 (1993), 11-38.  
"Counting circular arc intersections," with M. Pellegrini and M. Sharir, SIAM J. Comput., 22 (1993), 778-793.  
"Implicit point location in arrangement segments with application to motion planning," with M. van Kreveld, Intl. J. Comput. Geom. & Appls., 4 (1994), 369-383.  
"The overlay of envelopes and their applications," with O. Schwarzkopf and M. Sharir, Discrete Comp. Geom., 15 (1996), 1-13.  
"Computing envelopes in four dimensions with applications," with B. Aronov and M. Sharir, SIAM J. Comput., 26 (1997), 1714-1732.  
"On levels in arrangements of lines, segments, planes, and triangles," with B. Aronov, T.M. Chan, and M. Sharir, Discrete Comp. Geom., 19 (1998), 315-331.  
"Constructing levels in arrangements and higher order Voronoi diagrams," with M. de Berg, J. Matousek, and O. Schwarzkopf, SIAM J. Comput. 27 (1998), 654-667.  
"Computing many faces in arrangements of lines and segments," with J. Matousek and O. Schwarzkopf, SIAM J. Comput., 27 (1998), 491-505.  
"Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions," with M. Sharir, Discrete Comput. Geom., 24 (2000), 645-685.  
"Line transversals of balls and smallest enclosing cylinders in three dimensions," with B. Aronov and M. Sharir, Discrete Comput. Geom. 21 (1999), 373-388.  
"Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications," with A. Efrat and M. Sharir, SIAM J. Comput. 29 (2000), 912-953.  

"On the complexity of many faces in arrangements of circles," with B. Aronov and M. Sharir, to appear in Discrete and Computational Geometry: The Goodman-Pollack Festschrift (B. Aronov, S. Basu, J. Pach, and M. Sharir, eds.), Springer Verlag, Berlin, 2003, pp. 1–24.

  
"Lenses in arrangements of pseudo-circles and their applications," with E. Nevo, J. Pach, R. Pinchasi, M. Sharir, and S. Smorodinsky, J. ACM 51 (2004), 139-186.  
“Approximating independent sets in segment-intersection graphs,” with N. H. Mustafa, in 9th Scandinavian Workshop on Algorithm Theory, 2004.  
"Pseudoline Arrangements: Duality, Algorithms, and Applications," with M. Sharir, to appear in SIAM J. Comput.  
“Independent set of intersection graphs of convex objects in 2D,” with N. H. Mustafa, submitted to Computat. Geom: Theory & Appls.
 Combinatorial Geometry
"Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences," with M. Sharir and P. Shor, J. Combin. Theory, Series A, 52 (1989), 228-274.
"Counting facets and incidences," with B. Aronov, Discrete Comp. Geom., 7 (1992), 359-369.  
"Can visibility graphs be represented compactly?" with N. Alon, B. Aronov, and S. Suri, Discrete Comput. Geom., 12 (1994), 347-365.  
"On stabbing lines for convex polyhedra in 3D," Comput. Geom.: Theory & Appls., 4 (1994), 177-189.  
"Line stabbing bounds on triangulations in 3D," with B. Aronov and S. Suri, in 11th ACM Symp. Comput. Geom., 1995.  
"The overlay of envelopes and their applications," with O. Schwarzkopf and M. Sharir, Discrete Comp. Geom., 15 (1996), 1-13.  
"Quasi-planar graphs have a linear number of edges," with B. Aronov, J. Pach, R. Pollack, and M. Sharir, Combinatorica, 17 (1997), 1-9.  
"On levels in arrangements of lines, segments, planes, and triangles," with B. Aronov and M. Sharir, in 13th ACM Symp. Comput. Geom., 1997.  

"On the numbers of congruent simplices in a point set," with M. Sharir, Geometry, 28 (2002), 123–150.

  
"On the complexity of many faces in arrangements of circles," with B. Aronov and M. Sharir, in Discrete and Computational Geometry: The Goodman-Pollack Festschrift (B. Aronov, S. Basu, J. Pach, and M. Sharir, eds.), Springer Verlag, Berlin, 2003, pp. 1–24.  
"Lenses in arrangements of pseudo-circles and their applications," with E. Nevo, J. Pach, R. Pinchasi, M. Sharir, and S. Smorodinsky, J. ACM 51 (2004), 139-186.  
“On lines avoiding unit balls in three dimensions,” with B. Aronov, V. Koltun, and M. Sharir, to appear in Discrete Comput. Geom.  
“Algorithms for center and Tverberg points,” with M. Sharir and E. Welzl, to appear in 20th Annual Sympos. Comput. Geom., 2004.  
“Object space segmentation by geometric reference structures,” with D. Brady and J. Matousek, submitted to ACM Transacations on Sensor Networks