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

- "Computing the discrete Fréchet distance in subquadratic time," with R. Ben Avraham, H. Kaplan, and M. Sharir, to appear in SIAM Journal on Computing.
- "Approximating dynamic time warping and edit distance of a pair of point sequences," with K. Fox, J. Pan, and R. Ying, in Proceedings Thirty-Second International Symposium on Computational Geometry, 2016, 6:1-6:16.
- "Computing the Gromov-Hausdorff distance for metric trees," with K. Fox, A. Nath, A. Sidiropoulos, and Y. Wang, in Proceedings Fortieth Annual International Symposium on Algorithms and Computation, 2015, 529-540.
- "Approximation algorithms for bipartite matching with metric and geometric costs," with R. Sharathkumar, in Proceedings Forty-Sixth Annual ACM Symposium on Theory of Computing, 2014, 555-564.
- "Model-driven matching and segmentation of trajectories," with S. Sankararaman, T. Mølhave, J. Pan, and A. P. Boedihardjo, in Proceedings Twenty-Second ACM Symposium on Advances in Geographic Information Systems, 2013, 234-243.
- "Algorithms for the transportation problem in geometric settings," with R. Sharathkumar, in Proceedings Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012.
- "A near-linear time ε-approximation algorithm for geometric bipartite matching," with R. Sharathkumar, in Proc. Forty-Fourth Ann. ACM Symp. Theory Computing, 2012.
- "An improved algorithm for computing the volume of the union of cubes," in 26th Annual Symp. Comput. Geom., 2010.
- "On polyhedra induced by point sets in space," with F. Hurtado, G. T. Toussaint, and J. Trias, Discrete Applied Mathematics, 156 (2008), 42-54.
- "Practical methods for shape fitting and kinetic data structures using coresets," with R. Poreddy, K. Varadarajan, and H. Yu, Algorithmica, 52 (2008), 378-402.
- "Robust shape fitting via peeling and grating coresets," with S. Har-Peled and H. Yu, Discrete Comput. Geom. 39 (2008), 38-58.
- "A space-optimal data-stream algorithm for coresets in the plane," with H. Yu, in 23rd Annual Symp. Comput. Geom., 2007.
- "Approximating extent measures of points," with S. Har-Peled and K.R. Varadarajan, J. ACM, 51 (2004), 606-635.
- "On bipartite matching under the rms distance," with J. Phillips, in 17th Canadian Conf. Comput. Geom., 2006.
- "Near-linear time approximation algorithms for curve simplification," with S. Har-Peled, N. Mustafa, and Y. Wang, Algorithmica, 42 (2005), 203-219
- "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.
- "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.
- "On the numbers of congruent simplices in a point set," with M. Sharir, Discrete Comput. Geom., 28 (2002), 123-150.
- "Exact and approximation algorithms for minimum-width cylindrical shells," with B. Aronov and M. Sharir, Discrete Comput. Geom., 26 (2001), 307-320.
- "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.
- "Approximation algorithms for bipartite and nonbipartite matchings in the plane," with K. R. Varadarajan, in 10th ACM-SIAM Symp. Discrete Algorithms, 1999.
- "Computing a segment-center for a planar point set," with A. Efrat, M. Sharir, and S. Toledo, J. Algorithms, 15 (1993), 314-323.

- "Markov-modulated marked Poisson processes for check-in data," with J. Pan, V. Rao, and A. Gelfand, in Proceedings Thirty-Third International Conference on Machine Learning, 2016.
- "Near-linear algorithms for geometric hitting sets and set covers," with J. Pan, in Proceedings Thirtieth Annual Symposium on Computational Geometry, 2014, 271-280.
- "The 2-center problem in three dimensions," with R. Ben Avraham and M. Sharir, Computational Geometry: Theory and Applications, 46 (2013), 734-746.
- "Near-linear approximation algorithms for geometric hitting sets," with E. Ezra and M. Sharir, Algorithmica, 63 (2012), 1-25.
- "An efficient algorithm for Euclidean 2-center with outliers," with J. Phillips, in 16th European Symp. Algorithms, 2008.
- "Stabbing convex polygons with a segment or a polygon," with D. Chen, S. Ganjugunte, E. Misiolek, M. Sharir, and K. Tang, in 16th European Symp. Algorithms, 2008.
- "Computing maximally separated sets in the plane," with M. Overmars and M. Sharir, in SIAM J. Comput., 36 (2006), 815-834.
- "Efficient algorithms for bichromatic separability," with B. Aronov and V. Koltun, ACM Transactions on Algorithms, 2 (2006), 209-227.
- "Approximation algorithms for k-line center," with C. M. Procopiuc and K. R. Varadarajan, Algorithmica, 42 (2005), 221-230.
- "k-means projective clustering," with N. H. Mustafa, in 23rd Annual Sympos. Principles of Database Systems, 2004.
- "A (1 + ε)-approximation algorithm for computing the two-line center," with C. M. Procopiuc and K. R. Varadarajan, Comput. Geom.: Theory and Appls., 26 (2003), 119-28.
- "Approximation algorithms for projective clustering," with C. M. Procopiuc, J. Algorithms, 46 (2003), 115-139.
- "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 Intl. Conf. Management Data, 2002.
- "Output-sensitive algorithms for uniform partitions of points," with B. Bhattacharya and S. Sen, Algorithmica, 32 (2002), 521-539.
- "The discrete 2-center problem," with M. Sharir and E. Welzl, Discrete Comput. Geom., 20 (1998), 287-306.
- "Linear approximation of convex objects," with K. Varadarajan, Inform. Process. Letts., 62 (1997), 89-94.
- "Extreme Elevation on a 2-Manifold,"with H. Edelsbrunner, J. Harer, and Y. Wang, Discrete Comput. Geom., 36 (2006), 553-572.
- "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.

- "Computing a center-transversal line," with S. Cabello, J.A. Sellarès, and M. Sharir, to appear in Intl. J. Comp. Geom. & Appls.
- "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 Comput. Geom., 39 (2008), 17-37.
- "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.
- "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.
- "Selection in monotone matrices and kth nearest neighbors," with S. Sen, J. Algorithms, 20 (1996), 581-601.
- "Selecting distances in the plane," with B. Aronov, M. Sharir, and S. Suri, Algorithmica, 9 (1993), 495-514.
- "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
- "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.
- "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.

- "Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions," with H. Kaplan, N. Rubin, and M. Sharir, Discrete and Computational Geometry, 54 (2015), 871-904.
- "Maintaining contour trees of dynamic terrains," with T. Mølhave, M. Revsbaek, I. Safa, Y.Wang, and J. Yang, in Proceedings Thirty-First International Symposium on Computational Geometry, 2015, 796-811.
- "Embeddings of surfaces, curves, and moving points in Euclidean space," with S. Har-Peled and H. Yu, SIAM J. Comput. 42 (2013), 442-458.
- "Kinetic stable Delaunay graphs," with J. Gao, L. Guibas, H. Kaplan, V. Koltun, N. Rubin, and M. Sharir, in 26th Annual Symp. Comput. Geom., 2010.
- "Kinetic and dynamic data structures for closest pairs and all nearest neighbors," with H. Kaplan and M. Sharir, in ACM Transactions on Algorithms 5, 1 (2008), Article 4, (37 pp.).
- "On approximate geodesic-distance queries amid deforming point clouds," with A. Efrat, R. Sharathkumar, and H. Yu, in 8th Workshop on Algorithmic Foundations of Robotics, 2008.
- "Practical methods for shape fitting and kinetic data structures using coresets," with R. Poreddy, K. Varadarajan, and H. Yu, Algorithmica, 52 (2008), 378-402.
- "Untangling triangulations through local explorations," with B. Sadri and H. Yu, in 24th Annual Symp. Comput. Geom., 2008.
- "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 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.
- "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.
- "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.
- "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.
- "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.
- "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.
- "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.
- "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.

- "On range searching with semialgebraic sets II," with J. Matoušek and M. Sharir, SIAM Journal on Computing, in press.
- "Top-k preferences in high dimensions," with A. Yu and J. Yang, to appear in Proc. Twenty-Ninth IEEE Intl. Conf. Data Engineering, 2013.
- "Parallel algorithms for constructing range and nearest-neighbor searching data structures," with K. Fox, K. Munagala, and A. Nath, in Proceedings Thity-Fifth Annual Symposium on Principles of Database Systems, 2016, 429-440.
- "Range-max queries on uncertain data," with N. Kumar, S. Sintos, and S. Suri, in Proceedings Thity-Fifth Annual Symposium on Principles of Database Systems, 2016, 465-476.
- "Efficient external memory structures for range-aggregate queries," with L. Arge, S. Govindrajan, J. Yang, and K. Yi, Computational Geometry: Theory and Applications, 46 (2013), 358-370.
- "Nearest-neighbor searching under uncertainty II," with B. Aronov, S. Har-Peled, J. Phillips, K. Yi, and W. Zhang, in Proc. Thirty-Second Ann. Symp. Principles of Database Systems, 2013.
- "Nearest-neighbor searching under uncertainty," with A. Efrat, S. Sankararaman, and W. Zhang, in Proc. Thirty-First Ann. Symp. Principles Database Systems, 2012.
- "An optimal dynamic data structure for stabbing-semigroup queries," with L. Arge, H. Kaplan, E. Molad, R. E. Tarjan, K. Yi, SIAM Journal on Computing, 41 (2012), 104-127.
- "Range searching on uncertain data," with S.-W. Cheng, Y. Tao, and K. Yi, ACM Transactions on Algorithms, 8 (2012), Article 43.
- "I/O-efficient contour queries on terrains," with T. Mølhave and B. Sadri, in Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011.
- "I/O-efficient batched union-find and its applications to terrain analysis," with L. Arge and K. Yi, ACM Transactions on Algorithms, 7, 1 (2010), Article 11, (21pp.).
- "Kinetic and dynamic data structures for closest pairs and all nearest neighbors," with H. Kaplan and M. Sharir, in ACM Transactions on Algorithms 5, 1 (2008), Article 4, (37 pp.).
- "ProSem: Scalable wide-area publish/subscribe," with B. Chandramouli, J. Yang, A. Yu, and Y. Zhang, in ACM SIGMOD Intl. Conf. Management Data, 2008.
- "Scalable continuous query processing by tracking hotspots," with J. Xie, J. Yang, and H. Yu, in Annual IEEE Intl. Conf. Very Large Databases 2006.
- "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.
- "Collision detection for deforming necklaces," with L. J. Guibas, A. Nguyen, D. Russel, and L. Zhang, Comput. Geom.: Theory & Appls, 28 (2004), 137-163.
- "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. 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.
- "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.
- "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.
- "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.
- "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.
- "Parametric and kinetic minimum spanning trees," with D. Eppstein, L.J. Guibas, and M. Henzinger, in 39th Annual Symp. Foundations Computer Science, 1998.
- "Polygon and connected component intersection searching," with M. van Kreveld, Algorithmica, 15 (1996), 626-660.
- "Ray shooting amidst convex polyhedra and polyhedral terrains in three dimensions," 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.
- "Dynamic half-space range reporting and its applications," with J. Matousek, Algorithmica, 13 (1995), 325-345.
- "On range searching with semialgebraic sets," with J. Matousek, Discrete Comput. Geom., 11 (1994), 393-418.
- "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.
- "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. 21 (1992), 540-570.

- "Mergeable summaries," (invited) with G. Cormode, Z. Huang, J. M. Phillips, Z. Wei, and K. Yi, to appear in ACM Transactions on Database Systems.
- "Embeddings of surfaces, curves, and moving points in Euclidean space," with S. Har-Peled and H. Yu, SIAM J. Comput. 42 (2013), 442-458.
- "Processing a large number of continuous preference top-k Queries," with A. Yu and J. Yang, in Proc ACM SIGMOD Intl Conf. Management of Data, 2012.
- "Subscriber assignment for wide-area content-based publish/subscribe," with A. Yu and J. Yang, in International Conference on Data Engineering, 2011.
- "Stability of "ε-kernels," with J. Phillips and H. Yu, in Eighteenth European Symposium on Algorithms, 2010.
- "Streaming algorithms for extent problems in high dimensions," with R. Sharathkumar, in Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010.
- "Practical methods for shape fitting and kinetic data structures using coresets," with R. Poreddy, K. Varadarajan, and H. Yu, Algorithmica, 52 (2008), 378-402.
- "Robust shape fitting via peeling and grating coresets," with S. Har-Peled and H. Yu, Discrete Comput. Geom. 39 (2008), 38-58.
- "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.
- "Approximation algorithms for k-line center," with C. M. Procopiuc and K. R. Varadarajan, Algorithmica, 42 (2005), 221-230.

- "Computing a center-transversal line," with S. Cabello, J.A. Sellarès, and M. Sharir, to appear in Intl. J. Comp. Geom. & Appls.
- "Algorithms for center and Tverberg points," with M. Sharir and E. Welzl, ACM Transactions on Algorithms, 5, 1 (2008), Article 5, (20 pp.).
- "Computing the volume of the union of cubes," with H. Kaplan and M. Sharir, in 23rd Annual Symp. Comput. Geom., 2007.
- Independent set of intersection graphs of convex objects in 2D," with N. H. Mustafa, Comput. Geom.: Theory & Appls., 34 (2006), 83-95.
- "Pseudo-line arrangements: Duality, algorithms, and applications," with M. Sharir, SIAM J. Comput., 34 (2005), 526-552.
- "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 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.
- "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.
- "Line transversals of balls and smallest enclosing cylinders in three dimensions," with B. Aronov and M. Sharir, Discrete Comput. Geom. 21 (1999), 373-388.
- "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.
- "Computing envelopes in four dimensions with applications," with B. Aronov and M. Sharir, SIAM J. Comput., 26 (1997), 1714-1732.
- "The overlay of lower envelopes and its applications," with O. Schwarzkopf and M. Sharir, Discrete Comput. Geom., 15 (1996), 1-13.
- "Implicit point location in arrangement segments with application to motion planning," with M. van Kreveld, Intl. J. Comput. Geom. & Appls., 4 (1994), 369-383.
- "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.
- "Counting facets and incidences," with B. Aronov, Discrete Comp. Geom., 7 (1992), 359-369.
- "Partitioning arrangements of lines: I. An efficient deterministic algorithm," Discrete Comput. Geom., 5 (1990), 449-483.
- "Partitioning arrangements of lines: II. Applications," Discrete Comput. Geom., 5 (1990), 533-573.

- "Contour trees of uncertain terrains," withW. Zhang and S. Mukherjee, in Proceedings Twenty-Fourth ACM Symposium on Advances in Geographic Information Systems, 2015, 43:1-43:10.
- "Maintaining contour trees of dynamic terrains," with T. Mølhave, M. Revsbaek, I. Safa, Y.Wang, and J. Yang, in Proceedings Thirty-First International Symposium on Computational Geometry, 2015, 796-811.
- "Computing highly occluded paths using a sparse network," with N. Lebeck and T. Mølhave, in Proceedings Twenty-Third ACM Symposium on Advances in Geographic Information Systems, 2014, 1-10.
- "Computing highly occluded paths on a terrain," with N. Lebeck and T. Mølhave, in Proceedings Twenty-Second ACM Symposium on Advances in Geographic Information Systems 2013, 14-23.
- "Computing similarity of piecewise-linear functions," with B. Aronov, M. van Kreveld, M. Löffler, and R. I. Silveira, SIAM Journal on Computing, 42 (2013), 1867-1887.
- "Model-driven matching and segmentation of trajectories," with S. Sankararaman, T. Mølhave, J. Pan, and A. P. Boedihardjo, in Proceedings Twenty-Second ACM Symposium on Advances in Geographic Information Systems, 2013, 234-243.
- "I/O-efficient contour queries on terrains," with T. Mølhave and B. Sadri, in Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011.
- "TerraNNI: Natural neighbor interpolation on a 3D grid using a GPU," with A. Beutel, T. Mølhave, A. P. Boedihardjo, and J. A. Shine, in Proc. Twentieth ACM Symp. Advances in Geographic Information Systems, 2011. (Also appeared in Third Workshop on Massive Data Algorithmics, 2011.)
- "Computing similarity between piecewise-linear functions," with B. Aronov, M. van Kreveld, M. Löffler, and R. I. Silveira, in 26th Annual Symp. Comput. Geom., 2010.
- "Guarding a terrain by two watchtowers," with S. Bereg, O. Daescu, H. Kaplan, S. Ntafos, M. Sharir, and B. Zhu, Algorithmica, 58 (2010), 352-390.
- "I/O-efficient batched union-find and its applications to terrain analysis," with L. Arge and K. Yi, ACM Transactions on Algorithms, 7, 1 (2010), Article 11, (21pp.).
- "Lipschitz unimodel and isotonic regression on paths and trees," with J. Phillips and B. Sadri, in Ninth Annual Latin American Theoretical Informatics Symposium, 2010.
- "Natural neighbor interpolation based grid DEM construction using a GPU," with A. Beutel and T. Mølhave, in Nineteenth ACM Symposium on Advances in Geographic Information Systems (best paper), 2010.
- "Scalable algorithms for large high-resolution terrain data," with T. Mølhave, L. Arge, and M. Revsbæk, in First International Conference on Computing for Geospatial Research and Applications, 2010.
- "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.
- "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.
- "From point cloud to grid DEM: A scalable approach," with A. Danner and L. Arge, in 12th Intl. Symp. Spatial Data Handling, 2006.
- "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
- "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.
- "Approximating shortest paths on a nonconvex polyhedron," with K. Varadarajan, SIAM J. Comput. 30 (2001), 1321-1340.
- "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.
- "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.
- "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.
- "Polygon and connected component intersection searching," with M. van Kreveld, Algorithmica, 15 (1996), 626-660.
- "KBGIS-II: A knowledge-based geographic information system," with T. Smith, D. Peuquet, and S. Menon, Intl. J. GIS, 1 (1987), 149-172.

- "Top-k preferences in high dimensions," with A. Yu and J. Yang, to appear in Proc. Twenty-Ninth IEEE Intl. Conf. Data Engineering, 2013.
- "Parallel algorithms for constructing range and nearest-neighbor searching data structures," with K. Fox, K. Munagala, and A. Nath, in Proceedings Thity-Fifth Annual Symposium on Principles of Database Systems, 2016, 429-440.
- "Range-max queries on uncertain data," with N. Kumar, S. Sintos, and S. Suri, in Proceedings Thity-Fifth Annual Symposium on Principles of Database Systems, 2016, 465-476.
- "Toward computational fact checking," with Y. Wu, C. Li, J. Yang, and C. Yu, in Proceedings Fortieth Annual IEEE International Conference on Very Large Databases, 2014, 589-600.
- "Nearest-neighbor searching under uncertainty II," with B. Aronov, S. Har-Peled, J. Phillips, K. Yi, and W. Zhang, in Proc. Thirty-Second Ann. Symp. Principles of Database Systems, 2013.
- "Nearest-neighbor searching under uncertainty," with A. Efrat, S. Sankararaman, and W. Zhang, in Proc. Thirty-First Ann. Symp. Principles Database Systems, 2012.
- "On "one of the few" objects," with Y. Wu, C. Li, J. Yang, and C. Yu, in Proc. Eighteenth ACM Intl. Conf. Knowledge Discovery and Data Mining, 2012.
- "Processing a large number of continuous preference top-k Queries," with A. Yu and J. Yang, in Proc ACM SIGMOD Intl Conf. Management of Data, 2012.
- "Processing a large number of continuous preference top-k Queries," with A. Yu and J. Yang, in Proc ACM SIGMOD Intl Conf. Management of Data, 2012.
- "Processing and notifying range top-k subscriptions," with A. Yu, and J. Yang, in Proc. Twenty-Eighth IEEE Intl. Conf. Data Engineering, 2012.
- "Processing and notifying range top-k subscriptions," with A. Yu, and J. Yang, in Proc. Twenty-Eighth IEEE Intl. Conf. Data Engineering, 2012.
- "(Approximate) uncertain skylines," with P. Afshani, L. Arge, K. D. Larsen, and J. M. Phillips, in 14th Intl. Conf. Database Theory, 2011.
- "Subscriber assignment for wide-area content-based publish/subscribe," with A. Yu and J. Yang, in International Conference on Data Engineering, 2011.
- "Generating wide-area content-based publish/subscribe workloads," with A. Yu and J. Yang, in 5th International Workshop on Networking Meets Databases, 2009.
- "Indexing uncertain data," with S.-W. Cheng, Y. Tao, and K. Yi, in Twenty Eighth Annual Symposium on Principles of Database Systems, 2009.
- "Input-sensitive scalable continuous join query processing," with J. Xi, J. Yang, and H. Yu, ACM Transactions on Database Systems 34, 3 (2009), Article 13, (41 pp.).
- "ProSem: Scalable wide-area publish/subscribe," with B. Chandramouli, J. Yang, A. Yu, and Y. Zhang, in ACM SIGMOD Intl. Conf. Management Data, 2008.
- "Scalable continuous query processing by tracking hotspots," with J. Xie, J. Yang, and H. Yu, in Annual IEEE Intl. Conf. Very Large Databases 2006.
- "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.
- "Bkd-tree: A dynamic scalable kd-tree," with O. Procopiuc, L. Arge, and J. S. Vitter, in 8th Annual Symp. Spatial Temporal Databases, 2003.
- "CRB-tree: An efficient indexing scheme for range aggregate queries," with S. Govindarajan and L. Arge, in 9th Intl. Conf. Database Theory, 2003.
- "Indexing moving points," with L. Arge and J. Erickson, Journal of Computer and Systems Sciences, 66 (2003), 207-243.
- "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.
- "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.

- "Exploiting temporal coherence in forest dynamics simulation," with T. Mølhave, H. Yu, and J. Clark, in 27th Annual Symp. Comput. Geom., 2011.
- "Inferential ecosystem models, from network data to prediction," with J. S. Clark, D. M. Bell, P. Flikkema, A. Gelfand, X. Nguyen, E. Ward, and J. Yang, Ecological Applications, 21 (2011), 1523-1536.
- "Resolving the biodiversity paradox," with J. Clark, M. Dietze, S. Chakraborty, I. Ibanez, S. LaDeau, and M. Wolosin, Ecology Letters, 10 (2007),
- "A scalable algorithm for dispersing population," with S. Govindrajan, M. Dietze, and J. Clark, Journal of Intelligent Information Systems, 29 (2007), 39-61.
- "A scalable simulator for forest dynamics," with S. Govindrajan, M. Dietze, and J. Clark, in 20th Annual Symp. Comput. Geom., 2004.
- "The paradox of species diversity," with J. Clark, M. Dietze, and S. Govindarajan, in Ecological Society of America Annual Meeting, 2003.
- "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.

- "An efficient algorithm for computing high quality paths amid polygonal obstacles," with K. Fox and O. Salzmann, in Proceedings Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2016, 1179-1192.
- "Sparsification of motion-planning roadmaps by edge contraction," with D. Shaharabani, O. Salzman, and D. Halperin, in Proceedings IEEE International Conference on Robotics and Automation, 2013.
- "Approximate Euclidean shortest paths amid convex obstacles," with R. Sharathkumar and H. Yu, in 20th ACM-SIAM Symp. Discrete Algorithms, 2009.
- "On approximate geodesic-distance queries amid deforming point clouds," with A. Efrat, R. Sharathkumar, and H. Yu, in 8th Workshop on Algorithmic Foundations of Robotics, 2008.
- "A near-quadratic algorithm for fence design," with R.-P. Berretty and A. D. Collins, Discrete Comput. Geom., 33 (2005), 463-481.
- "HPRM: A hierarchical PRM," with A. D. Collins and J. Harer in Proc. Intl Conf. Robotics and Automation , 2003.
- "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 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.
- "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.
- "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.
- "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.
- "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.
- "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.
- "Motion planning for a steering-constrained robot through moderate obstacles," with P. Raghavan and H. Tamaki, in 27th ACM Symp. Theory Comput., 1995.
- "Red-blue intersection detection algorithms, with applications to motion planning and collision detection," with M. Sharir, SIAM J. Comput., 19 (1990), 297-322.

- "Union of random Minkowski sums and network vulnerability analysis," with H. Kaplan and M. Sharir, in Proc. Twenty-Ninth Ann. Symp. Computational Geometry, 2013.
- "Similar simplices in a d-dimensional point set," with R. Apfelbaum, G. Purdy, and M. Sharir, in 23rd Annual Symp. Comput. Geom., 2007.
- "On lines avoiding unit balls in three dimensions," with B. Aronov, V. Koltun, and M. Sharir, Discrete Comput. Geom., 34 (2005) 231-250.
- "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 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.
- "On the numbers of congruent simplices in a point set," with M. Sharir, Discrete Comput. Geom., 28 (2002), 123-150.
- "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.
- "Handbook of Computational Geometry (J. Sack and J. Urrutia, eds.), North-Holland, New York, 2000, pp 1-47.
- "Line stabbing bounds in three dimensions," with B. Aronov and S. Suri, in 11th Annual Symp. Comput. Geom., 1995.
- "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.
- "Counting facets and incidences," with B. Aronov, Discrete Comp. Geom., 7 (1992), 359-369.
- "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.

- "On channel-discontinuity-constraint routing in wireless networks" with S. Sankararaman, A. Efrat, and S. Ramasubramanian, to appear in Ad-Hoc Networks.
- "Distributed localization and clustering using data correlation and the Occams razor principle," with A. Efrat, C. Gniady, J.S.B. Mitchell, G. R. Sabhnani, and V. Plishchuk, to appear in 7th IEEE Intl. Conf. Distributed Comput. Sensor Systems, 2011.
- "The resilience of WDM networks to probabilistic geographical failures," with A. Efrat, S. Ganjugunte, D. Hay, S. Sankararaman, G. Zussman, in Thiryth International Conference on Computer Communications, 2011.
- "Network vulnerability to single, multiple, and probabilistic physical attacks," with A. Efrat, S. K. Ganjugunte, D. Hay, S. Sankararaman, G. Zussman, Military Communications Conference, 2010.
- "Efficient sensor placement for surveillance problems," with E. Ezra and S. Ganjugunte, in 5th IEEE Intl. Conf. Distributed Comput. Sensor Systems (best paper), 2009.
- "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 Intl. Conf. Comput. Science, 2006.
- "Localization using boundary sensors: an analysis based on graph theory," with Y. Zheng and D. J. Brady, in ACM Transactions on Sensor Networks 3 (2007).
- "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.
- "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.

- "Hausdorff distance under translation for points and balls," with S. Har-Peled, M. Sharir, and Y. Wang, ACM Transactions on Algorithms, 6 (2010), 1-26.
- "Fast molecular shape matching using contact maps," with N. Mustafa and Y. Wang. J. Comput. Biol., 14 (2007), 131-143.
- "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.
- "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
- "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, Discrete Comput. Geom., 36 (2006), 553-572.
- "Local search heuristic for rigid protein docking," with V. Choi, H. Edelsbrunner, and J. Rudolph, in Proc. 4th Workshop on Algorithms in Bioinformatics, 2004.

- "Computing similarity of piecewise-linear functions," with B. Aronov, M. van Kreveld, M. Löffler, and R. I. Silveira, SIAM Journal on Computing, 42 (2013), 1867-1887.
- "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.
- "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.
- "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.
- "Simplification envelopes," with J. Cohen, A. Varshney, D. Manocha, G. Turk, F. Brooks, H. Weber, and W. Wright, in SIGGRAPH, 1996.
- "Computing depth orders and related problems," with M. Katz and M. Sharir, Comput. Geom: Theory & Appls., 5 (1995), 187-206.
- "On the number of views of polyhedral terrains," with M. Sharir, Discrete Comput. Geom., 12 (1994), 177-182.

- "Convex hull under uncertainty," with S. Har-Peled, S. Suri, H. Tildiz, and W. Zhang, to appear in Algorithmica.
- "Range-max queries on uncertain data," with N. Kumar, S. Sintos, and S. Suri, in Proceedings Thity-Fifth Annual Symposium on Principles of Database Systems, 2016, 465-476.
- "Contour trees of uncertain terrains," withW. Zhang and S. Mukherjee, in Proceedings Twenty-Fourth ACM Symposium on Advances in Geographic Information Systems, 2015, 43:1-43:10.