Publications: Papers by Subject

See also:  Papers by Year | Books | Surveys

Shape Analysis

• "Geometric partial matchings and unbalanced transportation problem," with H.-C. Chang and A. Xiao, in Proceedings Thirty-Fifth International Symposium on Computational Geometry, 2019.
• "Approximate minimum-weight matching with outliers under translation," with H. Kaplan, G. Kipper, W. Mulzer, G. Rote, M. Sharir, and A. Xiao, in Proceedings Forty-Third Annual International Symposium on Algorithms and Computation, 2018, 26:1-26:13.
• "Faster algorithms for the geometric transportation problem," with K. Fox, D. Panigrahi, K. R. Varadarajan, and A. Xiao, in Proceedings Thirty-Third International Symposium on Computational Geometry, 2017, 7:1-7:16
• "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.
• "A simple efficient algorithm for dynamic time warping of two curves," with R. Ying, J. Pan, and K. Fox, in Proceedings Twenty-Fifth ACM Symposium on Advances in Geographic Information Systems, 2016, 25:1-25:10.
• "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.
• "Computing the discrete Fréchet distance in subquadratic time," with R. Ben Avraham, H. Kaplan, and M. Sharir, in Proceedings Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013, 155-167.
• "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 Proceedings Forty-Fourth Annual ACM Symposium on Theory of Computing, 2012.
• The 2-center problem in three dimensions," with R. Ben Avraham and M. Sharir, in Proceedings Twenty-Sixth Annual Symposium on Computational Geometry, 2010.
• "An improved algorithm for computing the volume of the union of cubes," in Proceedings Twenty-Sixth Annual Symposium on Computational Geometry, 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 & Computational Geometry 39 (2008), 38-58.
• "A space-optimal data-stream algorithm for coresets in the plane," with H. Yu, in Proceedings Twenty-Third Annual Symposium on Computational Geometry, 2007.
• "Approximating extent measures of points," with S. Har-Peled and K.R. Varadarajan, Journal of the ACM, 51 (2004), 606-635.
• "On bipartite matching under the rms distance," with J. Phillips, in Seventeenth Canadian Conference on Computational Geometry, 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, Journal of the ACM, 51 (2004), 606-635.
• "Computing the writhing number of a polygonal knot," with H. Edelsbrunner and Y. Wang, Discrete & Computational Geometry, 32 (2004), 37-54.
• "A near-linear constant-factor approximation for Euclidean bipartite matching?, with K. R. Varadarajan, in Proceedings Twentieth Annual Symposium on Computational Geometry, 2004.
• "Hausdorff distance under translation for points, and balls," with S. Har-Peled, M. Sharir, and Y. Wang, in Proceedings Nineteenth Annual Symposium on Computational Geometry, 2003.
• "Streaming geometric optimization using graphics hardware," with S. Krishnan, N. H. Mustafa, and S. Venkatasubramanian, in Proceedings Eleventh Annual European Symposium on Algorithms, 2003.
• "On the numbers of congruent simplices in a point set," with M. Sharir, Discrete & Computational Geometry, 28 (2002), 123-150.
• "Exact and approximation algorithms for minimum-width cylindrical shells," with B. Aronov and M. Sharir, Discrete & Computational Geometry, 26 (2001), 307-320.
• "Approximation algorithms for layered manufacturing," with P. K. Desikan, in Proceedings Eleventh ACM-SIAM Symposium on Discrete Algorithms, 2000.
• "Approximation and exact algorithms for minimum-width annuli and shells," with B. Aronov, S. Har-Peled and M. Sharir, Discrete & Computational Geometry, 24 (2000), 687-705.
• "Approximation algorithms for bipartite and nonbipartite matchings in the plane," with K. R. Varadarajan, in Proceedings Tenth ACM-SIAM Symposium on Discrete Algorithms, 1999.
• "Efficient randomized algorithms for some geometric optimization problems," with M. Sharir, Discrete & Computational Geometry, 16 (1996), 317-337
• "Computing a segment center for a planar point set," with A. Efrat, M. Sharir, and S. Toledo, Journal of Algorithms, 15 (1993), 314-323.

Clustering and Classification

• "Subtrajectory clustering: models and algorithms," with K. Fox, K. Munagala, A. Nath, and J. Pan, in Proceedings Thirty-Seventh Annual Symposium on Principles of Database Systems, 2018, 75-87.
• "An efficient algorithm for placing electric vehicle charging stations," with J. Pan and W. Victor, in Proceedings Forty-First Annual International Symposium on Algorithms and Computation, 2016, 7:1-7:12
• "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.
• The 2-center problem in three dimensions," with R. Ben Avraham and M. Sharir, in Proceedings Twenty-Sixth Annual Symposium on Computational Geometry, 2010.
• "An efficient algorithm for Euclidean 2-center with outliers," with J. Phillips, in Sixteenth European Symposium on Algorithms, 2008.
• "Stabbing convex polygons with a segment or a polygon," with D. Chen, S. Ganjugunte, E. Misiolek, M. Sharir, and K. Tang, in Proceedings Sixteenth European Symposium on Algorithms, 2008.
• "Computing maximally separated sets in the plane," with M. Overmars and M. Sharir, in SIAM Journal on Computing," 36 (2006), 815-834.
• "Efficient algorithms for bichromatic separability," with B. Aronov and V. Koltun, ACM Transactions on Algorithms, 2 (2006), 209-227.
• "Extreme Elevation on a 2-Manifold,"with H. Edelsbrunner, J. Harer, and Y. Wang, Discrete & Computational Geometry, 36 (2006), 553-572.
• "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 Proceedings Twenty-Third Annual Symposium on Principles of Database Systems, 2004.
• "A (1 + ε)-approximation algorithm for 2-line center," with C. M. Procopiuc and K. R. Varadarajan, Computational Geometry: Theory and Applications., 26 (2003), 119-28.
• "Approximation algorithms for projective clustering," with C. M. Procopiuc, Journal of 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 Proceedings ACM SIGMOD International Conference on Management of 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 & Computational Geometry, 20 (1998), 287-306.
• "Linear approximation of simple objects," with K. Varadarajan, Information Processing Letters, 62 (1997), 89-94.
• "Applications of parametric searching in geometric optimization," with M. Sharir and S. Toledo, Journal of Algorithms, 17 (1994), 292-318.
• "Planar geometric location problems," with M. Sharir, Algorithmica, 11 (1994), 185-195.

Proximity

• "Improved dynamic geodesic nearest neighbor searching in a simple polygon," with L. Arge and F. Staals, in Proceedings Thirty-Fourth International Symposium on Computational Geometry, 2018, 4:1-4:14.
• "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 & Computational Geometry, 39 (2008), 17-37.
• "I/O-efficient construction of constrained Delaunay triangulations," with L. Arge and K. Yi, in Thirteenth European Symposium on Algorithms, 2005.
• "Lower bound for sparse Euclidean spanners," with Y. Wang and P. Yin, in Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005.
• "Translating a planar object to maximize point containment," with T. Hagerup, R. Ray, M. Sharir, M. Smid, and E. Welzl, in Tenth Annual European Symposium on Algorithms, 2002.
• "Selection in monotone matrices and computing kth nearest neighbors," with S. Sen, Journal of 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, Computational Geometry: Theory & Applications, 1 (1992), 189-201.
• "Oriented aligned rectangle packing problem," with M. T. Shing, European Journal of Operational Research, 62 (1992), 210-220.
• "Relative neighborhood graphs in three dimensions," with J. Matousek, Computational Geometry: Theory & Applications., 2 (1992), 1-15.
• "Computing external farthest neighbors for a simple polygon," with A. Aggarwal, B. Aronov, S. Kosaraju, B. Shieber, and S. Suri, Discrete Applied Mathematics, 31 (1991), 97-111.
• "Euclidean minimum spanning tree and bichromatic closest pairs," with H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, Discrete & Computational Geometry 6 (1991), 407-422.
• "Off-line dynamic maintenance of the width of a planar point set," with M. Sharir, Computational Geometry: Theory & Applications, 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.

Geometric Data Structures

• "An efficient algorithm for generalized polynomial partitioning and its applications," with B. Aronov, E. Ezra, and J. Zahl, in Proceedings Thirty-Fifth International Symposium on Computational Geometry, 2019.
• "Maintaining the union of unit discs under insertions with near-optimal overhead," with R. Cohen, D. Halperin, and W. Mulzer, in Proceedings Thirty-Fifth International Symposium on Computational Geometry, 2019.
• "Approximate nearest neighbor search amid higher-dimensional flats," with N. Rubin and M. Sharir, in Proceedings Twenty-Fifth European Symposium on Algorithms, 2017, 4:1-4:13.
• "Nearest-neighbor searching under uncertainty I," with A. Efrat, S. Sankararaman, and W. Zhang, Discrete and Computational Geometry, 58 (2017), 705-745.
• "Nearest-neighbor searching under uncertainty II," with B. Aronov, S. Har-Peled, J. Phillips, K. Yi, and W. Zhang, ACM Transactions on Algorithms, 13 (2016), 3:1-3:25.
• "Parallel algorithms for constructing range and nearest-neighbor searching data structures," with K. Fox, K. Munagala, and A. Nath, in Proceedings Thirty-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 Thirty-Fifth Annual Symposium on Principles of Database Systems, 2016, 465-476.
• "Top-k preferences in high dimensions," with A. Yu and J. Yang IEEE Transactions on Knowledge and Data Engineering, 28 (2016), 311-325.
• "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.
• "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.
• "On range searching with semialgebraic sets II," with J. Matoušek and M. Sharir, in SIAM Journal on Computing, 42 (2013), 2039-2062.
• "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 International Conference on Management of Data, 2008.
• "Scalable continuous query processing by tracking hotspots," with J. Xie, J. Yang, and H. Yu, in Annual IEEE International Conference on Very Large Databases 2006.
• "Monitoring continuous band-join queries over dynamic data," with J. Xie, J. Yang, and H. Yu, in Twenty-Sixth Annual International Symposium on Algorithms and Computation, 2005.
• "An optimal dynamic interval stabbing-max data structure?", with L. Arge and K. Yi, in Proceedings Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, 803-812.
• "Collision detection for deforming necklaces," with L. J. Guibas, A. Nguyen, D. Russel, and L. Zhang, Computational Geometry: Theory & Applications, 28 (2004), 137-163.
• "Bkd-tree: A dynamic scalable kd-tree," with O. Procopiuc, L. Arge, and J. S. Vitter, in Eighth Annual Symposium on Spatial & Temporal Databases, 2003.
• "Cache-oblivious data structures for orthogonal range searching ," with L. Arge, A. Danner, and B. Holland-Minkley, in Nineteenth Annual Symposium on Computational Geometry, 2003.
• "CRB-tree: An efficient indexing scheme for range aggregate queries," with S. Govindarajan and L. Arge, in Ninth International Conference 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 Eleventh European Symposium on 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 & Computational Geometry, 28 (2002), 291-312.
• "Kinetic medians and kd-trees," with J. Gao and L. J. Guibas, in Tenth European Symposium on Algorithms, 2002.
• "Range searching in categorical data: Colored range searching on grid," with S. Govindarajan and S. Muthukrishnan, in Tenth European Symposium on Algorithms, 2002.
• "STAR-tree: An efficent self-adjusting index for moving points," with C. M. Procopiuc and S. Har-Peled, in Fourth 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 Twenty-Eighth Internatioanl Conference on Automata, Languages, and Programming, 2001.
• "Efficient searching with linear constraints," with L. Arge, J. Erickson, P. G. Franciosa, and J. S. Vitter, Journal of 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 Tenth ACM-SIAM Symposium on Discrete Algorithms, 1999.
• "Parametric and kinetic minimum spanning trees," with D. Eppstein, L.J. Guibas, and M. Henzinger, in Thirty-Ninth Annual Symposium on Foundations of Computer Science, 1998.
• "Connected component and simple polygon intersection searching," with M. van Kreveld, Algorithmica, 15 (1996), 626-660.
• "Ray shooting amidst convex polygons in 2D," with M. Sharir, Journal of Algorithms, 21 (1996), 508-519.
• "Ray shooting amidst convex polyhedra and polyhedral terrains in three dimensions," with M. Sharir, SIAM Journal of Computing, 25 (1996), 100-116.
• "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 & Computational Geometry, 11 (1994), 393-418.
• "Circle shooting in a simple polygon," with M. Sharir, Journal of Algorithms 14 (1993), 68-87.
• "Circular visibility of a simple polygon from a fixed point," with M. Sharir, International Journal of Computational Geometry and Applications, 3 (1993), 1-25.
• "Intersection queries in curved objects," with M. van Kreveld and M. Overmars, Journal of Algorithms 15 (1993), 229-266.
• "Ray shooting and parametric search," SIAM Journal on Computing 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 Journal on Computing 21 (1992), 540-570.

Geometric Summaries

• "Efficient algorithms for k-regret minimizing sets," with N. Kumar, S. Sintos, and S. Suri, in Proceedings Sixteenth Annual Symposium on Experimental Algorithms, 2017, 7:1-7:23
• "Embeddings of surfaces, curves, and moving points in Euclidean space," with S. Har-Peled and H. Yu, SIAM Journal on Computing 42 (2013), 442-458.
• "Mergeable summaries (invited)," with G. Cormode, Z. Huang, J. M. Phillips, Z. Wei, and K. Yi, in ACM Transactions on Database Systems, 38 (2013), 26.
• "Processing a large number of continuous preference top-k Queries," with A. Yu and J. Yang, in Proceedings ACM SIGMOD International Conference on 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 & Computational Geometry 39 (2008), 38-58.
• "Embeddings of surfaces, curves, and moving points in Euclidean space," with S. Har-Peled and H. Yu, in Twenty-Third Annual Symposium on Computational Geometry, 2007.
• "A space-optimal data-stream algorithm for coresets in the plane," with H. Yu, in Proceedings Twenty-Third Annual Symposium on Computational Geometry, 2007.
• "Approximation algorithms for k-line center," with C. M. Procopiuc and K. R. Varadarajan, Algorithmica, 42 (2005), 221-230.

Uncertain Data

• "Convex hull under uncertainty," with S. Har-Peled, S. Suri, H. Tildiz, and W. Zhang, in Algorithmica, 2017, 340-367.
• "Nearest-neighbor searching under uncertainty I," with A. Efrat, S. Sankararaman, and W. Zhang, Discrete and Computational Geometry, 58 (2017), 705-745.
• "Nearest-neighbor searching under uncertainty II," with B. Aronov, S. Har-Peled, J. Phillips, K. Yi, and W. Zhang, ACM Transactions on Algorithms, 13 (2016), 3:1-3:25.
• "Range-max queries on uncertain data," with N. Kumar, S. Sintos, and S. Suri, in Proceedings Thirty-Fifth Annual Symposium on Principles of Database Systems, 2016, 465-476.
• "Contour trees of uncertain terrains," with W. Zhang and S. Mukherjee, in Proceedings Twenty-Fourth ACM Symposium on Advances in Geographic Information Systems, 2015, 43:1-43:10.
• "Range searching on uncertain data," with S.-W. Cheng, Y. Tao, and K. Yi, ACM Transactions on Algorithms, 8 (2012), Article 43.
• "(Approximate) uncertain skylines," with P. Afshani, L. Arge, K. D. Larsen, and J. M. Phillips, in Fourteenth International Conference on Database Theory, 2011.

Trajectory Data Analysis

• "Subtrajectory clustering: models and algorithms," with K. Fox, K. Munagala, A. Nath, and J. Pan, in Proceedings Thirty-Seventh Annual Symposium on Principles of Database Systems, 2018, 75-87.
• "An efficient algorithm for placing electric vehicle charging stations," with J. Pan and W. Victor, in Proceedings Forty-First Annual International Symposium on Algorithms and Computation, 2016, 7:1-7:12
• "A simple efficient algorithm for dynamic time warping of two curves," with R. Ying, J. Pan, and K. Fox, in Proceedings Twenty-Fifth ACM Symposium on Advances in Geographic Information Systems, 2016, 25:1-25:10.

Kinetic Algorithms

• "Maintaining Reeb graphs of triangulated 2-manifolds," with K. Fox and A. Nath, in Proceedings Thirty-Seventh Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017, 8:1-8:14.
• "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 Journal on Computing 42 (2013), 442-458.
• "Kinetic stable Delaunay graphs," with J. Gao, L. Guibas, H. Kaplan, V. Koltun, N. Rubin, and M. Sharir, in Twenty-Sixth Annual Symposium on Computational Geometry, 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 Eighth 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 Twenty-Fourth Annual Symposium on Computational Geometry, 2008.
• "Embeddings of surfaces, curves, and moving points in Euclidean space," with S. Har-Peled and H. Yu, in Twenty-Third Annual Symposium on Computational Geometry, 2007.
• "A 2D kinetic tiangulation with near-quadratic topological changes," with Y. Wang and H. Yu, Discrete & Computational Geometry, 36 (2006), 573-592.
• "Out-of-order event processing in kinetic data structures," with M. A. Abam, M. de Berg, and H. Yu, in Fourteenth European Symposium on 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 Eighteenth Canadian Conference on Computational Geometry, 2005.
• "Collision detection for deforming necklaces," with L. J. Guibas, A. Nguyen, D. Russel, and L. Zhang, Computational Geometry: Theory & Applications, 28 (2004), 137-163.
• "Efficient tradeoff schemes in data structures for querying moving objects," with L. Arge, J. Erickson, and H. Yu, in Twelfth European Symposium on Algorithms, 2004.
• "Deformable free space tiling for kinetic collision detection," with J. Basch, L. J. Guibas, J. Hershberger, and L. Zhang, International Journal of Robotics Research, 21 (2002), 179-197.
• "Kinetic medians and kd-trees," with J. Gao and L. J. Guibas, in Tenth European Symposium on Algorithms, 2002.
• "STAR-tree: An efficent self-adjusting index for moving points," with C. M. Procopiuc and S. Har-Peled, in Fourth Workshop on Algorithms Engineering and Experiments, 2002.
• "Maintaining approximate extent measures of moving points," with S. Har-Peled, in Twelfth ACM-SIAM Symposium on Discrete Algorithms,, 2001.
• "Maintaining the extent of a moving point set," with L. Guibas, J. Hershberger, and E. Veach, Discrete & Computational Geometry, 26 (2001), 353-374.
• "Time responsive external data structures for moving points," with L. Arge and J. Vahrenhold, in Seventh Workshop on Algorithms and Data Structures, 2001.
• "Cylindrical static and kinetic binary space partitions," with L. Guibas, T.M. Murali, and J.S. Vitter, Computational Geometry: Theory & Applications 16 (2000), 103-127.
• "Indexing moving points," with L. Arge and J. Erickson, in Nineteenth ACM Symposium 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 & Computational Geometry, 24 (2000), 721-733.
• "Kinetic binary space partitions for intersecting segments and disjoint triangles," with J. Erickson and L. Guibas, in Ninth ACM-SIAM Symposium on Discrete Algorithms, 1998.
• "Parametric and kinetic minimum spanning trees," with D. Eppstein, L.J. Guibas, and M. Henzinger, in Thirty-Ninth Annual Symposium on Foundations of Computer Science, 1998.

GIS and Terrain Modeling

• "Flood risk analysis on terrains under the multi-flow-direction model," with A. Lowe, in Proceedings Twenty-Seventh ACM Symposium on Advances in Geographic Information Systems (best paper award), 2018, 53-62.
• "Flood risk analysis on terrains," with M. Rav and A. Lowe, in Proceedings Twenty-Sixth ACM Symposium on Advances in Geographic Information Systems, 2017, 36:1-36:10..
• "Massively parallel algorithms for computing TIN DEMs and contour trees for large terrains," with K. Fox, K. Munagala, and A. Nath, in Proceedings Twenty-Fifth ACM Symposium on Advances in Geographic Information Systems, 2016, 21:1-21:10.
• "Contour trees of uncertain terrains," with W. 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 correlation between piecewise-linear functions," with B. Aronov, M. van Kreveld, M. Löffler, and R. I. Silveira, SIAM Journal on Computing, 42 (2013), 1867-1887.
• "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.
• "Computing similarity between piecewise-linear functions," with B. Aronov, M. van Kreveld, M. Löffler, and R. I. Silveira, in Twenty-Sixth Annual Symposium on Computational Geometry, 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 contours on a terrain" with L. Arge, T. Mølhave, and B. Sadri, in Twenty-Fourth Annual Symposium on Computational Geometry, 2008, 129-138.
• "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 Proceedings Fifteenth ACM Symposium on Advances in GIS, 2007.
• "From point cloud to grid DEM: A scalable approach," with A. Danner and L. Arge, in Twelfth International Symposium on Spatial Data Handling, 2006.
• "I/O-efficient construction of constrained Delaunay triangulations," with L. Arge and K. Yi, in Thirteenth European Symposium on 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, Computational Geometry: Theory & Applications, 23 (2002), 195-208.
• "Approximating shortest paths on a nonconvex polyhedron," with K. Varadarajan, SIAM Journal on Computing 30 (2001), 1321-1340.
• "Efficient algorithms for approximating polygonal chains," with K. R. Varadarajan, Discrete & Computional Geometry, 23 (2000), 273-291.
• "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 Ninth ACM-SIAM Symposium on Discrete Algorithms (1998), 117-126.
• "Label placement by maximum independent set in rectangles," with M. van Kreveld and S. Suri, Computational Geometry: Theory & Applications, 11 (1998), 209-218.
• "Approximating shortest paths on a convex polytope in three dimensions," with S. Har-Peled, M. Sharir, and K. Varadarajan, Journal of the ACM, 44 (1997), 567-584.
• "An efficient algorithm for terrain simplification," with P. K. Desikan, in Eighth ACM-SIAM Symposium on Discrete Algorithms, 1997.
• "Connected component and simple polygon 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, International Journal of Geographic Information Systems, 1 (1987), 149-172.

Databases

• "Query perturbation analysis: An adventure of database researchers in fact-checking," with J.Yang, S. Roy, B. Walenz, Y. Wu, C. Yu, C. Li, in IEEE Data Engineering Bulletin, 41(3) 2018, 28-42.
• "Efficient algorithms for k-regret minimizing sets," with N. Kumar, S. Sintos, and S. Suri, in Proceedings Sixteenth Annual Symposium on Experimental Algorithms, 2017, 7:1-7:23
• "Nearest-neighbor searching under uncertainty I," with A. Efrat, S. Sankararaman, and W. Zhang, Discrete and Computational Geometry, 58 (2017), 705-745.
• "Nearest-neighbor searching under uncertainty II," with B. Aronov, S. Har-Peled, J. Phillips, K. Yi, and W. Zhang, ACM Transactions on Algorithms, 13 (2016), 3:1-3:25.
• "Parallel algorithms for constructing range and nearest-neighbor searching data structures," with K. Fox, K. Munagala, and A. Nath, in Proceedings Thirty-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 Thirty-Fifth Annual Symposium on Principles of Database Systems, 2016, 465-476.
• "Top-k preferences in high dimensions," with A. Yu and J. Yang IEEE Transactions on Knowledge and Data Engineering, 28 (2016), 311-325.
• "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.
• "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.
• "On "one of the few" objects," with Y. Wu, C. Li, J. Yang, and C. Yu, in Proceedings Eighteenth ACM International Conference on Knowledge Discovery and Data Mining, 2012.
• "Processing a large number of continuous preference top-k Queries," with A. Yu and J. Yang, in Proceedings ACM SIGMOD International Conference on Management of Data, 2012.
• "Processing and notifying range top-k subscriptions," with A. Yu, and J. Yang, in Proceedings Twenty-Eighth IEEE International Conference on Data Engineering, 2012.
• "(Approximate) uncertain skylines," with P. Afshani, L. Arge, K. D. Larsen, and J. M. Phillips, in Fourteenth International Conference on 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 Fifth 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 International Conference on Management of Data, 2008.
• "Scalable continuous query processing by tracking hotspots," with J. Xie, J. Yang, and H. Yu, in Annual IEEE International Conference on Very Large Databases 2006.
• "Monitoring continuous band-join queries over dynamic data," with J. Xie, J. Yang, and H. Yu, in Twenty-Sixth Annual International Symposium on Algorithms and Computation, 2005.
• "Bkd-tree: A dynamic scalable kd-tree," with O. Procopiuc, L. Arge, and J. S. Vitter, in Eighth Annual Symposium on Spatial & Temporal Databases, 2003.
• "CRB-tree: An efficient indexing scheme for range aggregate queries," with S. Govindarajan and L. Arge, in Ninth International Conference on 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 Twenty-Eighth Internatioanl Conference on Automata, Languages, and Programming, 2001.
• "Efficient searching with linear constraints," with L. Arge, J. Erickson, P. G. Franciosa, and J. S. Vitter, Journal of Computer and Systems Sciences, 61 (2000), 194-216.

Arrangements

• "An efficient algorithm for generalized polynomial partitioning and its applications," with B. Aronov, E. Ezra, and J. Zahl, in Proceedings Thirty-Fifth International Symposium on Computational Geometry, 2019.
• "Maintaining the union of unit discs under insertions with near-optimal overhead," with R. Cohen, D. Halperin, and W. Mulzer, in Proceedings Thirty-Fifth International Symposium on Computational Geometry, 2019.
• "Union of hypercubes and 3D Minkowski sums with random sizes," with H. Kaplan and M. Sharir, in Proceedings Forty-Fifth International Colloquium on Automata, Languages, and Programming, 2018, 10:1-10:15.
• "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 Twenty-Third Annual Symposium on Computational Geometry, 2007.
• "Computing a center-transversal line," with S. Cabello, J.A. Sellarès, and M. Sharir, in Proceedings Twenty Sixth Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2006, 93-104.
• Independent set of intersection graphs of convex objects in 2D," with N. H. Mustafa, Computational Geometry: Theory and Applications, 34 (2006), 83-95.
• "Pseudo-line arrangements: Duality, algorithms, and applications," with M. Sharir, SIAM Journal on Computing, 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, Journal of the 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 & Computational Geometry, 24 (2000), 645-685.
• "Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications," with A. Efrat and M. Sharir, SIAM Journal on Computing 29 (2000), 912-953.
• "Line transversals of balls and smallest enclosing cylinders in three dimensions," with B. Aronov and M. Sharir, Discrete & Computational Geometry 21 (1999), 373-388.
• "Computing many faces in arrangements of lines and segments," with J. Matousek and O. Schwarzkopf, SIAM Journal on Computing, 27 (1998), 491-505.
• "Constructing levels in arrangements and higher order Voronoi diagrams," with M. de Berg, J. Matousek, and O. Schwarzkopf, SIAM Journal on Computing 27 (1998), 654-667.
• "On levels in arrangements of lines, segments, planes, and triangles," with B. Aronov, T.M. Chan, and M. Sharir, Discrete & Computational Geometry, 19 (1998), 315-331.
• "Computing envelopes in four dimensions with applications," with B. Aronov and M. Sharir, SIAM Journal on Computing, 26 (1997), 1714-1732.
• "Efficient randomized algorithms for some geometric optimization problems," with M. Sharir, Discrete & Computational Geometry, 16 (1996), 317-337
• "The overlay of lower envelopes and its applications," with O. Schwarzkopf and M. Sharir, Discrete & Computational Geometry, 15 (1996), 1-13.
• "Implicit point location in arrangements of line segments, with an application to motion planning," with M. van Kreveld, International Journal of Computational Geometry & Applications, 4 (1994), 369-383.
• "Applications of a new space partitioning technique," with M. Sharir, Discrete & Computational Geometry, 9 (1993), 11-38.
• "Counting circular arc intersections," with M. Pellegrini and M. Sharir, SIAM Journal on Computing, 22 (1993), 778-793.
• "Counting facets and incidences," with B. Aronov, Discrete & Computational Geometry, 7 (1992), 359-369.
• "Partitioning arrangements of lines: I. An efficient deterministic algorithm," Discrete & Computational Geometry, 5 (1990), 449-483.
• "Partitioning arrangements of lines: II. Applications," Discrete & Computational Geometry, 5 (1990), 533-573.

Combinatorial Geometry

• "Union of hypercubes and 3D Minkowski sums with random sizes," with H. Kaplan and M. Sharir, in Proceedings Forty-Fifth International Colloquium on Automata, Languages, and Programming, 2018, 10:1-10:15.
• "Union of random Minkowski sums and network vulnerability analysis," with H. Kaplan and M. Sharir, in Proceedings Twenty-Ninth Annual Symposium on Computational Geometry, 2013.
• "Similar simplices in a d-dimensional point set," with R. Apfelbaum, G. Purdy, and M. Sharir, in Twenty-Third Annual Symposium on Computational Geometry, 2007.
• "On lines avoiding unit balls in three dimensions," with B. Aronov, V. Koltun, and M. Sharir, Discrete & Computational Geometry, 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, Journal of the 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 & Computational Geometry, 28 (2002), 123-150.
• "On levels in arrangements of lines, segments, planes, and triangles," with B. Aronov and M. Sharir, in Thirteenth Annual Symposium on Computational Geometry, 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.
• "Line stabbing bounds in three dimensions," with B. Aronov and S. Suri, in Eleventh Annual Symposium on Computational Geometry, 1995.
• "Can visibility graphs be represented compactly?" with N. Alon, B. Aronov, and S. Suri, Discrete & Computational Geometry, 12 (1994), 347-365.
• "On stabbing lines for convex polyhedra in 3D," Computational Geometry: Theory & Applications, 4 (1994), 177-189.
• "Counting facets and incidences," with B. Aronov, Discrete & Computational Geometry, 7 (1992), 359-369.
• "Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences," with M. Sharir and P. Shor, Journal of Combinatorial Theory, Series A, 52 (1989), 228-274.

Robotics

• "Computing shortest paths in the plane with removable obstacles," with N. Kumar, S. Sintos, and S. Suri, in Proceedings Sixteenth Scandinavian Workshop on Algorithm Theory, 2018, 5:1-5:15.
• "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 Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009.
• "On approximate geodesic-distance queries amid deforming point clouds," with A. Efrat, R. Sharathkumar, and H. Yu, in Eighth Workshop on Algorithmic Foundations of Robotics, 2008.
• "A near-quadratic algorithm for fence design," with R.-P. Berretty and A. D. Collins, Discrete & Computational Geometry, 33 (2005), 463-481.
• "HPRM: A hierarchical PRM," with A. D. Collins and J. Harer in Proceedings International Conference on 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 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, International Journal of Robotics Research, 21 (2002), 179-197.
• "Polygon decomposition for efficient construction of Minkowski sums," with E. Flato and D. Halperin, Computational Geometry: Theory & Applications, 21 (2002), 21-38.
• "Approximation algorithms for curvature-constrained shortest paths," with H. Wang, SIAM Journal on Computing, 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 Journal of Computing, 7 (2000), 227-240.
• "Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions," with M. Sharir, Discrete & Computational Geometry, 24 (2000), 645-685.
• "Motion planning of a ball amid segments in three dimensions," with M. Sharir, in Tenth ACM-SIAM Symposium on Discrete Algorithms, 1999.
• "Motion planning for a convex polygon in a polygonal environment," with B. Aronov and M. Sharir, Discrete & Computational Geometry, 22 (1999), 201-221.
• "Nonholonomic path planning for pushing a disk among obstacles," with J.-C. Latombe, R. Motwani, and P. Raghavan, in IEEE Conference on Robotics and Automation, 1997.
• "Star unfolding of a polytope with applications," with B. Aronov, J. O’Rourke, and C. Schevon, SIAM Journal on Computing, 26 (1997), 1689-1713.
• "Efficient generation of k-directional assembly sequences," with M. de Berg, D. Halperin, and M. Sharir, in Seventh ACM-SIAM Sympsium on Discrete Algorithms, 1996.
• "Largest placements and motion planning of a convex polygon," with N. Amenta, B. Aronov, and M. Sharir, in Second 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 Twenty-Seventh ACM Symposium on Theory of Computing, 1995.
• "Red-blue intersection detection algorithms, with applications to motion planning and collision detection," with M. Sharir, SIAM Journal on Computing, 19 (1990), 297-322.

Ecological Modeling

• "Exploiting temporal coherence in forest dynamics simulation," with T. Mølhave, H. Yu, and J. Clark, in Twenty-Seventh Annual Symposium on Computational Geometry, 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 Twentieth Annual Symposium on Computational Geometry, 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.

Sensor Networks

• "On channel-discontinuity-constraint routing in wireless networks", with S. Sankararaman, A. Efrat, and S. Ramasubramanian, in Ad-Hoc Networks, 13 (2014), 153-169
• "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.
• "The resilience of WDM networks to probabilistic geographical failures," with A. Efrat, S. Ganjugunte, D. Hay, S. Sankararaman, G. Zussman, in Thirtieth 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 Fifth IEEE International Conference on Distributed Computing in Sensor Systems (best paper), 2009.
• "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).
• "Scalable continuous query processing by tracking hotspots," with J. Xie, J. Yang, and H. Yu, in Annual IEEE International Conference on 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 Twenty-Sixth Annual International Symposium on Algorithms and Computation, 2005.

Computational Molecular Biology

• "Hausdorff distance under translation for points, and balls," with S. Har-Peled, M. Sharir, and Y. Wang, in ACM Transactions on Algorithms, 2010.
• "Fast molecular shape matching using contact maps," with N. Mustafa and Y. Wang. Journal of Computational Biology, 14 (2007), 131-143.
• "Faster algorithms for optimal multiple sequence alignment based on pairwise comparisons," with Y. Bilu and R. Kolodny, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3 (2006), 408-422.
• "Segmenting motifs in protein-protein interface surfaces," with J. Phillips and J. Rudolph, in Proceedings Sixth 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 Symposium on Biocomputing, 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, Computational Geometry: Theory & Applications, 28 (2004), 137-163.
• "Computing the writhing number of a polygonal knot," with H. Edelsbrunner and Y. Wang, Discrete & Computational Geometry, 32 (2004), 37-54.
• "Local search heuristic for rigid protein docking," with V. Choi, H. Edelsbrunner, and J. Rudolph, in Proceedings Fourth Workshop on Algorithms in Bioinformatics, 2004.

Computer Graphics and Visualization

• "An on-line occlusio-culling algorithm for fast walkthrough in urban areas," with S. Har-Peled and Y. Wang, in Eurographics, 2001.
• "Binary space partitions for fat rectangles," with E. Grove, T.M. Murali, and J.S. Vitter, SIAM Journal on Computing, 29 (2000), 1422-1448.
• "Cylindrical static and kinetic binary space partitions," with L. Guibas, T.M. Murali, and J.S. Vitter, Computational Geometry: Theory & Applications 16 (2000), 103-127.
• "Lower bounds for kinetic planar subdivisions," with J. Basch, M. de Berg, L. J. Guibas, and J. Hershberger, Discrete & Computational Geometry, 24 (2000), 721-733.
• "Kinetic binary space partitions for intersecting segments and disjoint triangles," with J. Erickson and L. Guibas, in Ninth ACM-SIAM Symposium on Discrete Algorithms, 1998.
• "Surface approximation and geometric partitions," with S. Suri, SIAM Journal on Computing 27 (1998), 1016-1035.
• "An efficient algorithm for terrain simplification," with P. K. Desikan, in Eighth ACM-SIAM Symposium on Discrete Algorithms, 1997.
• "Practical techniques for constructing binary space partitions for orthogonal rectangles," with T. M. Murali and J. S. Vitter, in Proceedings Thirteenth Annual Symposium on Computational Geometry, 1997, 382-384.
• "Simplification envelopes," with J. Cohen, A. Varshney, D. Manocha, G. Turk, F. Brooks, H. Weber, and W. Wright, in SIGGRAPH, 1996, 119-128.
• "Computing depth orders for fat objects and related problems," with M. Katz and M. Sharir, Computational Geometry Theory & Applications., 5 (1995), 187-206.
• "On the number of views of polyhedral terrains," with M. Sharir, Discrete & Computational Geometry, 12 (1994), 177-182.