Publications: Papers

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

Shape Analysis

"Computing a segment-center for a planar point set," with A. Efrat, M. Sharir, and S. Toledo, J. Algorithms, 15 (1993), 314-323.
"Approximation algorithms for bipartite and nonbipartite matchings in the plane," with K. R. Varadarajan, in 10th ACM-SIAM Symp. Discrete Algorithms, 1999.
"Approximation algorithms for layered manufacturing," with P. K. Desikan, in 11th ACM-SIAM Symp. Discrete Algorithms, 2000.
"Approximation and exact algorithms for minimum-width annuli and shells," with B. Aronov, S. Har-Peled and M. Sharir, Discrete Comput. Geom., 24 (2000), 687-705.
"Exact and approximation algorithms for minimum-width cylindrical shells," with B. Aronov and M. Sharir, Discrete Comput. Geom., 26 (2001), 307-320.
"On the numbers of congruent simplices in a point set," with M. Sharir, Discrete Comput. Geom., 28 (2002), 123-150.
"Hausdorff distance under translation for points, and balls," with S. Har-Peled, M. Sharir, and Y. Wang, in 17th Annual Symp. Comput. Geom. 2003.
"Streaming geometric optimization using graphics hardware," with Krishnan, N. H. Mustafa, and S. Venkatasubramanian, in 11th Annual European Symp. Algorithms, 2003.
"Approximating extent measures of points," with S. Har-Peled and K.R. Varadarajan, J. ACM, 51 (2004), 606-635.
"Computing the writhing number of a polygonal knot, with H. Edelsbrunner and Y.Wang, Discrete Comp. Geom., 32 (2004), 37-54.
"A near-linear constant-factor approximation for Euclidean bipartite matching, with K. R. Varadarajan, in 20th Annual Symp. on Comput. Geom., 2004.
"Near-linear time approximation algorithms for curve simplification," with S. Har-Peled, N. Mustafa, and Y. Wang, Algorithmica, 42 (2005), 203-219
"Approximating extent measures of points," with S. Har-Peled and K.R. Varadarajan, J. ACM, 51 (2004), 606-635.
"On bipartite matching under the rms distance," with J. Phillips, in 17th Canadian Conf. Comput. Geom., 2006.
"A space-optimal data-stream algorithm for coresets in the plane," with H. Yu, in 23rd Annual Symp. Comput. Geom., 2007.
"On polyhedra induced by point sets in space," with F. Hurtado, G. T. Toussaint, and J. Trias, Discrete Applied Mathematics, 156 (2008), 42-54.
"Practical methods for shape fitting and kinetic data structures using coresets," with R. Poreddy, K. Varadarajan, and H. Yu, Algorithmica, 52 (2008), 378-402.
"Robust shape fitting via peeling and grating coresets," with S. Har-Peled and H. Yu, Discrete Comput. Geom. 39 (2008), 38-58.
"The 2-center problem in three dimensions," with R. Ben Avraham and M. Sharir, in 26th Annual Symp. Comput. Geom., 2010.
"An improved algorithm for computing the volume of the union of cubes ," in 26th Annual Symp. Comput. Geom., 2010.

top

Clustering and Classification

"Applications of parametric searching in geometric optimization," with M. Sharir and S. Toledo, J. Algorithms, 17 (1994), 292-318.
"Planar geometric location problems," with M. Sharir, Algorithmica, 11 (1994), 185-195.
"Extreme Elevation on a 2-Manifold,"with H. Edelsbrunner, J. Harer, and Y. Wang, Discrete Comput. Geom., 36 (2006), 553-572.
"Linear approximation of convex objects," with K. Varadarajan, Inform. Process. Letts., 62 (1997), 89-94.
"The discrete 2-center problem," with M. Sharir and E. Welzl, Discrete Comput. Geom., 20 (1998), 287-306.
"Exact and approximation algorithms for clustering," with C.M. Procopiuc, Algorithmica, 33 (2002), 201-226.
"A Monte Carlo algorithm for fast projective clustering," with C. M. Procopiuc, M. Jones, and T.M. Murali, in ACM SIGMOD Intl. Conf. Management Data, 2002.
"Output-sensitive algorithms for uniform partitions of points," with B. Bhattacharya and S. Sen, Algorithmica, 32 (2002), 521-539.
"A (1 + ε)-approximation algorithm for computing the two-line center," with C. M. Procopiuc and K. R. Varadarajan, Comput. Geom.: Theory and Appls., 26 (2003), 119-28.
"Approximation algorithms for projective clustering," with C. M. Procopiuc, J. Algorithms, 46 (2003), 115-139.
"k-means projective clustering," with N. H. Mustafa, in 23rd Annual Sympos. Principles of Database Systems, 2004.
"Approximation algorithms for k-line center," with C. M. Procopiuc and K. R. Varadarajan, Algorithmica, 42 (2005), 221-230.
"Computing maximally separated sets in the plane," with M. Overmars and M. Sharir, in SIAM J. Comput., 36 (2006), 815-834.
"Efficient algorithms for bichromatic separability," with B. Aronov and V. Koltun, ACM Transactions on Algorithms, 2 (2006), 209-227.
"An efficient algorithm for Euclidean 2-center with outliers," with J. Phillips, in 16th European Symp. Algorithms, 2008.
"Stabbing convex polygons with a segment or a polygon," with D. Chen, S. Ganjugunte, E. Misiolek, M. Sharir, and K. Tang, in 16th European Symp. Algorithms, 2008.
"Near-linear approximation algorithms for geometric hitting sets," with E. Ezra and M. Sharir, to appear in Algorithmica.

top

Proximity

"Algorithms for special cases of rectilinear Steiner trees: I. Points on the boundary of a rectangle," with M. T. Shing, Networks, 20 (1990), 453-485.
"Computing all external-farthest neighbors for a simple polygon," with A. Aggarwal, B. Aronov, S. Kosaraju, B. Shieber, and S. Suri, Discrete and Applied Math, 31 (1991), 97-111.
"Euclidean minimum spanning tree and bichromatic closest pairs," with H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, Discrete Comp. Geom. 6 (1991), 407-422.
"Off-line dynamic maintenance of the width of a planar point set," with M. Sharir, Comput. Geom.: Theory & Appls., 1 (1991), 65-78.
"Farthest neighbors, maximum spanning trees and related problems in higher dimensions," with J. Matousek and S. Suri, Comput. Geom.: Theory & Appls, 1 (1992), 189-201.
"Oriented aligned rectangle packing problem," with M. T. Shing, European J. Operations Research, 62 (1992), 210-220.
"Relative neighborhood graphs in three dimensions," with J. Matousek, Comput. Geom.: Theory & Appls., 2 (1992), 1-15
"Selecting distances in the plane," with B. Aronov, M. Sharir, and S. Suri, Algorithmica, 9 (1993), 495-514.
"Selection in monotone matrices and kth nearest neighbors," with S. Sen, J. Algorithms, 20 (1996), 581-601.
"Translating a planar object to maximize point containment," with T. Hagerup, R. Ray, M. Sharir, M. Smid, and E. Welzl, in 10th Annual European Symp. Algorithms, 2002.
"I/O-efficient construction of constrained Delaunay triangulations," with L. Arge and K. Yi, in 13th European Symp. Algorithms, 2005.
"Lower bound for sparse Euclidean spanners," with Y. Wang and P.Yin, in 16th Annual ACM-SIAM Symp. Discrete Algorithms, 2005.
"Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D," with R. Klein, C. Knauer, S. Langerman, P. Morin, M. Sharir, and M. Soss, in Discrete Comput. Geom., 39 (2008), 17-37.
"Computing a center-transversal line," with S. Cabello, J.A. Sellarès, and M. Sharir, to appear in Intl. J. Comp. Geom. & Appls.

top

Kinetic Algorithms

"Kinetic binary space partitions for intersecting segments and disjoint triangles," with J. Erickson and L. Guibas, in 9th ACM-SIAM Symp. Discrete Algorithms, 1998.
"Parametric and kinetic minimum spanning trees," with D. Eppstein, L.J. Guibas, and M. Henzinger, in 39th Annual Symp. Foundations Computer Science, 1998.
"Cylindrical static and kinetic binary space partitions," with L. Guibas, T.M. Murali, and J.S. Vitter, Comput. Geom: Theory & Appls. 16 (2000), 103-127.
"Indexing moving points," with L. Arge and J. Erickson, in 19th ACM Symp. on Principles of Database Systems, 2000.
"Lower bounds for kinetic planar subdivisions," with J. Basch, M. de Berg, L. J. Guibas, and J. Hershberger, Discrete Comput. Geom., 24 (2000), 721-733.
"Maintaining approximate extent measures of moving points," with S. Har-Peled, in 12th ACM-SIAM Symp. Discrete Algorithms,, 2001.
"Maintaining the extent of a moving point set," with L. Guibas, J. Hershberger, and E. Veach, Discrete Comput. Geom., 26 (2001), 353-374.
"Time responsive external data structures for moving points," with L. Arge and J. Vahrenhold, in 7th Workshop on Algorithms and Data Structures, 2001.
"Deformable free space tiling for kinetic collision detection," with J. Basch, L. J. Guibas, J. Hershberger, and L. Zhang, Intl. J. Robotics Research, 21 (2002), 179-197.
"Kinetic medians and kd-trees," with J. Gao and L. J. Guibas, in 10th European Symp. Algorithms, 2002.
"STAR-tree: An efficent self-adjusting index for moving points," with C. M. Procopiuc and S. Har-Peled, in 4th Workshop on Algorithms Engineering and Experiments, 2002.
"Collision detection for deforming necklaces," with L. J. Guibas, A. Nguyen, D. Russel, and L. Zhang, Comput. Geom.: Theory & Appls, 28 (2004), 137-163.
"Efficient tradeoff schemes in data structures for querying," with L. Arge, J. Erickson, and H. Yu, in 12th European Symp. Algorithms, 2004.
"Staying in the middle: Exact and approximate medians in R¹ and R² for moving points," with M. de Berg, J. Gao, L. Guibas, and S. Har-Peled, in 18th Canadian Conf. Comput. Geom., 2005.
"A 2D kinetic tiangulation with near-quadratic topological changes," with Y. Wang and H. Yu, Discrete Comput. Geom., 36 (2006), 573-592.
"Out-of-order event processing in kinetic data structures," with M. A. Abam, M. de Berg, and H. Yu, in 14th European Symp. Algorithms, 2006.
"Embeddings of surfaces, curves, and moving points in Euclidean space," with S. Har-Peled and H. Yu, in 23rd Annual Symp. Comput. Geom., 2007.
"Kinetic and dynamic data structures for closest pairs and all nearest neighbors," with H. Kaplan and M. Sharir, in ACM Transactions on Algorithms 5, 1 (2008), Article 4, (37 pp.).
"On approximate geodesic-distance queries amid deforming point clouds," with A. Efrat, R. Sharathkumar, and H. Yu, in 8th Workshop on Algorithmic Foundations of Robotics, 2008.
"Practical methods for shape fitting and kinetic data structures using coresets," with R. Poreddy, K. Varadarajan, and H. Yu, Algorithmica, 52 (2008), 378-402.
"Untangling triangulations through local explorations," with B. Sadri and H. Yu, in 24th Annual Symp. Comput. Geom., 2008.
"Kinetic stable Delaunay graphs," with J. Gao, L. Guibas, H. Kaplan, V. Koltun, N. Rubin, and M. Sharir, in 26th Annual Symp. Comput. Geom., 2010.
"Embeddings of surfaces, curves, and moving points in Euclidean space," with S. Har-Peled and H. Yu, submitted to SIAM J. Comput.

top

Computational Molecular Biology

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

top

GIS and Terrain Modeling

"KBGIS-II: A knowledge-based geographic information system," with T. Smith, D. Peuquet, and S. Menon, Intl. J. GIS, 1 (1987), 149-172.
"Polygon and connected component intersection searching," with M. van Kreveld, Algorithmica, 15 (1996), 626-660.
"Approximating shortest paths on a convex polytope in three dimensions," with S. Har-Peled, M. Sharir, and K. Varadarajan, J. ACM, 44 (1997), 567-584.
"An efficient algorithm for terrain simplification," with P. K. Desikan, in 8th ACM-SIAM Symp. Discrete Algorithms, 1997.
"I/O-Efficient algorithms for contour line extraction and planar graph blocking," with L. Arge, T.M. Murali, K. Varadarajan, and J.S. Vitter, in 9th ACM-SIAM Symp. Discrete Algorithms, 1998.
"Label placement by maximum independent set in rectangles," with M. van Kreveld and S. Suri, Comput. Geom.: Theory & Appls., 11 (1998), 209-218.
"Efficient algorithms for approximating polygonal chains," with K. R. Varadarajan, Discrete Comput. Geom., 23 (2000), 273-291.
"A simple and efficient algorithm for high quality line labeling," with L. Knipping, M. van Kreveld, T. Strijk, and A. Wolff, in Innovations in GIS VII: GeoComputation, (P. M. Atkinson and D. Martin, eds.), Taylor and Francis, London, 2000, pp. 147-159.
"Approximating shortest paths on a nonconvex polyhedron," with K. Varadarajan, SIAM J. Comput. 30 (2001), 1321-1340.
"Computing approximate shortest paths on convex polytopes," with S. Har-Peled and M. Karia, Algorithmica, 33 (2002), 227-242.
"Reporting intersecting pairs of polytopes in two and three dimensions," with M. de Berg, S. Har-Peled, M. Overmars, M. Sharir, and J. Vahrenhold, Comput. Geom: Theory & Appls., 23 (2002), 195-208.
"I/O-efficient construction of constrained Delaunay triangulations," with L. Arge and K. Yi, in 13th European Symp. Algorithms, 2005.
"Near-linear time approximation algorithms for curve simplification," with S. Har-Peled, N. Mustafa, and Y. Wang, Algorithmica, 42 (2005), 203-219
"From point cloud to grid DEM: A scalable approach," with A. Danner and L. Arge, in 12th Intl. Symp. Spatial Data Handling, 2006.
"A scalable algorithm for dispersing population," with S. Govindrajan, M. Dietze, and J. Clark, Journal of Intelligent Information Systems, 29 (2007), 39-61.
"TerraStream: From elevation data to watershed hierarchies," with A. Danner, K. Yi, T. MÃ¸lhave, L. Arge, H. Mitasova, in Proc. 15th ACM Symp. Advances in GIS, 2007.
"I/O efficient algorithms for computing contour lines on a terrain" with L. Arge, T. Mølhave, and B. Sadri, in 24th Annual Symp. Comput. Geom., 2008.
"Computing similarity between piecewise-linear functions," with B. Aronov, M. van Kreveld, M. Löffler, and R. I. Silveira, in 26th Annual Symp. Comput. Geom., 2010.
"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.).
"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 contour queries on terrains," with T. Mølhave and B. Sadri, in Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011.
"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.
"Lipschitz unimodel and isotonic regression on paths and trees," with J. Phillips and B. Sadri, in Ninth Annual Latin American Theoretical Informatics Symposium, 2010.

top

Ecological Modeling

"The extinction debt revisited: Population dynamics in a continuous space model," with M. Dietze, S. Govindarajan, and J. Clark, in Ecological Society of America Annual Meeting, 2001.
"The paradox of species diversity," with J. Clark, M. Dietze, and S. Govindarajan, in Ecological Society of America Annual Meeting, 2003.
"A scalable simulator for forest dynamics," with S. Govindrajan, M. Dietze, and J. Clark, in 20th Annual Symp. Comput. Geom., 2004.
"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.
"Exploiting temporal coherence in forest dynamics simulation," with T. Mølhave, H. Yu, and J. Clark, in 27th Annual Symp. Comput. Geom., 2011.
"Inferential ecosystem models, from network data to prediction," with J. S. Clark, D. M. Bell , P. Flikkema, A. Gelfand, X. Nguyen, E. Ward, and J. Yang, Ecological Applications, 2010, in press.

top

Robotics

"Red-blue intersection detection algorithms, with applications to motion planning and collision detection," with M. Sharir, SIAM J. Comput., 19 (1990), 297-322.
"Motion planning for a steering-constrained robot through moderate obstacles," with P. Raghavan and H. Tamaki, in 27th ACM Symp. Theory Comput., 1995.
"Efficient generation of k-directional assembly sequences," with M. de Berg, D. Halperin, and M. Sharir, in 7th ACM-SIAM Symp. Discrete Algorithms, 1996.
"Largest placements and motion planning of a convex polygon," with N. Amenta, B. Aronov, and M. Sharir, in 2nd International Workshop on Algorithmic Foundation of Robotics, 1996.
"Nonholonomic path planning for pushing a disk among obstacles," with J.-C. Latombe, R. Motwani, and P. Raghavan, in IEEE Conf. on Robotics and Automation, 1997.
"Star unfolding of a polytope with applications," with B. Aronov, J. O’Rourke, and C. Schevon, SIAM J. Comput., 26 (1997), 1689-1713.
"Motion planning of a ball amid segments in three dimensions," with M. Sharir, in 10th ACM-SIAM Symp. Discrete Algorithms, 1999.
"Motion planning for a convex polygon in a polygonal environment," with B. Aronov and M. Sharir, Discrete Comput. Geom., 22 (1999), 201-221.
"Penetration depth of two convex polytopes in 3D," with L. J. Guibas, S. Har-Peled, A. Rabinovitch, and M. Sharir, Nordic J. Computing, 7 (2000), 227-240.
"Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions," with M. Sharir, Discrete Comput. Geom., 24 (2000), 645-685.
"Approximation algorithms for curvature-constrained shortest paths," with H. Wang, SIAM J. Comput., 30 (2001), 1739-1772.
"Minimal trap design," with A. D. Collins and J. Harer, in IEEE Conference on Robotics and Automation, 2001.
"Curvature-constrained shortest paths in a convex polygon," with T. Biedl, S. Lazard, S. Robbins, S. Suri, and S. Whitesides, SIAM J. Comput., 31 (2002), 1814-1852.
"Deformable free space tiling for kinetic collision detection," with J. Basch, L. J. Guibas, J. Hershberger, and L. Zhang, Intl. J. Robotics Research, 21 (2002), 179-197.
"Polygon decomposition for efficient construction of Minkowski sums," with E. Flato and D. Halperin, Comput. Geom.: Theory & Appls., 21 (2002), 21-38.
"HPRM: A hierarchical PRM," with A. D. Collins and J. Harer in Proc. Intl Conf. Robotics and Automation , 2003.
"A near-quadratic algorithm for fence design," with R.-P. Berretty and A. D. Collins, Discrete Comput. Geom., 33 (2005), 463-481.
"On approximate geodesic-distance queries amid deforming point clouds," with A. Efrat, R. Sharathkumar, and H. Yu, in 8th Workshop on Algorithmic Foundations of Robotics, 2008.
"Approximate Euclidean shortest paths amid convex obstacles," with R. Sharathkumar and H. Yu, in 20th ACM-SIAM Symp. Discrete Algorithms, 2009.

top

Geometric Data Structures

"Intersection queries in sets of discs," with M. van Kreveld and M. Overmars, BIT 32 (1992), 268-279.
"Ray shooting and other applications of spanning trees with low stabbing number," SIAM J. Comput. 21 (1992), 540-570.
"Circle shooting in a simple polygon," with M. Sharir, J. Algorithms 14 (1993), 68-87.
"Intersection queries in curved objects," with M. van Kreveld and M. Overmars, J. Algorithms 15 (1993), 229-266.
"Ray shooting and parametric search," SIAM J. Comput. 22 (1993), 794-806.
"On range searching with semialgebraic sets," with J. Matousek, Discrete Comput. Geom., 11 (1994), 393-418.
"Dynamic half-space range reporting and its applications," with J. Matousek, Algorithmica, 13 (1995), 325-345.
"Polygon and connected component intersection searching," with M. van Kreveld, Algorithmica, 15 (1996), 626-660.
"Ray shooting amidst convex polyhedra and polyhedral terrains in three dimensions," with M. Sharir, SIAM J. Comput., 25 (1996), 100-116.
"Ray shooting amidst convex polygons in 2D," with M. Sharir, J. Algorithms, 21 (1996), 508-519.
"Parametric and kinetic minimum spanning trees," with D. Eppstein, L.J. Guibas, and M. Henzinger, in 39th Annual Symp. Foundations Computer Science, 1998.
"I/O efficient dynamic point location in monotone planar subdivisions," with L. Arge, G. S. Brodal, and J. S. Vitter, in 10th ACM-SIAM Symp. Discrete Algorithms, 1999.
"Efficient searching with linear constraints," with L. Arge, J. Erickson, P. G. Franciosa, and J. S. Vitter, J. Computer and Systems Sciences, 61 (2000), 194-216.
"A framework for index bulk loading and dynamization," with L. Arge, O. Procopiuc, and J. S. Vitter, in 28th Intl. Conf. on Automata, Languages, and Programming, 2001.
"Box-trees and R-trees with near-optimal query time," with M. de Berg, J. Gudmundsson, M. Hammar, and H. J. Haverkort, Discrete Comput. Geom., 28 (2002), 291-312.
"Kinetic medians and kd-trees," with J. Gao and L. J. Guibas, in 10th European Symp. Algorithms, 2002.
"Range searching in categorical data: Colored range searching on grid," with S. Govindarajan and S. Muthukrishnan, in 10th European Symp. Algorithms, 2002.
"STAR-tree: An efficent self-adjusting index for moving points," with C. M. Procopiuc and S. Har-Peled, in 4th Workshop on Algorithms Engineering and Experiments, 2002.
"Bkd-tree: A dynamic scalable kd-tree," with O. Procopiuc, L. Arge, and J. S. Vitter, in 8th Annual Symp. Spatial Temporal Databases, 2003.
"Cache-oblivious data structures for orthogonal range searching ," with L. Arge, A. Danner, and B. Holland-Minkley, in 19th Annual Symp. Comput. Geom., 2003.
"CRB-tree: An efficient indexing scheme for range aggregate queries," with S. Govindarajan and L. Arge, in 9th Intl. Conf. Database Theory, 2003.
"Indexing moving points," with L. Arge and J. Erickson, Journal of Computer and Systems Sciences, 66 (2003), 207-243.
"I/O-Efficient structures for orthogonal range max and stabbing max queries," with L. Arge, J. Yang, and K. Yi, in 11th European Sympos. Algorithms, 2003.
"Collision detection for deforming necklaces," with L. J. Guibas, A. Nguyen, D. Russel, and L. Zhang, Comput. Geom.: Theory & Appls, 28 (2004), 137-163.
"Monitoring continuous band-join queries over dynamic data," with J. Xie, J. Yang, and H. Yu, in 26th Annual Intl. Symp. Algorithms and Computation, 2005.
"An optimal dynamic interval stabbing-max data structure?" with L. Arge and K. Yi, to appear in 16th Annual ACM-SIAM Symp. Discrete Algorithms, 2005.
"Scalable continuous query processing by tracking hotspots," with J. Xie, J. Yang, and H. Yu, in Annual IEEE Intl. Conf. Very Large Databases 2006.
"Kinetic and dynamic data structures for closest pairs and all nearest neighbors," with H. Kaplan and M. Sharir, in ACM Transactions on Algorithms 5, 1 (2008), Article 4, (37 pp.).
"ProSem: Scalable wide-area publish/subscribe," with B. Chandramouli, J. Yang, A. Yu, and Y. Zhang, in ACM SIGMOD Intl. Conf. Management Data, 2008.
"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.).
"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.
"An optimal dynamic data structure for stabbing-semigroup queries," with L. Arge, H. Kaplan, E. Molad, R. E. Tarjan, K. Yi, to appear in SIAM Journal on Computing.
"Range searching on uncertain data," with S.-W. Cheng, Y. Tao, and K. Yi, to appear in ACM Transactions on Algorithms.
"Efficient external memory structures for range-aggregate queries," with L. Arge, S. Govindrajan, J. Yang, and K. Yi, submitted to Comput. Geom.: Theory & Appls.

top

Arrangements

"Partitioning arrangements of lines: I. An efficient deterministic algorithm," Discrete Comput. Geom., 5 (1990), 449-483.
"Partitioning arrangements of lines: II. Applications," Discrete Comput. Geom., 5 (1990), 533-573.
"Counting facets and incidences," with B. Aronov, Discrete Comp. Geom., 7 (1992), 359-369.
"Applications of a new space partitioning technique," with M. Sharir, Discrete Comput. Geom., 9 (1993), 11-38.
"Counting circular arc intersections," with M. Pellegrini and M. Sharir, SIAM J. Comput., 22 (1993), 778-793.
"Implicit point location in arrangement segments with application to motion planning," with M. van Kreveld, Intl. J. Comput. Geom. & Appls., 4 (1994), 369-383.
"The overlay of lower envelopes and its applications," with O. Schwarzkopf and M. Sharir, Discrete Comput. Geom., 15 (1996), 1-13.
"Computing envelopes in four dimensions with applications," with B. Aronov and M. Sharir, SIAM J. Comput., 26 (1997), 1714-1732.
"Computing many faces in arrangements of lines and segments," with J. Matousek and O. Schwarzkopf, SIAM J. Comput., 27 (1998), 491-505.
"Constructing levels in arrangements and higher order Voronoi diagrams," with M. de Berg, J. Matousek, and O. Schwarzkopf, SIAM J. Comput. 27 (1998), 654-667.
"On levels in arrangements of lines, segments, planes, and triangles," with B. Aronov, T.M. Chan, and M. Sharir, Discrete Comput. Geom., 19 (1998), 315-331.
"Line transversals of balls and smallest enclosing cylinders in three dimensions," with B. Aronov and M. Sharir, Discrete Comput. Geom. 21 (1999), 373-388.
"Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions," with M. Sharir, Discrete Comput. Geom., 24 (2000), 645-685.
"Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications," with A. Efrat and M. Sharir, SIAM J. Comput. 29 (2000), 912-953.
"On the complexity of many faces in arrangements of pseudo-segments and of circles," with B. Aronov and M. Sharir, in Discrete and Computational Geometry: The Goodman-Pollack Festschrift (B. Aronov, S. Basu, J. Pach, and M. Sharir, eds.), Springer Verlag, Berlin, 2003, pp. 1-24.
"Lenses in arrangements of pseudo-circles and their applications," with E. Nevo, J. Pach, R. Pinchasi, M. Sharir, and S. Smorodinsky, J. ACM 51 (2004), 139-186.
"Pseudo-line arrangements: Duality, algorithms, and applications," with M. Sharir, SIAM J. Comput., 34 (2005), 526-552.
Independent set of intersection graphs of convex objects in 2D," with N. H. Mustafa, Comput. Geom.: Theory & Appls., 34 (2006), 83-95.
"Computing the volume of the union of cubes," with H. Kaplan and M. Sharir, in 23rd Annual Symp. Comput. Geom., 2007.
"Algorithms for center and Tverberg points," with M. Sharir and E. Welzl, ACM Transactions on Algorithms, 5, 1 (2008), Article 5, (20 pp.).
"Computing a center-transversal line," with S. Cabello, J.A. Sellarès, and M. Sharir, to appear in Intl. J. Comp. Geom. & Appls.

top

Combinatorial Geometry

"Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences," with M. Sharir and P. Shor, J. Combin. Theory, Series A, 52 (1989), 228-274.
"Counting facets and incidences," with B. Aronov, Discrete Comp. Geom., 7 (1992), 359-369.
"Can visibility graphs be represented compactly?" with N. Alon, B. Aronov, and S. Suri, Discrete Comput. Geom., 12 (1994), 347-365.
"On stabbing lines for convex polyhedra in 3D," Comput. Geom.: Theory & Appls., 4 (1994), 177-189.
"Line stabbing bounds in three dimensions," with B. Aronov and S. Suri, in 11th Annual Symp. Comput. Geom., 1995.
"The overlay of lower envelopes and its applications," with O. Schwarzkopf and M. Sharir, Discrete Comput. Geom., 15 (1996), 1-13.
"On levels in arrangements of lines, segments, planes, and triangles," with B. Aronov and M. Sharir, in 13th Annual Symp. Comput. Geom., 1997.
"Quasi-planar graphs have a linear number of edges," with B. Aronov, J. Pach, R. Pollack, and M. Sharir, Combinatorica, 17 (1997), 1-9.
"On the numbers of congruent simplices in a point set," with M. Sharir, Discrete Comput. Geom., 28 (2002), 123-150.
"On the complexity of many faces in arrangements of pseudo-segments and of circles," with B. Aronov and M. Sharir, in Discrete and Computational Geometry: The Goodman-Pollack Festschrift (B. Aronov, S. Basu, J. Pach, and M. Sharir, eds.), Springer Verlag, Berlin, 2003, pp. 1-24.
"Lenses in arrangements of pseudo-circles and their applications," with E. Nevo, J. Pach, R. Pinchasi, M. Sharir, and S. Smorodinsky, J. ACM 51 (2004), 139-186.
"On lines avoiding unit balls in three dimensions," with B. Aronov, V. Koltun, and M. Sharir, Discrete Comput. Geom., 34 (2005) 231-250.
"Similar simplices in a d-dimensional point set," with R. Apfelbaum, G. Purdy, and M. Sharir, in 23rd Annual Symp. Comput. Geom., 2007.

top

Sensor Networks

"Monitoring continuous band-join queries over dynamic data," with J. Xie, J. Yang, and H. Yu, in 26th Annual Intl. Symp. Algorithms and Computation, 2005.
"Model-driven dynamic control of embedded wireless sensor networks," with P. Flikkema, J. Clark, C. Ellis, A. Gelfand, K. Munagala, and J. Yang, in 3rd International Conference on Computational Science, 2006.
"Scalable continuous query processing by tracking hotspots," with J. Xie, J. Yang, and H. Yu, in Annual IEEE Intl. Conf. Very Large Databases 2006.
"Segmenting object space by geometric reference structures," with D. Brady and J. Matousek, ACM Transactions on Sensor Networks, 2 (2006), 455-465.
"Model-driven dynamic control of embedded wireless sensor networks," with P. Flikkema, J. Clark, C. Ellis, A. Gelfand, K. Munagala, and J. Yang, in 3rd Intl. Conf. Comput. Science, 2006.
"Localization using boundary sensors: an analysis based on graph theory," with Y. Zheng and D. J. Brady, in ACM Transactions on Sensor Networks 3 (2007).
"Efficient sensor placement for surveillance problems," with E. Ezra and S. Ganjugunte, in 5th IEEE Intl. Conf. Distributed Comput. Sensor Systems (best paper), 2009.
"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.
"Distributed localization and clustering using data correlation and the Occams razor principle," with A. Efrat, C. Gniady, J.S.B. Mitchell, G. R. Sabhnani, and V. Plishchuk, to appear in 7th IEEE Intl. Conf. Distributed Comput. Sensor Systems, 2011.
"The resilience of WDM networks to probabilistic geographical failures," with A. Efrat, S. Ganjugunte, D. Hay, S. Sankararaman, G. Zussman, in Thiryth International Conference on Computer Communications, 2011.
“On channel-discontinuity-constraint routing in wireless networks” with S. Sankararaman, A. Efrat, and S. Ramasubramanian, to appear in Ad-Hoc Networks.

top

Core Sets

"Approximation algorithms for k-line center," with C. M. Procopiuc and K. R. Varadarajan, Algorithmica, 42 (2005), 221-230.
"Embeddings of surfaces, curves, and moving points in Euclidean space," with S. Har-Peled and H. Yu, in 23rd Annual Symp. Comput. Geom., 2007.
"A space-optimal data-stream algorithm for coresets in the plane," with H. Yu, in 23rd Annual Symp. Comput. Geom., 2007.
"Practical methods for shape fitting and kinetic data structures using coresets," with R. Poreddy, K. Varadarajan, and H. Yu, Algorithmica, 52 (2008), 378-402.
"Robust shape fitting via peeling and grating coresets," with S. Har-Peled and H. Yu, Discrete Comput. Geom. 39 (2008), 38-58.
"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.
"Subscriber assignment for wide-area content-based publish/subscribe," with A. Yu and J. Yang, in International Conference on Data Engineering, 2011.
"Embeddings of surfaces, curves, and moving points in Euclidean space," with S. Har-Peled and H. Yu, submitted to SIAM J. Comput.

top

Computer Graphics and Visualization

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

top

Databases

"Efficient searching with linear constraints," with L. Arge, J. Erickson, P. G. Franciosa, and J. S. Vitter, J. Computer and Systems Sciences, 61 (2000), 194-216.
"A framework for index bulk loading and dynamization," with L. Arge, O. Procopiuc, and J. S. Vitter, in 28th Intl. Conf. on Automata, Languages, and Programming, 2001.
"Bkd-tree: A dynamic scalable kd-tree," with O. Procopiuc, L. Arge, and J. S. Vitter, in 8th Annual Symp. Spatial Temporal Databases, 2003.
"CRB-tree: An efficient indexing scheme for range aggregate queries," with S. Govindarajan and L. Arge, in 9th Intl. Conf. Database Theory, 2003.
"Indexing moving points," with L. Arge and J. Erickson, Journal of Computer and Systems Sciences, 66 (2003), 207-243.
"Monitoring continuous band-join queries over dynamic data," with J. Xie, J. Yang, and H. Yu, in 26th Annual Intl. Symp. Algorithms and Computation, 2005.
"Scalable continuous query processing by tracking hotspots," with J. Xie, J. Yang, and H. Yu, in Annual IEEE Intl. Conf. Very Large Databases 2006.
"ProSem: Scalable wide-area publish/subscribe," with B. Chandramouli, J. Yang, A. Yu, and Y. Zhang, in ACM SIGMOD Intl. Conf. Management Data, 2008.
"Generating wide-area content-based publish/subscribe workloads," with A. Yu and J. Yang, in 5th International Workshop on Networking Meets Databases, 2009.
"Indexing uncertain data," with S.-W. Cheng, Y. Tao, and K. Yi, in Twenty Eighth Annual Symposium on Principles of Database Systems, 2009.
"Input-sensitive scalable continuous join query processing," with J. Xi, J. Yang, and H. Yu, ACM Transactions on Database Systems 34, 3 (2009), Article 13, (41 pp.).
"(Approximate) uncertain skylines," with P. Afshani, L. Arge, K. D. Larsen, and J. M. Phillips, in 14th Intl. Conf. Database Theory, 2011.
"Subscriber assignment for wide-area content-based publish/subscribe," with A. Yu and J. Yang, in International Conference on Data Engineering, 2011.

top