• Home
• Research
• Publications
• Software
• Students
• Teaching
• BioSktech
• Contact

publications :: Books | Surveys | Papers | Slides

Shape Analysis / Clustering and Classification / Proximity / Kinetic Algorithms / Computational Molecular Biology / GIS and Terrain Modeling / Ecological Modeling / Robotics / Geometric Data Structures / Arrangements / Combinatorial Geometry / Sensor Networks / Core Sets / Computer Graphics and Visualization

Shape 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.
• "Approximation algorithms for layered manufacturing," with P. K. Desikan, in 11th ACM-SIAM Symp. Discrete Algorithms, 2000.
• "Approximation and exact algorithms for minimum-width annuli and shells," with B. Aronov, S. Har-Peled and M. Sharir, Discrete Comput. Geom., 24 (2000), 687-705.
• "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, Discrete Comput. Geom., 28 (2002), 123-150.
• "Hausdorff distance under translation for points, and balls," with S. Har-Peled, M. Sharir, and Y. Wang, in 17th Annual Symp. Comput. Geom. 2003.
• "Streaming geometric optimization using graphics hardware," with Krishnan, N. H. Mustafa, and S. Venkatasubramanian, in 11th Annual European Symp. Algorithms, 2003.
• "Approximating extent measures of points," with S. Har-Peled and K.R. Varadarajan, J. ACM, 51 (2004), 606-635.
• "Computing the writhing number of a polygonal knot, with H. Edelsbrunner and Y.Wang, Discrete Comp. Geom., 32 (2004), 37-54.
• "A near-linear constant-factor approximation for Euclidean bipartite matching, with K. R. Varadarajan, in 20th Annual Symp. on Comput. Geom., 2004.
• "Near-linear time approximation algorithms for curve simplification," with S. Har-Peled, N. Mustafa, and Y. Wang, Algorithmica, 42 (2005), 203-219.
• "Extreme Elevation on a 2-Manifold,"with H. Edelsbrunner, J. Harer, and Y. Wang, Discrete and Computational Geometry, 36 (2006), 553-572.
• "On bipartite matching under the rms distance," with J. Phillips, in 17th Canadian Conf. Comput. Geom., 2006.
• "A space-optimal data-stream algorithm for coresets in the plane," with H. Yu, in 23rd Annual Symp. Comput. Geom., 2007.
• "On polyhedra induced by point sets in space," with F. Hurtado, G. T. Toussaint, and J. Trias, Discrete Applied Mathematics, 156 (2008), 42-54.
• "Robust shape fitting via peeling and grating coresets," with S. Har-Peled and H. Yu, Discrete Comput. Geom. 39 (2008), 38-58.
• "Practical methods for shape fitting and kinetic data structures using coresets," with R. Poreddy, K. Varadarajan, and H. Yu, to appear in Algorithmica.
• "A space-optimal data-stream algorithm for coresets in the plane," with H. Yu, submitted to Discrete Comput. Geom.

Clustering and Classification

• "Applications of parametric searching in geometric optimization," with M. Sharir and S. Toledo, J. Algorithms, 17 (1994), 292-318.
• "Planar geometric location problems," with M. Sharir, Algorithmica, 11 (1994), 185-195.
• "Efficient randomized algorithms for some geometric optimization problems," with M. Sharir, Discrete Comput. 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.
• "A Monte Carlo algorithm for fast projective clustering," with C. M. Procopiuc, M. Jones, and T.M. Murali, in ACM SIGMOD Int. Conf. Management Data, 2002.
• "Output-sensitive algorithms for uniform partitions of points," with B. Bhattacharya and S. Sen, Algorithmica, 32 (2002), 521-539.
• "A (1 + ε)-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.
• "Approximation algorithms for projective clustering," with C. M. Procopiuc, Journal of Algorithms, 46 (2003), 115-139.
• "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. R. Varadarajan, Algorithmica, 42 (2005), 221-230.
• "Computing maximally separated sets in the plane," with M. Overmars and M. Sharir, SIAM Journal on Computing, 36 (2006), 815-834.
• "Efficient algorithms for bichromatic separability," with B. Aronov and V. Koltun, ACM Transacations on Algorithms, 2 (2006), 209-227.
• "An efficient algorithm for Euclidean 2-center with outliers," with J. Phillips, to appear in 16th European Symp. Algorithms, 2008.
• "Stabbing convex polygons with a segment or a polygon," with D. Chen, S. Gujgunte, E. Misiolek, M. Sharir, and K. Tang, to appear in 16th European Symp. Algorithms, 2008.

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, Comput. Geom.: Theory & Appls., 1 (1991), 65-78.
• "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.
• "Oriented aligned rectangle packing problem," with M. T. Shing, European J. Operations Research, 62 (1992), 210-220.
• "Relative neighborhood graphs in three dimensions," with J. Matousek, Comput. Geom.: Theory & 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 kth 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 Symp. Algorithms, 2002.
• "I/O-efficient construction of constrained Delaunay triangulations," with L. Arge and K. Yi, in 13th European Symp. Algorithms, 2005.
• "Lower bound for sparse Euclidean spanners," with Y. Wang and P.Yin, in 16th Annual ACM-SIAM Symp. Discrete Algorithms, 2005.
• "Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D," with R. Klein, C. Knauer, S. Langerman, P. Morin, M. Sharir, and M. Soss, in Discrete and Computational Geometry, 39 (2008), 17-37.
• "Computing a center-transversal line," with S. Cabello, J.A. Sellarès, and M. Sharir, to appear in Comput. Geom.: Theory & Appls.

Kinetic Algorithms

• "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 Annual Symp. Foundations Computer Science, 1998.
• "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.
• "Indexing moving points," with L. Arge and J. Erickson, in 19th ACM Symp. on Principles of Database Systems, 2000.
• "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.
• "Maintaining approximate extent measures of moving points," with S. Har-Peled, in 12th ACM-SIAM Symp. Discrete Algorithms,, 2001.
• "Maintaining the extent of a moving point set," with L. Guibas, J. Hershberger, and E. Veach, Discrete Comput. Geom., 26 (2001), 353-374.
• "Time responsive external data structures for moving points," with L. Arge and J. Vahrenhold, in 7th Workshop on Algorithms and Data Structures, 2001.
• "Deformable free space tilings for kinetic collision detection," with J. Basch, L. J. Guibas, J. Hershberger, and L. Zhang, Intl. J. Robotics Research, 21 (2002), 179-197.
• "Kinetic medians and kd-trees," with J. Gao and L. J. Guibas, in 10th European Symp. Algorithms, 2002
• "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.
• "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 ," with L. Arge, J. Erickson, and H. Yu, in 12th European Symp. Algorithms, 2004.
• "Staying in the middle: Exact and approximate medians in R¹ and R² for moving points," with M. de Berg, J. Gao, L. Guibas, and S. Har-Peled, in 18th Canadian Conf. Comput. Geom., 2005.
• "A 2D kinetic tiangulation with near-quadratic topological changes," with Y. Wang and H. Yu, Discrete Comput. Geom., 36 (2006), 573-592.
• "Out-of-order event processing in kinetic data structures," with M. A. Abam, M. de Berg, and H. Yu, in 14th European Symp. Algorithms, 2006.
• "Embeddings of surfaces, curves, and moving points in Euclidean space," with S. Har-Peled and H. Yu, in 23rd Annual Symp. Comput. Geom., 2007.
• "Untangling triangulations through local explorations," with B. Sadri and H. Yu, in 24th Annual Symp. Comput. Geom., 2008.
• "Kinetic and dynamic data structures for closest pairs and all nearest neighbors," with H. Kaplan and M. Sharir, to appear in ACM Transactions on Algorithms.
• "Out-of-order event processing in kinetic data structures," with M. A. Abam, M. de Berg, and H. Yu, to appear in Algorithmica.
• "Practical methods for shape fitting and kinetic data structures using coresets," with R. Poreddy, K. Varadarajan, and H. Yu, to appear in Algorithmica.
• "Embeddings of surfaces, curves, and moving points in Euclidean space," with S. Har-Peled and H. Yu, submitted to SIAM J. Comput.

Computational Molecular Biology

• "Collision detection for deforming necklaces," with L. J. Guibas, A. Nguyen, D. Russel, and L. Zhang, Comput. Geom.: Theory & Appls, 28 (2004), 137-163.
• "Computing the writhing number of a polygonal knot," with H. Edelsbrunner and Y.Wang, Discrete Comp. Geom., 32 (2004), 37-54.
• "Extreme elevation on a 2-manifold," with H. Edelsbrunner, J. Harer, and Y. Wang, in 20th Annual Symp. Comput. Geom., 2004.
• "Local search heuristic for rigid protein docking," with V. Choi, H. Edelsbrunner, and J. Rudolph, in Proc. 4th Workshop on Algorithms in Bioinformatics, 2004.
• "Coarse and reliable geometric alignment for protein docking," with Y.Wang, P. Brown, H. Edelsbrunner, and J. Rudolph, in Pacific Symp. Biocomput., 2005.
• "Near-linear time approximation algorithms for curve simplification," with S. Har-Peled, N. Mustafa, and Y. Wang, Algorithmica, 42 (2005), 203-219.
• "Faster algorithms for optimal multiple sequence alignment based on pairwise comparisons," with Y. Bilu and R. Kolodny, IEEE Trans. Bioinformatics, 3 (2006), 408-422.
• "Segmenting motifs in protein-protein interface surfaces," with J. Phillips and J. Rudolph, in 6th Workshop on Algorithms in Bioinformatics, 2006.
• "Fast molecular shape matching using contact maps," with N. Mustafa and Y.Wang. J. Comput. Biol., 14 (2007), 131-143.
• "Hausdorff distance under translation for points and balls," with S. Har-Peled, M. Sharir, and Y. Wang, to appear in ACM Transactions on Algorithms.

GIS and Terrain Modeling

• "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.
• "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.
• "An efficient algorithm for terrain simplification," with P. K. Desikan, in 8th ACM-SIAM Symp. Discrete Algorithms, 1997.
• "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.
• "Label placement by maximum independent set in rectangles," with M. van Kreveld and S. Suri, Comput. Geom.: Theory & Appls., 11 (1998), 209-218.
• "Efficient algorithms for approximating polygonal chains," with K. R. Varadarajan, Discrete Comput. Geom., 23 (2000), 273-291.
• "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.
• "Approximating shortest paths on a nonconvex polyhedron," with K. Varadarajan, SIAM J. Comput. 30 (2001), 1321-1340.
• "Computing approximate shortest paths on convex polytopes," with S. Har-Peled and M. Karia, Algorithmica, 33 (2002), 227-242.
• "Reporting 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: Theory & Appls., 23 (2002), 195-208.
• "I/O-efficient construction of constrained Delaunay triangulations," with L. Arge and K. Yi, in 13th European Symp. Algorithms, 2005.
• "Near-linear time approximation algorithms for curve simplification," with S. Har-Peled, N. Mustafa, and Y. Wang, Algorithmica, 42 (2005), 203-219.
• "From point cloud to grid DEM: A scalable approach," with A. Danner and L. Arge, in 12th Intl. Symp. Spatial Data Handling, 2006.
• "A scalable algorithm for dispersing population," with S. Govindrajan, M. Dietze, and J. Clark, Journal of Intelligent Information Systems, 29 (2007), 39-61.
• "TerraStream: From elevation data to watershed hierarchies," with A. Danner, K. Yi, T. Mølhave, L. Arge, H. Mitasova, in Proc. 15th ACM Symp. Advances in GIS, 2007.
• "I/O efficient algorithms for computing contour lines on a terrain" with L. Arge, T. Mølhave, and B. Sadri, in 24th Annual Symp. Comput. Geom., 2008.
• "Guarding a terrain by two watchtowers," with S. Bereg, O. Daescu, H. Kaplan, S. Ntafos, M. Sharir, and B. Zhu, to appear in Algorithmica.
• "I/O-efficient batched union-find and its applications to terrain analysis," with L. Arge and K. Yi, to appear in ACM Transactions on Algorithms.
• "Lipschitz unimodel and isotonic regression on paths and trees," with J. Phillips and B. Sadri, submitted to 20th ACM-SIAM Symp. Discrete Algorithms, 2009.

Ecological Modeling

• "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.
• "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 Symp. Comput. Geom., 2004.
• "A scalable algorithm for dispersing population," with S. Govindrajan, M. Dietze, and J. Clark, Journal of Intelligent Information Systems, 29 (2007), 39-61.
• "Resolving the biodiversity paradox," with J. Clark, M. Dietze, S. Chakraborty, I. Ibanez, S. LaDeau, and M. Wolosin, Ecology Letters, 10 (2007), 647-659.

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 Comput., 1995.
• "Efficient generation of k-directional assembly sequences," with M. de Berg, D. Halperin, and M. Sharir, in 7th ACM-SIAM Symp. Discrete Algorithms, 1996.
• "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.
• "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.
• "Star unfolding of a polytope with applications," with B. Aronov, J. O’Rourke, and C. Schevon, SIAM J. Comput., 26 (1997), 1689-1713.
• "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 Comput. Geom., 22 (1999), 201-221.
• "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.
• "Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions," with M. Sharir, Discrete Comput. Geom., 24 (2000), 645-685.
• "Approximation algorithms for curvature-constrained shortest paths," with H. Wang, SIAM J. Comput., 30 (2001), 1739-1772.
• "Minimal trap design," with A. D. Collins and J. Harer, in IEEE Conference on Robotics and Automation, 2001.
• "Curvature-constrained shortest paths in a convex polygon," with T. Biedl, S. Lazard, S. Robbins, S. Suri, and S. Whitesides, SIAM J. Comput., 31 (2002), 1814-1852.
• "Deformable free space tilings 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.
• "HPRM: A hierarchical PRM," with A. D. 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, Discrete Comput. Geom., 33 (2005), 463-481.

Geometric Data Structures

• "Intersection queries in sets of discs," with M. van Kreveld and M. Overmars, BIT 32 (1992), 268-279.
• "Ray shooting and other applications of spanning trees with low stabbing number," SIAM J. Comput. 22 (1992), 540-570.
• "Circle shooting in a simple polygon," with M. Sharir, J. Algorithms 14 (1993), 68-87.
• "Intersection queries in curved objects," with M. van Kreveld and M. Overmars, J. Algorithms 15 (1993), 229-266.
• "Ray shooting and parametric search," SIAM J. Comput. 22 (1993), 794-806.
• "On 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 amidst convex polygons in 2D," with M. Sharir, J. Algorithms, 21 (1996), 508-519.
• "Ray shooting among convex polytopes in 3D," with M. Sharir, SIAM J. Comput., 25 (1996), 100-116.
• "Parametric and kinetic minimum spanning trees," with D. Eppstein, L.J. Guibas, and M. Henzinger, in 39th Annual Symp. Foundations 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 Comput. Geom., 28 (2002), 291-312.
• "Kinetic medians and kd-trees," with J. Gao and L. J. Guibas, in 10th European Symp. Algorithms, 2002.
• "Range searching in categorical data: Colored range searching on grid," with S. Govindarajan and S. Muthukrishnan, in 10th European Symp. Algorithms, 2002.
• "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.
• "Bkd-tree: A dynamic scalable kd-tree," with O. Procopiuc, L. Arge, and J. S. Vitter, in 8th Annual Symp. Spatial Temporal Databases, 2003.
• "Cache-oblivious data structures for orthogonal range searching ," with L. Arge, A. Danner, and B. Holland-Minkley, in 19th Annual Symp. Comput. Geom., 2003.
• "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.
• "I/O-Efficient structures for orthogonal range max and stabbing max queries," with L. Arge, J. Yang, and K. Yi, in 11th 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.
• "Monitoring continuous band-join queries over dynamic data," with J. Xie, J. Yang, and H. Yu, in 26th Annual Intl. Symp. Algorithms and Computation, 2005.
• "An optimal dynamic interval stabbing-max data structure?" with L. Arge and K. Yi, to appear in 16th Annual ACM-SIAM Symp. Discrete Algorithms, 2005.
• "Scalable continuous query processing by tracking hotspots," with J. Xie, J. Yang, and H. Yu, in Annual IEEE Intl. Conf. Very Large Databases 2006.
• "ProSem: Scalable wide-area publish/subscribe," with B. Chandramouli, J. Yang, A. Yu, and Y. Zhang, in ACM SIGMOD Intl. Conf. Management Data, 2008.
• "I/O-efficient batched union-find and its applications to terrain analysis," with L. Arge and K. Yi, to appear in ACM Transactions on Algorithms.
• "Kinetic and dynamic data structures for closest pairs and all nearest neighbors," with H. Kaplan and M. Sharir, to appear in ACM Transactions on Algorithms.

Arrangements

• "Partitioning arrangements of lines: I. A deterministic algorithm," Discrete Comput. Geom., 5 (1990), 449-483.
• "Partitioning arrangements of lines: II. Applications," Discrete Comput. Geom., 5 (1990), 533-573.
• "Counting facets and incidences," with B. Aronov, Discrete Comput. Geom., 7 (1992), 359-369.
• "Applications of a new space partitioning technique," with M. Sharir, Discrete Comput. 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 lower envelopes and its applications," with O. Schwarzkopf and M. Sharir, Discrete Comput. 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.
• "Computing many faces in arrangements of lines and segments," with J. Matousek and O. Schwarzkopf, SIAM J. Comput., 27 (1998), 491-505.
• "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.
• "On levels in arrangements of lines, segments, planes, and triangles," with B. Aronov, T.M. Chan, and M. Sharir, Discrete Comput. Geom., 19 (1998), 315-331.
• "Line transversals of balls and smallest enclosing cylinders in three dimensions," with B. Aronov and M. Sharir, Discrete Comput. Geom. 21 (1999), 373-388.
• "Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions," with M. Sharir, Discrete Comput. Geom., 24 (2000), 645-685.
• "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 pseudo-segments and 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.
• "Pseudo-line arrangements: Duality, algorithms, and applications," with M. Sharir, SIAM J. Comput., 34 (2005), 526-552.
• Independent set of intersection graphs of convex objects in 2D," with N. H. Mustafa, Comput. Geom.: Theory & Appls., 34 (2006), 83-95.
• "Computing the volume of the union of cubes," with H. Kaplan and M. Sharir, in 23rd Annual Symp. Comput. Geom., 2007.
• "Algorithms for center and Tverberg points," with M. Sharir and E. Welzl, to appear in ACM Transacations on Algorithms.
• "Computing a center-transversal line," with S. Cabello, J.A. Sellarès, and M. Sharir, to appear in Comput. 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 Comput. 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 in three dimensions," with B. Aronov and S. Suri, in 11th Annual Symp. Comput. Geom., 1995.
• "The overlay of lower envelopes and its applications," with O. Schwarzkopf and M. Sharir, Discrete Comput. Geom., 15 (1996), 1-13.
• "On levels in arrangements of lines, segments, planes, and triangles," with B. Aronov and M. Sharir, in 13th Annual Symp. Comput. Geom., 1997.
• "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 the numbers of congruent simplices in a point set," with M. Sharir, Discrete Comput. Geom., 28 (2002), 123-150.
• "On the complexity of many faces in arrangements of pseudo-segments and 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, Discrete Comput. Geom., 34 (2005) 231-250.
• "Similar simplices in a d-dimensional point set," with R. Apfelbaum, G. Purdy, and M. Sharir, in 23rd Annual Symp. Comput. Geom., 2007.

Sensor Networks

• "Monitoring continuous band-join queries over dynamic data," with J. Xie, J. Yang, and H. Yu, in 26th Annual Intl. Symp. Algorithms and Computation, 2005.
• "Model-driven dynamic control of embedded wireless sensor networks," with P. Flikkema, J. Clark, C. Ellis, A. Gelfand, K. Munagala, and J. Yang, in 3rd International Conference on Computational Science, 2006.
• "Scalable continuous query processing by tracking hotspots," with J. Xie, J. Yang, and H. Yu, in Annual IEEE Intl. Conf. Very Large Databases 2006.
• "Segmenting object space by geometric reference structures," with D. Brady and J. Matousek, ACM Transactions on Sensor Networks, 2 (2006), 455-465.
• "From data reverence to data relevance: Model-mediated wireless sensing of the physical environment," with P. G. Flikkema, J. S. Clark, C. S. Ellis, A. Gelfand, K. Munagala, and J. Yang, in 4th International Conference on Computational Science, 2007.
• "Localization using boundary sensors: an analysis based on graph theory," with Y. Zheng and D. J. Brady, ACM Transactions on Sensor Networks 3 (2007).

Core Sets

• "Approximation algorithms for k-line center," with C. M. Procopiuc and K. R. Varadarajan, Algorithmica, 42 (2005), 221-230.
• "Embeddings of surfaces, curves, and moving points in Euclidean space," with S. Har-Peled and H. Yu, in 23rd Annual Symp. Comput. Geom., 2007.
• "A space-optimal data-stream algorithm for coresets in the plane," with H. Yu, in 23rd Annual Symp. Comput. Geom., 2007.
• "Robust shape fitting via peeling and grating coresets," with S. Har-Peled and H. Yu, Discrete Comput. Geom. 39 (2008), 38-58.
• "Practical methods for shape fitting and kinetic data structures using coresets," with R. Poreddy, K. Varadarajan, and H. Yu, to appear in Algorithmica.
• "Embeddings of surfaces, curves, and moving points in Euclidean space," with S. Har-Peled and H. Yu, submitted to SIAM J. Comput.
• "A space-optimal data-stream algorithm for coresets in the plane," with H. Yu, submitted to Discrete Comput. Geom.

Computer Graphics and Visualization

• "On the number of views of polyhedral terrains," with M. Sharir, Discrete 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.
• "An efficient algorithm for terrain simplification," with P. K. Desikan, in 8th ACM-SIAM Symp. Discrete Algorithms, 1997.
• "Practical techniques for constructing binary space partitions for orthogonal rectangles," with T.M. Murali and J.S. Vitter, in 13th Annual Symp. Comput. Geom., 1997.
• "Kinetic binary space partitions for intersecting segments and disjoint triangles," with J. Erickson and L. Guibas, in 9th ACM-SIAM Symp. Discrete Algorithms, 1998.
• "Surface approximation and geometric partitions," with S. Suri, SIAM J. Comput. 27 (1998), 1016-1035.
• "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.
• "Approximate Euclidean shortest paths amid convex obstacles," with R. Sharathkumar and H. Yu, submitted to 20th ACM-SIAM Symp. Discrete Algorithms, 2009.