Publications: Papers by Year

See also:  Papers by Subject | Books | Surveys

2015-

• "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.
• "Geometric partial matchings and unbalanced transportation problem," with H.-C. Chang and A. Xiao, 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 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.
• "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.
• "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.
• "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.
• "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.
• "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.
• "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.
• "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.
• "Convex hull under uncertainty," with S. Har-Peled, S. Suri, H. Tildiz, and W. Zhang, in Algorithmica, 2017, 340-367.
• "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
• "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
• "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..
• "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.
• "Nearest-neighbor searching under uncertainty I," with A. Efrat, S. Sankararaman, and W. Zhang, Discrete and Computational Geometry, 58 (2017), 705-745.
• "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.
• "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.
• "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.
• "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.
• "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.
• "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.
• "Top-k preferences in high dimensions," with A. Yu and J. Yang IEEE Transactions on Knowledge and Data Engineering, 28 (2016), 311-325.
• "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.
• "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.
• "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.

2010-2014

• "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 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.
• "Near-linear algorithms for geometric hitting sets and set covers," with J. Pan, in Proceedings Thirtieth Annual Symposium on Computational Geometry, 2014, 271-280.
• "On channel-discontinuity-constraint routing in wireless networks", with S. Sankararaman, A. Efrat, and S. Ramasubramanian, in Ad-Hoc Networks, 13 (2014), 153-169
• "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.
• "The 2-center problem in three dimensions," with R. Ben Avraham and M. Sharir, Computational Geometry: Theory and Applications, 46 (2013), 734-746.
• "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.
• "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.
• "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.
• "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.
• "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.
• "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.
• "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.
• "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.
• "Algorithms for the transportation problem in geometric settings," with R. Sharathkumar, in Proceedings Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012.
• "Near-linear approximation algorithms for geometric hitting sets," with E. Ezra and M. Sharir, Algorithmica, 63 (2012), 1-25.
• "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.
• "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.
• "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.
• "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.
• "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.
• "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.
• "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.
• "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.
• "Subscriber assignment for wide-area content-based publish/subscribe," with A. Yu and J. Yang, in International Conference on Data Engineering, 2011.
• The 2-center problem in three dimensions," with R. Ben Avraham and M. Sharir, in Proceedings Twenty-Sixth Annual Symposium on Computational Geometry, 2010.
• "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.
• "Hausdorff distance under translation for points, and balls," with S. Har-Peled, M. Sharir, and Y. Wang, in ACM Transactions on Algorithms, 2010.
• "An improved algorithm for computing the volume of the union of cubes," in Proceedings Twenty-Sixth Annual Symposium on Computational Geometry, 2010.
• "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 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.
• "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.
• "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.
• "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.
• "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.

2005-2009

• "Approximate Euclidean shortest paths amid convex obstacles," with R. Sharathkumar and H. Yu, in Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009.
• "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.
• "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.).
• "Algorithms for center and Tverberg points," with M. Sharir and E. Welzl, ACM Transactions on Algorithms, 5, 1 (2008), Article 5, (20 pp.).
• Computing contour maps and answering contour queries, Dagstuhl Seminar on Data Structures, 2008.
• "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.
• "An efficient algorithm for Euclidean 2-center with outliers," with J. Phillips, in Sixteenth European Symposium on Algorithms, 2008.
• "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.
• "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.
• "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.
• "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.
• "Robust shape fitting via peeling and grating coresets," with S. Har-Peled and H. Yu, Discrete & Computational Geometry 39 (2008), 38-58.
• "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.
• "State of the union (of geometric objects): A Review," with J. Pach and M. Sharir, in Computational Geometry: Twenty Years Later (J. Goodman, J.Pach, and R. Pollack, eds.), American Mathematical Society, Providence, 2008, pp. 9-48.
• "Untangling triangulations through local explorations," with B. Sadri and H. Yu, in Twenty-Fourth Annual Symposium on Computational Geometry, 2008.
• "Computing the volume of the union of cubes," with H. Kaplan and M. Sharir, in Twenty-Third Annual Symposium on Computational Geometry, 2007.
• "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.
• "Fast molecular shape matching using contact maps," with N. Mustafa and Y. Wang. Journal of Computational Biology, 14 (2007), 131-143.
• "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).
• Modeling and analyzing massive terrain data sets, Annual Symposium of Geometric Processing, Barcelona, Spain, 2007.
• Modeling and analyzing massive terrain data sets, International Symposium on Algorithms and Computation, 2007.
• "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.
• "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.
• "A space-optimal data-stream algorithm for coresets in the plane," with H. Yu, in Proceedings Twenty-Third Annual Symposium on Computational Geometry, 2007.
• A space–optimal data–stream algorithm for coresets in the plane, Workshop on Computational Geometry, Dagstuhl, Germany, 2007.
• "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.
• "A 2D kinetic tiangulation with near-quadratic topological changes," with Y. Wang and H. Yu, Discrete & Computational Geometry, 36 (2006), 573-592.
• "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.
• "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.
• "Approximating extent measures of points," with S. Har-Peled and K.R. Varadarajan, Journal of the ACM, 51 (2004), 606-635.
• "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.
• "From point cloud to grid DEM: A scalable approach," with A. Danner and L. Arge, in Twelfth International Symposium on Spatial Data Handling, 2006.
• Geometric approximation using coresets, Workshop on Algorithms, Nachsholim, Israel, 2006.
• Independent set of intersection graphs of convex objects in 2D," with N. H. Mustafa, Computational Geometry: Theory and Applications, 34 (2006), 83-95.
• I/O-efficient batched union-find and its applications to terrain analysis, Workshop on Data Structures, Dagstuhl, Germany, 2006.
• Kinetic algorithms: approximation and trade-offs, Discrete and Computational Geometry: Twenty Years Later, Snowbird, UT, 2006.
• "On bipartite matching under the rms distance," with J. Phillips, in Seventeenth Canadian Conference on Computational Geometry, 2006.
• "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.
• "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 motifs in protein-protein interface surfaces," with J. Phillips and J. Rudolph, in Proceedings Sixth Workshop on Algorithms in Bioinformatics, 2006.
• "Segmenting object space by geometric reference structures," with D. Brady and J. Matousek, ACM Transactions on Sensor Networks, 2 (2006), 455-465.
• "Approximation algorithms for k-line center," with C. M. Procopiuc and K. R. Varadarajan, Algorithmica, 42 (2005), 221-230.
• "Approximation algorithms for k-line center," with C. M. Procopiuc and K. R. Varadarajan, Algorithmica, 42 (2005), 221-230.
• "Coarse and reliable geometric alignment for protein docking," with Y. Wang, P. Brown, H. Edelsbrunner, and J. Rudolph, in Pacific Symposium on Biocomputing, 2005.
• Extreme elevation on a 2-manifold, Second Joint Meeting of AMS, DMV, ÖMG, Mainz, Germany, 2005.
• "Geometric approximation via coresets," with S. Har-Peled and K. R. Varadarajan, in Combinatorial and Computational Geometry (J. E. Goodman, J. Pach, and E.Welzl, eds.), Cambridge University Press, New York, 2005, pp. 1-30.
• "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.
• "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.
• "Near-linear time approximation algorithms for curve simplification," with S. Har-Peled, N. Mustafa, and Y. Wang, Algorithmica, 42 (2005), 203-219.
• "A near-quadratic algorithm for fence design," with R.-P. Berretty and A. D. Collins, Discrete & Computational Geometry, 33 (2005), 463-481.
• "On lines avoiding unit balls in three dimensions," with B. Aronov, V. Koltun, and M. Sharir, Discrete & Computational Geometry, 34 (2005) 231-250.
• "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.
• "Pseudo-line arrangements: Duality, algorithms, and applications," with M. Sharir, SIAM Journal on Computing, 34 (2005), 526-552.
• "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.

2000-2004

• "Approximating extent measures of points," with S. Har-Peled and K.R. Varadarajan, Journal of the ACM, 51 (2004), 606-635.
• "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.
• "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.
• "k-means projective clustering," with N. H. Mustafa, in Proceedings Twenty-Third Annual Symposium on Principles of Database Systems, 2004.
• "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.
• "Local search heuristic for rigid protein docking," with V. Choi, H. Edelsbrunner, and J. Rudolph, in Proceedings Fourth Workshop on Algorithms in Bioinformatics, 2004.
• "A near-linear constant-factor approximation for Euclidean bipartite matching?, with K. R. Varadarajan, in Proceedings Twentieth Annual Symposium on Computational Geometry, 2004.
• "A scalable simulator for forest dynamics," with S. Govindrajan, M. Dietze, and J. Clark, in Twentieth Annual Symposium on Computational Geometry, 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.
• "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.
• "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.
• "HPRM: A hierarchical PRM," with A. D. Collins and J. Harer in Proceedings International Conference on Robotics and Automation, 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.
• "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.
• "The paradox of species diversity," with J. Clark, M. Dietze, and S. Govindarajan, in Ecological Society of America Annual Meeting, 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.
• "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.
• "Computing approximate shortest paths on convex polytopes," with S. Har-Peled and M. Karia, Algorithmica, 33 (2002), 227-242.
• "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.
• "Exact and approximation algorithms for clustering," with C.M. Procopiuc, Algorithmica, 33 (2002), 201-226.
• "Kinetic medians and kd-trees," with J. Gao and L. J. Guibas, in Tenth European Symposium on Algorithms, 2002.
• "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.
• "On the numbers of congruent simplices in a point set," with M. Sharir, Discrete & Computational Geometry, 28 (2002), 123-150.
• "Output-sensitive algorithms for uniform partitions of points," with B. Bhattacharya and S. Sen, Algorithmica, 32 (2002), 521-539.
• "Polygon decomposition for efficient construction of Minkowski sums," with E. Flato and D. Halperin, Computational Geometry: Theory & Applications, 21 (2002), 21-38.
• "Range searching in categorical data: Colored range searching on grid," with S. Govindarajan and S. Muthukrishnan, in Tenth European Symposium on Algorithms, 2002.
• "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.
• "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.
• "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.
• "Approximation algorithms for curvature-constrained shortest paths," with H. Wang, SIAM Journal on Computing, 30 (2001), 1739-1772.
• "Approximating shortest paths on a nonconvex polyhedron," with K. Varadarajan, SIAM Journal on Computing 30 (2001), 1321-1340.
• "Exact and approximation algorithms for minimum-width cylindrical shells," with B. Aronov and M. Sharir, Discrete & Computational Geometry, 26 (2001), 307-320.
• "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.
• "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.
• "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.
• "Minimal trap design," with A. D. Collins and J. Harer, in IEEE Conference on Robotics and Automation, 2001.
• "An on-line occlusio-culling algorithm for fast walkthrough in urban areas," with S. Har-Peled and Y. Wang, in Eurographics, 2001.
• "Time responsive external data structures for moving points," with L. Arge and J. Vahrenhold, in Seventh Workshop on Algorithms and Data Structures, 2001.
• "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.
• "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.
• "Efficient algorithms for approximating polygonal chains," with K. R. Varadarajan, Discrete & Computional Geometry, 23 (2000), 273-291.
• "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.
• "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.
• "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.
• "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.

1995-2000

• "Approximation algorithms for bipartite and nonbipartite matchings in the plane," with K. R. Varadarajan, in Proceedings Tenth ACM-SIAM Symposium on Discrete Algorithms, 1999.
• "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.
• "Line transversals of balls and smallest enclosing cylinders in three dimensions," with B. Aronov and M. Sharir, Discrete & Computational Geometry 21 (1999), 373-388.
• "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.
• "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.
• "The discrete 2-center problem," with M. Sharir and E. Welzl, Discrete & Computational Geometry, 20 (1998), 287-306.
• "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.
• "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.
• "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.
• "Label placement by maximum independent set in rectangles," with M. van Kreveld and S. Suri, Computational Geometry: Theory & Applications, 11 (1998), 209-218.
• "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.
• "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.
• "Surface approximation and geometric partitions," with S. Suri, SIAM Journal on Computing 27 (1998), 1016-1035.
• "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.
• "Computing envelopes in four dimensions with applications," with B. Aronov and M. Sharir, SIAM Journal on Computing, 26 (1997), 1714-1732.
• "An efficient algorithm for terrain simplification," with P. K. Desikan, in Eighth ACM-SIAM Symposium on Discrete Algorithms, 1997.
• "Linear approximation of simple objects," with K. Varadarajan, Information Processing Letters, 62 (1997), 89-94.
• "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.
• "On levels in arrangements of lines, segments, planes, and triangles," with B. Aronov and M. Sharir, in Thirteenth Annual Symposium on Computational Geometry, 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.
• "Quasi-planar graphs have a linear number of edges," with B. Aronov, J. Pach, R. Pollack, and M. Sharir, Combinatorica, 17 (1997), 1-9.
• "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.
• "Efficient randomized algorithms for some geometric optimization problems," with M. Sharir, Discrete & Computational Geometry, 16 (1996), 317-337
• "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.
• "The overlay of lower envelopes and its applications," with O. Schwarzkopf and M. Sharir, Discrete & Computational Geometry, 15 (1996), 1-13.
• "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.
• "Selection in monotone matrices and computing kth nearest neighbors," with S. Sen, Journal of Algorithms, 20 (1996), 581-601.
• "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.
• "Dynamic half-space range reporting and its applications," with J. Matousek, Algorithmica, 13 (1995), 325-345.
• "Line stabbing bounds in three dimensions," with B. Aronov and S. Suri, in Eleventh Annual Symposium on Computational Geometry, 1995.
• "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.

1990-1994

• "Applications of parametric searching in geometric optimization," with M. Sharir and S. Toledo, Journal of Algorithms, 17 (1994), 292-318.
• "Can visibility graphs be represented compactly?" with N. Alon, B. Aronov, and S. Suri, Discrete & Computational Geometry, 12 (1994), 347-365.
• "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.
• "On the number of views of polyhedral terrains," with M. Sharir, Discrete & Computational Geometry, 12 (1994), 177-182.
• "On range searching with semialgebraic sets," with J. Matousek, Discrete & Computational Geometry, 11 (1994), 393-418.
• "On stabbing lines for convex polyhedra in 3D," Computational Geometry: Theory & Applications, 4 (1994), 177-189.
• "Planar geometric location problems," with M. Sharir, Algorithmica, 11 (1994), 185-195.
• "Applications of a new space partitioning technique," with M. Sharir, Discrete & Computational Geometry, 9 (1993), 11-38.
• "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.
• "Computing a segment center for a planar point set," with A. Efrat, M. Sharir, and S. Toledo, Journal of Algorithms, 15 (1993), 314-323.
• "Counting circular arc intersections," with M. Pellegrini and M. Sharir, SIAM Journal on Computing, 22 (1993), 778-793.
• "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.
• "Selecting distances in the plane," with B. Aronov, M. Sharir, and S. Suri, Algorithmica, 9 (1993), 495-514.
• "Counting facets and incidences," with B. Aronov, Discrete & Computational Geometry, 7 (1992), 359-369.
• "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.
• "Intersection queries in sets of discs," with M. van Kreveld and M. Overmars, BIT 32 (1992), 268-279.
• "Oriented aligned rectangle packing problem," with M. T. Shing, European Journal of Operational Research, 62 (1992), 210-220.
• "Ray shooting and other applications of spanning trees with low stabbing number," SIAM Journal on Computing 21 (1992), 540-570.
• "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.
• "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.
• "Red-blue intersection detection algorithms, with applications to motion planning and collision detection," with M. Sharir, SIAM Journal on Computing, 19 (1990), 297-322.

1985-1989

• "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.
• "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.