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 ThirtyFifth International Symposium on Computational Geometry, 2019.
 "Geometric partial matchings and unbalanced transportation problem," with H.C. Chang and A. Xiao, in Proceedings ThirtyFifth International Symposium on Computational Geometry, 2019.
 "Maintaining the union of unit discs under insertions with nearoptimal overhead," with R. Cohen, D. Halperin, and W. Mulzer, in Proceedings ThirtyFifth International Symposium on Computational Geometry, 2019.
 "Approximate minimumweight matching with outliers under translation," with H. Kaplan, G. Kipper, W. Mulzer, G. Rote, M. Sharir, and A. Xiao, in Proceedings FortyThird Annual International Symposium on Algorithms and Computation, 2018, 26:126: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:15:15.
 "Flood risk analysis on terrains under the multiflowdirection model," with A. Lowe, in Proceedings TwentySeventh ACM Symposium on Advances in Geographic Information Systems (best paper award), 2018, 5362.
 "Improved dynamic geodesic nearest neighbor searching in a simple polygon," with L. Arge and F. Staals, in Proceedings ThirtyFourth International Symposium on Computational Geometry, 2018, 4:14:14.
 "Query perturbation analysis: An adventure of database researchers in factchecking," with J.Yang, S. Roy, B. Walenz, Y. Wu, C. Yu, C. Li, in IEEE Data Engineering Bulletin, 41(3) 2018, 2842.
 "Subtrajectory clustering: models and algorithms," with K. Fox, K. Munagala, A. Nath, and J. Pan, in Proceedings ThirtySeventh Annual Symposium on Principles of Database Systems, 2018, 7587.
 "Union of hypercubes and 3D Minkowski sums with random sizes," with H. Kaplan and M. Sharir, in Proceedings FortyFifth International Colloquium on Automata, Languages, and Programming, 2018, 10:110:15.
 "Approximate nearest neighbor search amid higherdimensional flats," with N. Rubin and M. Sharir, in Proceedings TwentyFifth European Symposium on Algorithms, 2017, 4:14:13.
 "Convex hull under uncertainty," with S. HarPeled, S. Suri, H. Tildiz, and W. Zhang, in Algorithmica, 2017, 340367.
 "Efficient algorithms for kregret minimizing sets," with N. Kumar, S. Sintos, and S. Suri, in Proceedings Sixteenth Annual Symposium on Experimental Algorithms, 2017, 7:17:23
 "Faster algorithms for the geometric transportation problem," with K. Fox, D. Panigrahi, K. R. Varadarajan, and A. Xiao, in Proceedings ThirtyThird International Symposium on Computational Geometry, 2017, 7:17:16
 "Flood risk analysis on terrains," with M. Rav and A. Lowe, in Proceedings TwentySixth ACM
Symposium on Advances in Geographic Information Systems, 2017, 36:136:10..
 "Maintaining Reeb graphs of triangulated 2manifolds," with K. Fox and A. Nath, in Proceedings ThirtySeventh Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017, 8:18:14.
 "Nearestneighbor searching under uncertainty I," with A. Efrat, S. Sankararaman, and W. Zhang, Discrete and Computational Geometry, 58 (2017), 705745.
 "Approximating dynamic time warping and edit distance of a pair of point sequences," with K. Fox, J. Pan, and R. Ying, in Proceedings ThirtySecond International Symposium on Computational Geometry, 2016, 6:16:16.
 "An efficient algorithm for computing high quality paths amid polygonal obstacles," with K. Fox and O. Salzmann, in Proceedings TwentySixth Annual ACMSIAM Symposium on Discrete Algorithms, 2016, 11791192.
 "An efficient algorithm for placing electric vehicle charging stations," with J. Pan and W. Victor, in Proceedings FortyFirst Annual International Symposium on Algorithms and Computation, 2016, 7:17:12
 "Markovmodulated marked Poisson processes for checkin data," with J. Pan, V. Rao, and A. Gelfand, in Proceedings ThirtyThird 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 TwentyFifth ACM Symposium on Advances in Geographic Information Systems, 2016, 21:121:10.
 "Nearestneighbor searching under uncertainty II," with B. Aronov, S. HarPeled, J. Phillips, K. Yi, and W. Zhang, ACM Transactions on Algorithms, 13 (2016), 3:13:25.
 "Parallel algorithms for constructing range and nearestneighbor searching data structures," with K. Fox, K. Munagala, and A. Nath, in Proceedings ThirtyFifth Annual Symposium on Principles of Database Systems, 2016, 429440.
 "Rangemax queries on uncertain data," with N. Kumar, S. Sintos, and S. Suri, in Proceedings ThirtyFifth Annual Symposium on Principles of Database Systems, 2016, 465476.
 "A simple efficient algorithm for dynamic time warping of two curves," with R. Ying, J. Pan, and K. Fox, in Proceedings TwentyFifth ACM Symposium on Advances in Geographic Information Systems, 2016, 25:125:10.
 "Topk preferences in high dimensions," with A. Yu and J. Yang IEEE Transactions on Knowledge and Data Engineering, 28 (2016), 311325.
 "Computing the GromovHausdorff 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, 529540.
 "Contour trees of uncertain terrains," with W. Zhang and S. Mukherjee, in Proceedings TwentyFourth ACM Symposium on Advances in Geographic Information Systems, 2015, 43:143: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), 871904.
 "Maintaining contour trees of dynamic terrains," with T. Mølhave, M. Revsbaek, I. Safa, Y. Wang, and J. Yang, in Proceedings ThirtyFirst International Symposium on Computational Geometry, 2015, 796811.
20102014
 "Approximation algorithms for bipartite matching with metric and geometric costs," with R. Sharathkumar, in Proceedings FortySixth Annual ACM Symposium on Theory of Computing, 2014, 555564.
 "Computing highly occluded paths using a sparse network," with N. Lebeck and T. Mølhave, in Proceedings TwentyThird ACM Symposium on Advances in Geographic Information Systems, 2014, 110.
 "Nearlinear algorithms for geometric hitting sets and set covers," with J. Pan, in Proceedings Thirtieth Annual Symposium on Computational Geometry, 2014, 271280.
 "On channeldiscontinuityconstraint routing in wireless networks", with S. Sankararaman, A. Efrat, and S. Ramasubramanian, in AdHoc Networks, 13 (2014), 153169
 "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, 589600.
 "The 2center problem in three dimensions," with R. Ben Avraham and M. Sharir, Computational Geometry: Theory and Applications, 46 (2013), 734746.
 "Computing correlation between piecewiselinear functions," with B. Aronov, M. van Kreveld, M. Löffler, and R. I. Silveira, SIAM Journal on Computing, 42 (2013), 18671887.
 "Computing the discrete Fréchet distance in subquadratic time," with R. Ben Avraham, H. Kaplan, and M. Sharir, in Proceedings TwentyFourth Annual ACMSIAM Symposium on Discrete
Algorithms, 2013, 155167.
 "Computing highly occluded paths on a terrain," with N. Lebeck and T. Mølhave, in Proceedings TwentySecond ACM Symposium on Advances in Geographic Information Systems 2013, 1423.
 "Computing correlation between piecewiselinear functions," with B. Aronov, M. van Kreveld, M. Löffler, and R. I. Silveira, SIAM Journal on Computing, 42 (2013), 18671887.
 "Efficient external memory structures for rangeaggregate queries," with L. Arge, S. Govindrajan, J. Yang, and K. Yi, Computational Geometry: Theory and Applications, 46 (2013), 358370.
 "Embeddings of surfaces, curves, and moving points in Euclidean space," with S. HarPeled and H. Yu, SIAM Journal on Computing 42 (2013), 442458.
 "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.
 "Modeldriven matching and segmentation of trajectories," with S. Sankararaman, T. Mølhave, J. Pan, and A. P. Boedihardjo, in Proceedings TwentySecond ACM Symposium on Advances in Geographic Information Systems, 2013, 234243.
 "On range searching with semialgebraic sets II," with J. Matoušek and M. Sharir, in SIAM Journal on Computing, 42 (2013), 20392062.
 "Sparsification of motionplanning 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 TwentyNinth Annual Symposium on Computational Geometry, 2013.
 "Algorithms for the transportation problem in geometric settings," with R. Sharathkumar, in Proceedings TwentyThird Annual ACMSIAM Symposium on Discrete Algorithms, 2012.
 "Nearlinear approximation algorithms for geometric hitting sets," with E. Ezra and M. Sharir, Algorithmica, 63 (2012), 125.
 "A nearlinear time εapproximation algorithm for geometric bipartite matching," with R. Sharathkumar, in Proceedings FortyFourth 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 stabbingsemigroup queries," with L. Arge, H. Kaplan, E. Molad, R. E. Tarjan, K. Yi, SIAM Journal on Computing, 41 (2012), 104127.
 "Processing a large number of continuous preference topk Queries," with A. Yu and J. Yang, in Proceedings ACM SIGMOD International Conference on Management of Data, 2012.
 "Processing and notifying range topk subscriptions," with A. Yu, and J. Yang, in Proceedings TwentyEighth 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 TwentySeventh 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), 15231536.
 "I/Oefficient contour queries on terrains," with T. Mølhave and B. Sadri, in TwentySecond Annual ACMSIAM 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 widearea contentbased publish/subscribe," with A. Yu and J. Yang, in International Conference on Data Engineering, 2011.
 The 2center problem in three dimensions," with R. Ben Avraham and M. Sharir, in Proceedings TwentySixth Annual Symposium on Computational Geometry, 2010.
 "Computing similarity between piecewiselinear functions," with B. Aronov, M. van Kreveld, M. Löffler, and R. I. Silveira, in TwentySixth 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), 352390.
 "Hausdorff distance under translation for points, and balls," with S. HarPeled, 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 TwentySixth Annual Symposium on Computational Geometry, 2010.
 "I/Oefficient batched unionfind 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 TwentySixth 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 highresolution 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 TwentyFirst Annual ACMSIAM Symposium on Discrete Algorithms, 2010.
20052009
 "Approximate Euclidean shortest paths amid convex obstacles," with R. Sharathkumar and H. Yu, in Twentieth Annual ACMSIAM 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 widearea contentbased 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 TwentyEighth Annual Symposium on Principles of Database Systems, 2009.
 "Inputsensitive 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), 1737.
 "An efficient algorithm for Euclidean 2center 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 TwentyFourth Annual Symposium on Computational Geometry, 2008, 129138.
 "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 geodesicdistance 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), 4254.
 "Practical methods for shape fitting and kinetic data structures using coresets," with R. Poreddy, K. Varadarajan, and H. Yu, Algorithmica, 52 (2008), 378402.
 "ProSem: Scalable widearea 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. HarPeled and H. Yu, Discrete & Computational Geometry 39 (2008), 3858.
 "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. 948.
 "Untangling triangulations through local explorations," with B. Sadri and H. Yu, in TwentyFourth Annual Symposium on Computational Geometry, 2008.
 "Computing the volume of the union of cubes," with H. Kaplan and M. Sharir, in TwentyThird Annual Symposium on Computational Geometry, 2007.
 "Embeddings of surfaces, curves, and moving points in Euclidean space," with S. HarPeled and H. Yu, in TwentyThird 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), 131143.
 "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), 3961.
 "Similar simplices in a ddimensional point set," with R. Apfelbaum, G. Purdy, and M. Sharir, in TwentyThird Annual Symposium on Computational Geometry, 2007.
 "A spaceoptimal datastream algorithm for coresets in the plane," with H. Yu, in Proceedings TwentyThird 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 nearquadratic topological changes," with Y. Wang and H. Yu, Discrete & Computational Geometry, 36 (2006), 573592.
 "Computing a centertransversal 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, 93104.
 "Computing maximally separated sets in the plane," with M. Overmars and M. Sharir, in SIAM Journal on Computing," 36 (2006), 815834.
 "Efficient algorithms for bichromatic separability," with B. Aronov and V. Koltun, ACM Transactions on Algorithms, 2 (2006), 209227.
 "Extreme Elevation on a 2Manifold,"with H. Edelsbrunner, J. Harer, and Y. Wang, Discrete & Computational Geometry, 36 (2006), 553572.
 "Approximating extent measures of points," with S. HarPeled and K.R. Varadarajan, Journal of the ACM, 51 (2004), 606635.
 "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), 408422.
 "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), 8395.
 I/Oefficient batched unionfind and its applications to terrain analysis, Workshop on Data Structures, Dagstuhl, Germany, 2006.
 Kinetic algorithms: approximation and tradeoffs, 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.
 "Outoforder 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 proteinprotein 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), 455465.
 "Approximation algorithms for kline center," with C. M. Procopiuc and K. R. Varadarajan, Algorithmica, 42 (2005), 221230.
 "Approximation algorithms for kline center," with C. M. Procopiuc and K. R. Varadarajan, Algorithmica, 42 (2005), 221230.
 "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 2manifold, Second Joint Meeting of AMS, DMV, ÖMG, Mainz, Germany, 2005.
 "Geometric approximation via coresets," with S. HarPeled 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. 130.
 "I/Oefficient 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 ACMSIAM Symposium on Discrete Algorithms, 2005.
 "Monitoring continuous bandjoin queries over dynamic data," with J. Xie, J. Yang, and H. Yu, in TwentySixth Annual International Symposium on Algorithms and Computation, 2005.
 "Nearlinear time approximation algorithms for curve simplification," with S. HarPeled, N. Mustafa, and Y. Wang, Algorithmica, 42 (2005), 203219.
 "A nearquadratic algorithm for fence design," with R.P. Berretty and A. D. Collins, Discrete & Computational Geometry, 33 (2005), 463481.
 "On lines avoiding unit balls in three dimensions," with B. Aronov, V. Koltun, and M. Sharir, Discrete & Computational Geometry, 34 (2005) 231250.
 "An optimal dynamic interval stabbingmax data structure?", with L. Arge and K. Yi, in Proceedings Sixteenth Annual ACMSIAM Symposium on Discrete Algorithms, 2005, 803812.
 "Pseudoline arrangements: Duality, algorithms, and applications," with M. Sharir, SIAM Journal on Computing, 34 (2005), 526552.
 "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. HarPeled, in Eighteenth Canadian Conference on Computational Geometry, 2005.
20002004
 "Approximating extent measures of points," with S. HarPeled and K.R. Varadarajan, Journal of the ACM, 51 (2004), 606635.
 "Collision detection for deforming necklaces," with L. J. Guibas, A. Nguyen, D. Russel, and L. Zhang, Computational Geometry: Theory & Applications, 28 (2004), 137163.
 "Computing the writhing number of a polygonal knot," with H. Edelsbrunner and Y. Wang, Discrete & Computational Geometry, 32 (2004), 3754.
 "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.
 "kmeans projective clustering," with N. H. Mustafa, in Proceedings TwentyThird Annual Symposium on Principles of Database Systems, 2004.
 "Lenses in arrangements of pseudocircles and their applications," with E. Nevo, J. Pach, R. Pinchasi, M. Sharir, and S. Smorodinsky, Journal of the ACM 51 (2004), 139186.
 "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 nearlinear constantfactor 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 2line center," with C. M. Procopiuc and K. R. Varadarajan, Computational Geometry: Theory and Applications., 26 (2003), 11928.
 "Approximation algorithms for projective clustering," with C. M. Procopiuc, Journal of Algorithms, 46 (2003), 115139.
 "Bkdtree: A dynamic scalable kdtree," with O. Procopiuc, L. Arge, and J. S. Vitter, in Eighth Annual Symposium on Spatial & Temporal Databases, 2003.
 "Cacheoblivious data structures for orthogonal range searching ," with L. Arge, A. Danner, and B. HollandMinkley, in Nineteenth Annual Symposium on Computational Geometry, 2003.
 "CRBtree: 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. HarPeled, 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), 207243.
 "I/OEfficient 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 pseudosegments and of circles," with B. Aronov and M. Sharir, in Discrete and Computational Geometry: The GoodmanPollack Festschrift (B. Aronov, S. Basu, J. Pach, and M. Sharir, eds.), Springer Verlag, Berlin, 2003, pp. 124.
 "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.
 "Boxtrees and Rtrees with nearoptimal query time," with M. de Berg, J. Gudmundsson, M. Hammar, and H. J. Haverkort, Discrete & Computational Geometry, 28 (2002), 291312.
 "Computing approximate shortest paths on convex polytopes," with S. HarPeled and M. Karia, Algorithmica, 33 (2002), 227242.
 "Curvatureconstrained shortest paths in a convex polygon," with T. Biedl, S. Lazard, S. Robbins, S. Suri, and S. Whitesides, SIAM Journal on Computing, 31 (2002), 18141852.
 "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), 179197.
 "Exact and approximation algorithms for clustering," with C.M. Procopiuc, Algorithmica, 33 (2002), 201226.
 "Kinetic medians and kdtrees," 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), 123150.
 "Outputsensitive algorithms for uniform partitions of points," with B. Bhattacharya and S. Sen, Algorithmica, 32 (2002), 521539.
 "Polygon decomposition for efficient construction of Minkowski sums," with E. Flato and D. Halperin, Computational Geometry: Theory & Applications, 21 (2002), 2138.
 "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. HarPeled, M. Overmars, M. Sharir, and J. Vahrenhold, Computational Geometry: Theory & Applications, 23 (2002), 195208.
 "STARtree: An efficent selfadjusting index for moving points," with C. M. Procopiuc and S. HarPeled, 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 curvatureconstrained shortest paths," with H. Wang, SIAM Journal on Computing, 30 (2001), 17391772.
 "Approximating shortest paths on a nonconvex polyhedron," with K. Varadarajan, SIAM Journal on Computing 30 (2001), 13211340.
 "Exact and approximation algorithms for minimumwidth cylindrical shells," with B. Aronov and M. Sharir, Discrete & Computational Geometry, 26 (2001), 307320.
 "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 TwentyEighth Internatioanl Conference on Automata, Languages, and Programming, 2001.
 "Maintaining approximate extent measures of moving points," with S. HarPeled, in Twelfth ACMSIAM 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), 353374.
 "Minimal trap design," with A. D. Collins and J. Harer, in IEEE Conference on Robotics and Automation, 2001.
 "An online occlusioculling algorithm for fast walkthrough in urban areas," with S. HarPeled 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 ACMSIAM Symposium on Discrete Algorithms, 2000.
 "Approximation and exact algorithms for minimumwidth annuli and shells," with B. Aronov, S. HarPeled and M. Sharir, Discrete & Computational Geometry, 24 (2000), 687705.
 "Binary space partitions for fat rectangles," with E. Grove, T.M. Murali, and J.S. Vitter, SIAM Journal on Computing, 29 (2000), 14221448.
 "Cylindrical static and kinetic binary space partitions," with L. Guibas, T.M. Murali, and J.S. Vitter, Computational Geometry: Theory & Applications 16 (2000), 103127.
 "Efficient algorithms for approximating polygonal chains," with K. R. Varadarajan, Discrete & Computional Geometry, 23 (2000), 273291.
 "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), 194216.
 "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), 721733.
 "Penetration depth of two convex polytopes in 3D," with L. J. Guibas, S. HarPeled, A. Rabinovitch, and M. Sharir, Nordic Journal of Computing, 7 (2000), 227240.
 "Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions," with M. Sharir, Discrete & Computational Geometry, 24 (2000), 645685.
 "Vertical decomposition of shallow levels in 3dimensional arrangements and its applications," with A. Efrat and M. Sharir, SIAM Journal on Computing 29 (2000), 912953.
19952000
 "Approximation algorithms for bipartite and nonbipartite matchings in the plane," with K. R. Varadarajan, in Proceedings Tenth ACMSIAM 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 ACMSIAM 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), 373388.
 "Motion planning of a ball amid segments in three dimensions," with M. Sharir, in Tenth ACMSIAM 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), 201221.
 "Computing many faces in arrangements of lines and segments," with J. Matousek and O. Schwarzkopf, SIAM Journal on Computing, 27 (1998), 491505.
 "Constructing levels in arrangements and higher order Voronoi diagrams," with M. de Berg, J. Matousek, and O. Schwarzkopf, SIAM Journal on Computing 27 (1998), 654667.
 "The discrete 2center problem," with M. Sharir and E. Welzl, Discrete & Computational Geometry, 20 (1998), 287306.
 "I/OEfficient algorithms for contour line extraction and planar graph blocking," with L. Arge, T.M. Murali, K. Varadarajan, and J.S. Vitter, in Ninth ACMSIAM Symposium on Discrete Algorithms (1998), 117126.
 "Kinetic binary space partitions for intersecting segments and disjoint triangles," with J. Erickson and L. Guibas, in Ninth ACMSIAM Symposium on Discrete Algorithms, 1998.
 "Kinetic binary space partitions for intersecting segments and disjoint triangles," with J. Erickson and L. Guibas, in Ninth ACMSIAM 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), 209218.
 "On levels in arrangements of lines, segments, planes, and triangles," with B. Aronov, T.M. Chan, and M. Sharir, Discrete & Computational Geometry, 19 (1998), 315331.
 "Parametric and kinetic minimum spanning trees," with D. Eppstein, L.J. Guibas, and M. Henzinger, in ThirtyNinth Annual Symposium on Foundations of Computer Science, 1998.
 "Surface approximation and geometric partitions," with S. Suri, SIAM Journal on Computing 27 (1998), 10161035.
 "Approximating shortest paths on a convex polytope in three dimensions," with S. HarPeled, M. Sharir, and K. Varadarajan, Journal of the ACM, 44 (1997), 567584.
 "Computing envelopes in four dimensions with applications," with B. Aronov and M. Sharir, SIAM Journal on Computing, 26 (1997), 17141732.
 "An efficient algorithm for terrain simplification," with P. K. Desikan, in Eighth ACMSIAM Symposium on Discrete Algorithms, 1997.
 "Linear approximation of simple objects," with K. Varadarajan, Information Processing Letters, 62 (1997), 8994.
 "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, 382384.
 "Quasiplanar graphs have a linear number of edges," with B. Aronov, J. Pach, R. Pollack, and M. Sharir, Combinatorica, 17 (1997), 19.
 "Star unfolding of a polytope with applications," with B. Aronov, J. O’Rourke, and C. Schevon, SIAM Journal on Computing, 26 (1997), 16891713.
 "Efficient generation of kdirectional assembly sequences," with M. de Berg, D. Halperin, and M. Sharir, in Seventh ACMSIAM Sympsium on Discrete Algorithms, 1996.
 "Efficient randomized algorithms for some geometric optimization problems," with M. Sharir, Discrete & Computational Geometry, 16 (1996), 317337
 "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), 113.
 "Connected component and simple polygon intersection searching," with M. van Kreveld, Algorithmica, 15 (1996), 626660.
 "Ray shooting amidst convex polygons in 2D," with M. Sharir, Journal of Algorithms, 21 (1996), 508519.
 "Ray shooting amidst convex polyhedra and polyhedral terrains in three dimensions," with M. Sharir, SIAM Journal of Computing, 25 (1996), 100116.
 "Selection in monotone matrices and computing kth nearest neighbors," with S. Sen, Journal of Algorithms, 20 (1996), 581601.
 "Simplification envelopes," with J. Cohen, A. Varshney, D. Manocha, G. Turk, F. Brooks, H. Weber, and W. Wright, in SIGGRAPH, 1996, 119128.
 "Computing depth orders for fat objects and related problems," with M. Katz and M. Sharir, Computational Geometry Theory & Applications., 5 (1995), 187206.
 "Dynamic halfspace range reporting and its applications," with J. Matousek, Algorithmica, 13 (1995), 325345.
 "Line stabbing bounds in three dimensions," with B. Aronov and S. Suri, in Eleventh Annual Symposium on Computational Geometry, 1995.
 "Motion planning for a steeringconstrained robot through moderate obstacles," with P. Raghavan and H. Tamaki, in TwentySeventh ACM Symposium on Theory of Computing, 1995.
19901994
 "Applications of parametric searching in geometric optimization," with M. Sharir and S. Toledo, Journal of Algorithms, 17 (1994), 292318.
 "Can visibility graphs be represented compactly?" with N. Alon, B. Aronov, and S. Suri, Discrete & Computational Geometry, 12 (1994), 347365.
 "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), 369383.
 "On the number of views of polyhedral terrains," with M. Sharir, Discrete & Computational Geometry, 12 (1994), 177182.
 "On range searching with semialgebraic sets," with J. Matousek, Discrete & Computational Geometry, 11 (1994), 393418.
 "On stabbing lines for convex polyhedra in 3D," Computational Geometry: Theory & Applications, 4 (1994), 177189.
 "Planar geometric location problems," with M. Sharir, Algorithmica, 11 (1994), 185195.
 "Applications of a new space partitioning technique," with M. Sharir, Discrete & Computational Geometry, 9 (1993), 1138.
 "Circle shooting in a simple polygon," with M. Sharir, Journal of Algorithms 14 (1993), 6887.
 "Circular visibility of a simple polygon from a fixed point," with M. Sharir, International Journal of Computational Geometry and Applications, 3 (1993), 125.
 "Computing a segment center for a planar point set," with A. Efrat, M. Sharir, and S. Toledo, Journal of Algorithms, 15 (1993), 314323.
 "Counting circular arc intersections," with M. Pellegrini and M. Sharir, SIAM Journal on Computing, 22 (1993), 778793.
 "Intersection queries in curved objects," with M. van Kreveld and M. Overmars, Journal of Algorithms 15 (1993), 229266.
 "Ray shooting and parametric search," SIAM Journal on Computing 22 (1993), 794806.
 "Selecting distances in the plane," with B. Aronov, M. Sharir, and S. Suri, Algorithmica, 9 (1993), 495514.
 "Counting facets and incidences," with B. Aronov, Discrete & Computational Geometry, 7 (1992), 359369.
 "Farthest neighbors, maximum spanning trees and related problems in higher dimensions," with J. Matousek and S. Suri, Computational Geometry: Theory & Applications, 1 (1992), 189201.

"Intersection queries in sets of discs," with M. van Kreveld and M. Overmars, BIT 32 (1992), 268279.
 "Oriented aligned rectangle packing problem," with M. T. Shing, European Journal of Operational Research, 62 (1992), 210220.
 "Ray shooting and other applications of spanning trees with low stabbing number," SIAM Journal on Computing 21 (1992), 540570.
 "Relative neighborhood graphs in three dimensions," with J. Matousek, Computational Geometry: Theory & Applications., 2 (1992), 115.
 "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), 97111.
 "Euclidean minimum spanning tree and bichromatic closest pairs," with H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, Discrete & Computational Geometry 6 (1991), 407422.
 "Offline dynamic maintenance of the width of a planar point set," with M. Sharir, Computational Geometry: Theory & Applications, 1 (1991), 6578.
 "Algorithms for special cases of rectilinear Steiner trees: I. Points on the boundary of a rectangle," with M. T. Shing, Networks, 20 (1990), 453485.
 "Partitioning arrangements of lines: I. An efficient deterministic algorithm," Discrete & Computational Geometry, 5 (1990), 449483.
 "Partitioning arrangements of lines: II. Applications," Discrete & Computational Geometry, 5 (1990), 533573.
 "Redblue intersection detection algorithms, with applications to motion planning and collision detection," with M. Sharir, SIAM Journal on Computing, 19 (1990), 297322.
19851989
 "Sharp upper and lower bounds on the length of general DavenportSchinzel sequences," with M. Sharir and P. Shor, Journal of Combinatorial Theory, Series A, 52 (1989), 228274.
 "KBGISII: A knowledgebased geographic information system," with T. Smith, D. Peuquet, and S. Menon, International Journal of Geographic Information Systems, 1 (1987), 149172.