Indian Institute of Technology Roorkee
Office:
Department of Computer Science Box 90129
Duke University Durham, NC 27708-0129
Tel: (919) 660-6540
pankaj@cs.duke.edu ∼pankaj
PANKAJ K. AGARWAL
Home:
306 Pitch Pine Lane Chapel Hill, NC 27514 Tel: (919) 403-8008
Research Interests
Computational and combinatorial geometry, geographic information systems, spatial databases, ecological modeling, sensor networks, computational molecular biology, robotics, data struc- tures, combinatorial optimization.
Education
1986–89 PhD in Computer Science, Courant Institute of Mathematical Sciences, New York University, New York.
1984–86 Master of Science in Computer Science, University of California, Santa Barbara.
1978–82 Bachelor of Engineering in Electronics and Communication, Indian Institute of Technology, Roorkee, India.
Employment
2017– Chair, Department of Computer Science, Duke University, Durham.
2010–11 Max Planck Institute Visiting Professor, Indian Institute of Technology, Delhi, India.
2010–11 Amar S. Gupta Professor of Computer Science and Engineering, Indian Institute of Technology, Delhi, India.
2008– R. J. R. Nabisco Professor, Department of Computer Science, Duke University, Durham. 2004–10 Chair, Department of Computer Science, Duke University, Durham.
2001 Visiting Professor, Department of Computer Science, Stanford University, Stanford.
2001–05 Adjunct Professor, Department of Computer Science, University of North Carolina, Chapel Hill. 2001– Professor (secondary appointment), Department of Mathematics, Duke University, Durham.
2000–05 Earl D. McLean, Jr., Professor, Department of Computer Science, Duke University, Durham. 1998– Professor, Department of Computer Science, Duke University, Durham.
1997–2005 Co-Director, Center for Geometric Computing, Duke University, Durham.
1995–00 Founding Member, Center for Geometric Computing, Brown University, Providence.
1995 Visiting Associate Professor, Department of Computer Science, Tel Aviv University, Tel Aviv. 1994–98 Associate Professor (tenured), Department of Computer Science, Duke University, Durham. 1993 Visiting Associate Professor, Department of Computer Science, Tel Aviv University, Tel Aviv.
1992–94 Associate Professor (untenured), Department of Computer Science, Duke University, Durham.
1989–92 Assistant Professor, Department of Computer Science, Duke University, Durham.
1989–90 Postdoctoral Fellow, Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, Piscataway.
1986–89 Graduate Research Assistant, Department of Computer Science, Courant Institute of Mathemati- cal Sciences, New York University, New York.
1985–86 Research Associate, Department of Computer Science, University of California, Santa Barbara.
1984–85 Teaching Assistant, Department of Computer Science, University of California, Santa Barbara.
1982–84 Design Engineer, Research and Development Laboratory, Tata Electrical Companies, Bombay, India.
1981 Graduate Engineer Trainee, Delhi Television Center, New Delhi, India.
Awards and Honors
|2018 |Best paper award, ACM Symposium on Advances in Geographic Information Systems. |
|2014 |Foreign member, The Royal Danish Academy of Sciences and Letters |
|2013 |Honorary doctorate, Aarhus University, Denmark. |
|2010 |Best paper award, ACM Symposium on Advances in Geographic Information Systems. |
|2010 |Amar S. Gupta Professor of Computer Science and Engineering, Indian Institute of Technology, Delhi. |
|2009 |Best paper award, IEEE Conference on Distributed Computing in Sensor Systems. |
|2008 |RJR Nabisco Professor of Computer Science, Dke University. |
|2002 |ACM Fellow. |
|2000 |Member, Bass Society of Fellows. |
|1996 |Alfred P. Sloan Fellow. |
|1993 |National Young Investigator Award. |
|1989 |Janet Fabri Award (best PhD thesis). |
|1984 |JN Tata Endowment Scholarship. |
|1982 |Highest rank in BE (Electronics and Communication). |
|1978 |National Talent Search Scholarship. |
I. Publications Books
1. Intersection and Decomposition Algorithms for Planar Arrangements, Cambridge University Press, Cambridge–New York–Melbourne, 1991.
2. Davenport-Schinzel Sequences and Their Geometric Applications, with M. Sharir, Cambridge Univer- sity Press, Cambridge–New York–Melbourne, 1995.
3. Combinatorial Geometry, with J. Pach, John Wiley and Sons, New York, 1995.
4. Robotics: The Algorithmic Perspective, with L. Kavraki and M. Mason, eds., A. K. Peters, Wellesley, 1998.
Book Chapters
5. “Geometric partitioning and its applications,” (invited) in Discrete and Computational Geometry: Papers from the DIMACS Special Year (J. Goodman, R. Pollack, and W. Steiger, eds.), American Mathematical Society, Providence, 1991, pp. 1–37.
6. “Algorithmic techniques for geometric optimization,” (invited) with M. Sharir, in Computer Science Today: Recent Trends and Developments, Lecture Notes in Computer Science, vol. 1000 (J. van Leeuwen, ed.), Springer-Verlag, Berlin, 1995, pp. 234–253.
7. “Largest placements and motion planning of a convex polygon,” with N. Amenta, B. Aronov, and M. Sharir, in Algorithms for Robotic Motion and Manipulation (J.-P. Laumond and M. Overmars, eds.), A. K. Peters, Wellesley, 1997, pp. 143–154.
8. “Range searching,” (invited) in CRC Handbook of Discrete and Computational Geometry (J. Goodman and J. O’Rourke, eds.), CRC Press, New York, 1997, pp. 575–598.
9. “Geometric range searching and its relatives,” (invited) with J. Erickson, in Advances in Dis- crete and Computational Geometry (B. Chazelle, J. Goodman, and R. Pollack, eds.), American Mathematical Society, Providence, 1998, pp. 1–56.
10. “Davenport–Schinzel sequences and their geometric applications,” (invited) with M. Sharir, in Handbook of Computational Geometry (J.-R. Sack and J. Urrutia, eds.), North-Holland, New York, 2000, pp. 1–47.
11. “Arrangements and their applications,” (invited) with M. Sharir, in Handbook of Computational Geometry (J.-R. Sack and J. Urrutia, eds.), North-Holland, New York, 2000, pp. 49–119.
12. “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.
13. “Deformable free space tiling for kinetic collision detection,” with J. Basch, L. J. Guibas, J. Hershberger, and L. Zhang, in Algorithmic Foundations of Robotics (B. Donald, K. Lynch, and D. Russ, eds.), A.K. Peters, Natick, MA, 2001, pp. 83–96.
14. “Randomized algorithms for geometric optimization,” with S. Sen, in Handbook of Randomized Computation (J. Pardalos, S. Rajasekaran, J. Reif, and J. Rolim eds.), Kluwar Academic Press, The Netherlands, 2001, pp. 151–201.
15. “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.
16. “Range searching,” revised and expanded version in CRC Handbook of Discrete and Computational Geometry (J. Goodman and J. O’Rourke, eds.), CRC Press, New York, 2004.
17. “Geometric approximation via coresets,” with S. Har-Peled and K. R. Varadarajan, in Combi- natorial and Computational Geometry (J. E. Goodman, J. Pach, and E. Welzl, eds.), Cambridge University Press, New York, 2005, pp. 1–30.
18. “State of the union (of geometric objects): A Review,” with J. Pach and M. Sharir, in Surveys on Computational Geometry: Twenty Years Later (J. Goodman, J. Pach, and R. Pollack, eds.), American Mathematical Society, Providence, 2008, pp. 9–48.
19. “Range searching,” revised and expanded version in CRC Handbook of Discrete and Computational Geometry (J. Goodman, J. O’Rourke, and C. Toth eds.), CRC Press, New York, 2017, 1057–1092.
20. “Simplex range searching,” in Journey Through Discrete Mathematics: A Tribute to JirˇıMatousˇek. (M. Loebl, J. Nesˇetrˇil, and R. Thomas eds.), Springer, Heidelberg, 2017, 1–30.
21. “Geometric optimization revisited,” with E. Ezra and K. Fox, in Computing and Software Science, Lecture Notes in Computer Science, vol 10,000 (B. Steffen and G. Woeginger, eds.), 2019, 66–84.
Journal Articles
22. “KBGIS-II: A knowledge-based geographic information system,” with T. Smith, D. Peuquet, and
S. Menon, International Journal of Geographical Information Systems, 1 (1987), 149–172.
23. “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.
24. “Red-blue intersection detection algorithms, with applications to motion planning and collision detection,” with M. Sharir, SIAM Journal on Computing, 19 (1990), 297–322.
25. “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.
26. “Partitioning arrangements of lines: I. A deterministic algorithm,” (invited) Discrete and Compu- tational Geometry, 5 (1990), 449–483.
27. “Partitioning arrangements of lines: II. Applications,” (invited) Discrete and Computational Geometry, 5 (1990), 533–573.
28. “Computing all 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.
29. “Euclidean minimum spanning tree and bichromatic closest pairs,” (invited) with H. Edelsbrun- ner, O. Schwarzkopf, and E. Welzl, Discrete and Computational Geometry, 6 (1991), 407–422.
30. “Off-line dynamic maintenance of the width of a planar point set,” with M. Sharir, Computational Geometry: Theory and Applications, 1 (1991), 65–78.
31. “Counting facets and incidences,” with B. Aronov, Discrete and Computational Geometry, 7 (1992), 359–369.
32. “Farthest neighbors, maximum spanning trees and related problems in higher dimensions,” with J. Matousˇek and S. Suri, Computational Geometry: Theory and Applications, 1 (1992), 189–201.
33. “Ray shooting and other applications of spanning trees with low stabbing number,” SIAM Journal on Computing, 21 (1992), 540–570.
34. “Intersection queries in sets of discs,” (invited) with M. van Kreveld and M. Overmars, BIT, 32 (1992), 268–279.
35. “Relative neighborhood graphs in three dimensions,” with J. Matousˇek, Computational Geometry: Theory and Applications, 2 (1992), 1–15.
36. “Oriented aligned rectangle packing problem,” with M. T. Shing, European Journal of Operations Research, 62 (1992), 210–220.
37. “Applications of a new space partitioning technique,” with M. Sharir, Discrete and Computational Geometry, 9 (1993), 11–38.
38. “Circle shooting in a simple polygon,” with M. Sharir, Journal of Algorithms, 14 (1993), 68–87.
39. “Circular visibility of a simple polygon from a fixed point,” with M. Sharir, International Journal of Computational Geometry and Applications, 3 (1993), 1–25.
40. “Selecting distances in the plane,” with B. Aronov, M. Sharir, and S. Suri, Algorithmica, 9 (1993), 495–514.
41. “Counting circular arc intersections,” with M. Pellegrini and M. Sharir, SIAM Journal on Comput- ing, 22 (1993), 778–793.
42. “Ray shooting and parametric search,” with J. Matousˇek, SIAM Journal on Computing, 22 (1993), 794–806.
43. “Intersection queries in curved objects,” with M. van Kreveld and M. Overmars, Journal of Algorithms, 15 (1993), 229–266.
44. “Computing a segment-center for a planar point set,” with A. Efrat, M. Sharir, and S. Toledo,
Journal of Algorithms, 15 (1993), 314–323.
45. “Planar geometric location problems,” with M. Sharir, Algorithmica, 11 (1994), 185–195.
46. “On range searching with semialgebraic sets,” with J. Matousˇek, Discrete and Computational Geometry, 11 (1994), 393–418.
47. “On the number of views of polyhedral terrains,” with M. Sharir, Discrete and Computational Geometry, 12 (1994), 177–182.
48. “On stabbing lines for convex polyhedra in 3D,” Computational Geometry: Theory and Applications, 4 (1994), 177–189.
49. “Can visibility graphs be represented compactly?” (invited) with N. Alon, B. Aronov, and S. Suri, Discrete and Computational Geometry, 12 (1994), 347–365.
50. “Applications of parametric searching in geometric optimization,” (invited) with M. Sharir and
S. Toledo, Journal of Algorithms, 17 (1994), 292–318.
51. “Implicit point location in arrangement segments with application to motion planning,” with M. van Kreveld, International Journal of Computational Geometry and Applications, 4 (1994), 369–383.
52. “Dynamic half-space searching and its applications,” with J. Matousˇek, Algorithmica, 13 (1995), 325–345.
53. “Computing depth orders and related problems,” with M. Katz and M. Sharir, Computational Geometry: Theory and Applications, 5 (1995), 187–206.
54. “Ray shooting among convex polytopes in 3D,” with M. Sharir, SIAM Journal on Computing, 25 (1996), 100–116.
55. “The overlay of lower envelopes and its applications, ” with O. Schwarzkopf and M. Sharir,
Discrete and Computational Geometry, 15 (1996), 1–13.
56. “Selection in monotone matrices and kth nearest neighbors,” with S. Sen, Journal of Algorithms, 20 (1996), 581–601.
57. “Polygon and connected component intersection searching,” with M. van Kreveld, Algorithmica, 15 (1996), 626–660.
58. “Efficient randomized algorithms for some geometric optimization problems,” (invited) with M. Sharir, Discrete and Computational Geometry, 16 (1996), 317–337.
59. “Ray shooting amidst convex polygons in 2D,” with M. Sharir, Journal of Algorithms, 21 (1996), 508–519.
60. “Linear approximation of convex objects,” with K. R. Varadarajan, Information Processing Letters, 62 (1997), 89–94.
61. “Quasi-planar graphs have a linear number of edges,” with B. Aronov, J. Pach, R. Pollack, and
M. Sharir, Combinatorica, 17 (1997), 1–9.
62. “Approximating shortest paths on a convex polytope in three dimensions,” with S. Har-Peled,
M. Sharir, and K. R. Varadarajan, Journal of the Association for Computing Machinery, 44 (1997), 567–584.
63. “Star unfolding of a polytope with applications,” with B. Aronov, J. O’Rourke, and C. Schevon,
SIAM Journal on Computing, 26 (1997), 1689–1713.
64. “Computing envelopes in four dimensions with applications,” with B. Aronov and M. Sharir,
SIAM Journal on Computing, 26 (1997), 1714–1732.
65. “Placement of one convex polygon inside another,” with N. Amenta and M. Sharir, Discrete and Computational Geometry, 19 (1998), 95–104.
66. “Computing many faces in arrangements of lines and segments,” with J. Matousˇek and O. Schwarzkopf, SIAM Journal on Computing, 27 (1998), 491–505.
67. “On levels in arrangements of lines, segments, planes, and triangles,” (invited) with B. Aronov,
T. M. Chan, and M. Sharir, Discrete and Computational Geometry, 19 (1998), 315–331.
68. “Constructing levels in arrangements and higher order Voronoi diagrams,” with M. de Berg, J. Matousˇek, and O. Schwarzkopf, SIAM Journal on Computing, 27 (1998), 654–667.
69. “Surface approximation and geometric partitions,” with S. Suri, SIAM Journal on Computing, 27 (1998), 1016–1035.
70. “The discrete 2-center problem,” (invited) with M. Sharir and E. Welzl, Discrete and Computational Geometry, 20 (1998), 287–306.
71. “Label placement by maximum independent set in rectangles,” with M. van Kreveld and S. Suri,
Computational Geometry: Theory and Applications, 11 (1998), 209–218.
72. “Efficient algorithms for geometric optimization,” with M. Sharir, ACM Computing Surveys, 30 (1998), 412–458.
73. “Line transversals of balls and smallest enclosing cylinders in three dimensions,” with B. Aronov and M. Sharir, Discrete and Computational Geometry, 21 (1999), 373–388.
74. “Motion planning for a convex polygon in a polygonal environment,” with B. Aronov and M. Sharir, Discrete and Computational Geometry, 22 (1999), 201–221.
75. “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.
76. “Efficient algorithms for approximating polygonal chains,” with K. R. Varadarajan, Discrete and Computational Geometry 23 (2000), 273–291.
77. “Binary space partitions for fat rectangles,” with E. Grove, T. M. Murali, and J. S. Vitter, SIAM Journal on Computing, 29 (2000), 1422–1448.
78. “Cylindrical static and kinetic binary space partitions,” with L. Guibas, T. M. Murali, and J. S. Vitter, Computational Geometry: Theory and Applications, 16 (2000), 103–127.
79. “Efficient searching with linear constraints,” (invited) with L. Arge, J. Erickson, P. G. Franciosa,
J. S. Vitter, Journal of Computer and Systems Sciences, 61 (2000), 194–216.
80. “Lower bounds for kinetic planar subdivisions,” (invited) with J. Basch, M. de Berg, L. J. Guibas, and J. Hershberger, Discrete and Computational Geometry, 24(2000), 721–733.
81. “Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions,” (invited) with
M. Sharir, Discrete and Computational Geometry, 24(2000), 645–685.
82. “Approximation and exact algorithms for minimum-width annuli and shells,” (invited) with B. Aronov, S. Har-Peled, and M. Sharir, Discrete and Computational Geometry, 24(2000), 687–705.
83. “Penetration depth of two convex polytopes in 3D,” (invited) with L. J. Guibas, S. Har-Peled, A. Rabinovitch, and M. Sharir, Nordic J. Computing, 7 (2000), 227–240.
84. “Approximation algorithms for curvature-constrained shortest paths,” with H. Wang, SIAM Journal on Computing, 30 (2001), 1739–1772.
85. “Approximating shortest paths on a nonconvex polyhedron,” with K. R. Varadarajan, SIAM Journal on Computing, 30 (2001), 1321–1340.
86. “Exact and approximation algorithms for minimum-width cylindrical shells,” with B. Aronov and M. Sharir, Discrete and Computational Geometry, 26 (2001), 307–320.
87. “Maintaining the extent of a moving point set,” with L. Guibas, J. Hershberger, and E. Veach,
Discrete and Computational Geometry, 26 (2001), 353–374.
88. “Polygon decomposition for efficient construction of Minkowski sums,” (invited) with E. Flato and D. Halperin, Computational Geometry: Theory and Applications, 21 (2002), 21–38.
89. “Output-sensitive algorithms for uniform partitions of points,” with B. Bhattacharya and S. Sen,
Algorithmica, 32 (2002), 521–539.
90. “Computing approximate shortest paths on convex polytopes,” with S. Har-Peled and M. Karia,
Algorithmica, 33 (2002), 227–242.
91. “Exact and approximation algorithms for clustering,” with C. M. Procopiuc, Algorithmica, 33 (2002), 201–226.
92. “Advances in indexing for mobile objects,” with C. M. Procopiuc, (invited) Bulletin of Data Engineering, 25 (2002), 25–34.
93. “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 and Applications, 23 (2002), 195–208.
94. “On the numbers of congruent simplices in a point set,” with M. Sharir, Discrete and Computational Geometry, 28 (2002), 123–150.
95. “Box-trees and R-trees with near-optimal query time,” with M. de Berg, J. Gudmundsson, M. Hammar, and H. J. Haverkort, Discrete and Computational Geometry, 28 (2002), 291–312.
96. “Algorithmic Issues in Modeling Motion,” with L. J. Guibas, H. Edelsbrunner, J. Erickson, M. Isard, S. Har-Peled, J. Hershberger, C. Jensen, L. Kavraki, P. Koehl, M. Lin, D. Manocha, D. Metaxas, B. Mitrich, D. Mount, S. Muthukrishnan, D. Pai, E. Sacks, J. Snoeyink, S. Suri, and O. Wolfson, ACM Computing Surveys, 24 (2002), 550–572.
97. “Deformable free space tilings for kinetic collision detection,” (invited) with J. Basch, L. J. Guibas,
J. Hershberger, and L. Zhang, International Journal of Robotics Research, 21 (2002), 179–197.
98. “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.
99. “Indexing moving points,” (invited) with L. Arge and J. Erickson, Journal of Computer and Systems Sciences, 66 (2003), 207–243.
100. “Approximation algorithms for projective clustering,” with C. M. Procopiuc, Journal of Algorithms, 46 (2003), 115–139.
101. “A (1 + ε)-approximation algorithm for computing the two-line center,” with C. M. Procopiuc and K. R. Varadarajan, Computational Geometry: Theory and Applications, 26 (2003), 119–128.
102. “Lenses in arrangements of pseudo-circles and their applications,” with E. Nevo, J. Pach, R. Pinchasi, M. Sharir, and S. Smorodinsky, Journal of the Association for Computing Machinery, 51 (2004), 139–186.
103. “Computing the writhing number of a polygonal knot,” with H. Edelsbrunner and Y. Wang,
Discrete and Computational Geometry, 32 (2004), 37–54.
104. “Collision detection for deforming necklaces,” (invited) with L. J. Guibas, A. Nguyen, D. Russel, and L. Zhang, Computational Geometry: Theory and Applications, 28 (2004), 137–163.
105. “Approximating extent measures of points,” with S. Har-Peled and K. R. Varadarajan, Journal of the Association for Computing Machinery, 51 (2004), 606–635.
106. “A near-quadratic algorithm for fence design,” with R.-P. Berretty and A. D. Collins, Discrete and Computational Geometry, 33 (2005), 463–481.
107. “Pseudo-line arrangements: Duality, algorithms, and applications,” with M. Sharir, SIAM Journal on Computing, 34 (2005), 526–552.
108. “On lines avoiding unit balls in three dimensions,” with B. Aronov, V. Koltun, and M. Sharir,
Discrete and Computational Geometry, 34 (2005) 231–250.
109. “Approximation algorithms for k-line center,” (invited) with C. M. Procopiuc and K. R. Varadara- jan, Algorithmica, 42 (2005), 221–230.
110. “Near-linear time approximation algorithms for curve simplification,” (invited) with S. Har- Peled, N. Mustafa, and Y. Wang, Algorithmica, 42 (2005), 203–219.
111. “Independent set of intersection graphs of convex objects in 2D,” with N. H. Mustafa, Computa- tional Geometry: Theory and Applications, 34 (2006), 83–95.
112. “Extreme elevation on a 2-manifold,” (invited) with H. Edelsbrunner, J. Harer, and Y. Wang,
Discrete and Computational Geometry, 36 (2006), 553–572.
113. “A 2D kinetic triangulation with near-quadratic topological changes,” (invited) with Y. Wang and H. Yu, Discrete and Computational Geometry, 36 (2006), 573–592.
114. “Faster algorithms for optimal multiple sequence alignment based on pairwise comparisons,” with Y. Bilu and R. Kolodny, IEEE Transactions on Bioinformatics, 3 (2006), 408–422.
115. “Computing maximally separated sets in the plane,” with M. Overmars and M. Sharir, SIAM Journal on Computing, 36 (2006), 815–834.
116. “Efficient algorithms for bichromatic separability,” with B. Aronov and V. Koltun, ACM Transac- tions on Algorithms, 2 (2006), 209–227.
117. “Segmenting object space by geometric reference structures,” with D. Brady and J. Matousˇek,
ACM Transactions on Sensor Networks, 2 (2006), 455–465.
118. “Resolving the biodiversity paradox,” with J. Clark, M. Dietze, S. Chakraborty, I. Ibanez, S. LaDeau, and M. Wolosin, Ecology Letters, 10 (2007), 647–659.
119. “A scalable algorithm for dispersing population,” (invited) with S. Govindrajan, M. Dietze, and
J. Clark, Journal of Intelligent Information Systems, 29 (2007), 39–61.
120. “Fast molecular shape matching using contact maps,” with N. Mustafa and Y. Wang, Journal of Computational Biology, 14 (2007), 131–143.
121. “Localization using boundary sensors: an analysis based on graph theory,” with Y. Zheng and
D. J. Brady, ACM Transactions on Sensor Networks, 3 (2007), Article 21 (19 pp.).
122. “On polyhedra induced by point sets in space,” with F. Hurtado, G. T. Toussaint, and J. Trias,
Discrete Applied Mathematics, 156 (2008), 42–54.
123. “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, Discrete and Computational Geometry, 39 (2008), 17–37.
124. “Robust shape fitting via peeling and grating coresets,” with S. Har-Peled and H. Yu, Discrete and Computational Geometry, 39 (2008), 38–58.
125. “Practical methods for shape fitting and kinetic data structures using coresets,” with R. Poreddy,
K. Varadarajan, and H. Yu, Algorithmica, 52 (2008), 378–402.
126. “Algorithms for center and Tverberg points,” with M. Sharir and E. Welzl, ACM Transactions on Algorithms, 5, 1 (2008), Article 5, (20 pp.).
127. “Kinetic and dynamic data structures for closest pairs and all nearest neighbors,” with H. Kaplan and M. Sharir, ACM Transactions on Algorithms 5, 1 (2008), Article 4, (37 pp.).
128. “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.)
129. “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.
130. “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.
131. “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, (21 pp.).
132. “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.
133. “Out-of-order event processing in kinetic data structures,” with M. A. Abam, M. de Berg, and H. Yu, Algorithmica, 60 (2011), 250-273.
134. “Near-linear approximation algorithms for geometric hitting sets,” with E. Ezra and M. Sharir,
Algorithmica, 63 (2012), 1–25.
135. “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.
136. “Subscriber assignment for wide-area content-based publish/subscribe system,” with A. Yu and
J. Yang, IEEE Transactions on Knowledge and Data Engineering, 24 (2012), 1833–1847.
137. “Range searching on uncertain data,” with S.-W. Cheng, Y. Tao, and K. Yi, ACM Transactions on Algorithms, 8 (2012), Article 43.
138. “(Approximate) uncertain skylines,” with P. Afshani, L. Arge, K. D. Larsen, and J. M. Phillips,
Theory of Computing, 52 (2013), 342–366.
139. “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.
140. “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.
141. “The 2-center problem in three dimensions,” with R. Ben Avraham and M. Sharir, Computational Geometry: Theory and Applications, 46 (2013), 734–746.
142. “Computing correlation between piecewise-linear functions,” with B. Aronov, M. van Kreveld,
M. Lo¨ ffler, and R. I. Silveira, SIAM Journal on Computing, 42 (2013), 1867–1887.
143. “The resilience of WDM networks to probabilistic geographical failures,” with A. Efrat, S. Ganjugunte, D. Hay, S. Sankararaman, G. Zussman, IEEE/ACM Transacations on Networking, 21 (2013), 1525–1538.
144. “On range searching with semialgebraic sets II,” with J. Matousˇek and M. Sharir, SIAM Journal on Computing, 42 (2013), 2039–2062.
145. “Mergeable summaries,” (invited) with G. Cormode, Z. Huang, J. M. Phillips, Z. Wei, and K. Yi,
ACM Transactions on Database Systems, 38 (2013), 26.
146. “On channel-discontinuity-constraint routing in wireless networks” with S. Sankararaman, A. Efrat, and S. Ramasubramanian, Ad-Hoc Networks, 13 (2014), 153–169..
147. “Computing the discrete Fre´chet distance in subquadratic time,” with R. Ben Avraham, H. Kaplan, and M. Sharir, SIAM Journal on Computing, 43 (2014), 429–449.
148. “Union of random Minkowski sums and network vulnerability analysis,” (invited) with S. Har-Peled, H. Kaplan, and M. Sharir, Discrete and Computational Geometry, 52 (2014), 153–169.
149. “Sparsification of motion-planning roadmaps by edge contraction,” with D. Shaharabani, O. Salzman, and D. Halperin, The International Journal of Robotics Research, 33 (2014), 1711–1725.
150. “Streaming algorithms for extent problems in high dimensions,” with R. Sharathkumar, Algo- rithmica, 72 (2015), 83–98.
151. “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.
152. “Stable Delaunay graphs,” with J. Gao, L. Guibas, H. Kaplan, N. Rubin, and M. Sharir, Discrete and Computational Geometry 54 (2015), 905–929..
153. “Top-k preferences in high dimensions,” with A. Yu and J. Yang, IEEE Transactions on Knowledge and Data Engineering28 (2016), 311–325.
154. “Natural neighbor interpolation on 2D and 3D grids using a GPU,” with A. Beutel and T. Mølhave, ACM Transactions on Spatial Algorithms and Systems, 2 (2016), 7:1–7:31.
155. “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.
156. “Convex hull under uncertainty,” with S. Har-Peled, S. Suri, H. Tildiz, and W. Zhang, Algorith- mica, 79 (2017), 340–367.
157. “Toward computational fact checking,” with Y. Wu, C. Li, J. Yang, and C. Yu, ACM Transactions on Database Systems, 42 (2017), 4:1–4:41.
158. “Finding diverse, high-value representatives on a surface of answers,” with Y. Wu, J. Gao, and J. Yang, PLVDB, 10 (2017), 793–804.
159. “Nearest-neighbor searching under uncertainty I,” with A. Efrat, S. Sankararaman, and W. Zhang, Discrete and Computational Geometry, 58 (2017), 705–745.
160. “Range-max queries on uncertain data,” with N. Kumar, S. Sintos, and S. Suri, Journal of Computer and Systems Sciences, 94 (2018), 118–134.
161. “Computing the Gromov-Hausdorff distance for metric trees,” with K. Fox, A. Nath, A. Sidiropou- los, and Y. Wang, ACM Transactions on Algorithms, 14(2) (2018), 24:1–24:20.
162. “On computing high quality paths amid polygonal obstacles,” with K. Fox and O. Salzmann,
ACM Transactions on Algorithms, 14(6) (2018), 46:1–46:21.
163. “Query perturbation analysis: An adventure of database researchers in fact-checking,” with J. Yang, S. Roy, B. Walenz, Y. Wu, C. Yu, C. Li, IEEE Data Engineering Bulletin, 41(3) (2018), 28–42.
164. “Durable top-k queries on temporal data,” with J. Gao and J. Yang, PVLDB, 11 (2018), 2223–2235.
165. “Flood risk analysis on terrains,” with M. Rav and A. Lowe (invited), ACM Transactions on Spatial Algorithms and Systems, 5 (2019), 2:1–2:31.
166. “Selecting data to clean for fact checking: Minimizing uncertainty vs. maximizing surprise,” with S. Stavros and J. Yang, PVLDB, 12 (2019), 2408–2421.
167. “Near-linear algorithms for geometric hitting sets and set covers,” with J. Pan, Discrete and Computational Geometry, in press.
168. “Flood risk analysis,” with A. Lowe and M. Rav (invited), Communications of the ACM (Research Highlight), in press.
169. “Flood risk analysis on terrains under the multi-flow-direction model,” with A. Lowe, to appear in ACM Transactions on Spatial Algorithms and Systems.
170. “A near-linear time ε-approximation algorithm for geometric bipartite matching,” with R. Sharathkumar, to appear in Journal of the Association for Computing Machinery.
171. “Union of hypercubes and 3D Minkowski sums with random sizes,” with H. Kaplan and M. Sharir, submitted to Discrete and Computational Geometry.
Conference Proceedings
172. “Red-blue intersection detection algorithms, with applications to motion planning and collision detection,” with Micha Sharir, in Proceedings Fourth Annual Symposium on Computational Geometry, 1988, 70–80.
173. “Ray shooting and other applications of spanning trees with low stabbing number,” in Proceed- ings Fifth Annual Symposium on Computational Geometry, 1989, 315–325.
174. “An deterministic algorithm for partitioning arrangements of lines and its applications,” in
Proceedings Fifth Annual Symposium on Computational Geometry, 1989, 11–22.
175. “Computing all external-farthest neighbors for a simple polygon,” with A. Aggarwal, B. Aronov,
S. Kosaraju, B. Shieber, and S. Suri, in Proceedings First Canadian Conference on Computational Geometry, 1989.
176. “Selecting distances in the plane,” with B. Aronov, M. Sharir, and S. Suri, in Proceedings Sixth Annual Symposium on Computational Geometry, 1990, 321–331.
177. “Euclidean minimum spanning tree and bichromatic closest pairs,” with H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, in Proceedings Sixth Annual Symposium on Computational Geometry, 1990, 203–210.
178. “Star unfolding of a polytope with applications,” with B. Aronov, J. O’Rourke, and C. Schevon, in Proceedings Second Scandinavian Workshop on Algorithm Theory, 1990, 251–263.
179. “Intersection queries in sets of discs,” with M. van Kreveld and M. Overmars, in Proceedings Second Scandinavian Workshop on Algorithm Theory, 1990, 393–403.
180. “Planar geometric location problems and maintaining the width of a planar set,” with M. Sharir, in Proceedings Second Annual ACM-SIAM Symposium on Discrete Algorithms, 1991, 449–458.
181. “Counting circular arc intersections,” with M. Sharir, in Proceedings Seventh Annual Symposium on Computational Geometry, 1991, 10–20.
182. “Storing and searching curved objects,” with M. van Kreveld and M. Overmars, in Proceedings Seventh Annual Symposium on Computational Geometry, 1991, 41–50.
183. “Applications of a new space partitioning technique,” with M. Sharir, in Proceedings Second Workshop on Algorithms and Data Structures, 1991, 379–391.
184. “Farthest neighbors, maximum spanning trees and related problems in higher dimensions,” with J. Matousˇek and S. Suri, in Proceedings Second Workshop on Algorithms and Data Structures, 1991, 105–116.
185. “Applications of parametric searching in geometric optimization,” with M. Sharir and S. Toledo, in Proceedings Third Annual ACM-SIAM Symposium on Discrete Algorithms, 1992, 72–82.
186. “Relative neighborhood graphs in three dimensions,” with J. Matousˇek, in Proceedings Third Annual ACM-SIAM Symposium on Discrete Algorithms, 1992, 58–65.
187. “Ray shooting and parametric search,” with J. Matousˇek, in Proceedings Twenty Fourth Annual ACM Symposium on Theory of Computing, 1992, 517–526.
188. “Range searching with semialgebraic sets,” with J. Matousˇek, in Proceedings Seventeenth Sympo- sium on Mathematical Foundations of Computer Science, 1992, 1–13.
189. “Dynamic half-space range searching with applications to proximity problems,” with D. Epp- stein and J. Matousˇek, in Proceedings Thirty Third Annual IEEE Symposium on Foundations of Computer Science, 1992, 80–89.
190. “Implicit point location in arrangement segments with application to motion planning,” with M. van Kreveld, in Proceedings Twelfth Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 1992, 80–91.
191. “Ray shooting among convex polytopes in 3D,” with M. Sharir, in Proceedings Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 1993, 260–270.
192. “Can visibility graphs be represented compactly?” with N. Alon, B. Aronov, and S. Suri, in
Proceedings Ninth Annual Symposium on Computational Geometry, 1993, 338–347.
193. “Polygon and connected component intersection searching,” with M. van Kreveld, in Proceedings Third Workshop on Algorithms and Data Structures, 1993, 36–47.
194. “On the number of views of polyhedral terrains,” with M. Sharir, in Proceedings Fifth Canadian Conference on Computational Geometry, 1993, 55–60.
195. “Surface approximation and disjoint geometric covers,” with S. Suri, in Proceedings Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 1994, 24–33.
196. “Computing envelopes in four dimensions with applications,” with B. Aronov and M. Sharir, in
Proceedings Tenth Annual Symposium on Computational Geometry, 1994, 348–358.
197. “Computing many faces in arrangements of lines and segments,” with J. Matousˇek and O. Schwarzkopf, in Proceedings Tenth Annual Symposium on Computational Geometry, 1994, 76–84.
198. “Constructing levels in arrangements and higher order Voronoi diagrams,” with M. de Berg,
J. Matousˇek, and O. Schwarzkopf, in Proceedings Tenth Annual Symposium on Computational Geometry, 1994, 67–75.
199. “Computing depth orders and related problems,” with M. Katz and M. Sharir, in Proceedings Fourth Scandinavian Workshop on Algorithm Theory, 1994, 1–12.
200. “Selection in monotone matrices and kth nearest neighbors,” with S. Sen, in Proceedings Fourth Scandinavian Workshop on Algorithm Theory, 1994, 13–24.
201. “Motion planning for a steering-constrained robot through moderate obstacles,” with P. Ragha- van and H. Tamaki, in Proceedings Twenty Seventh Annual ACM Symposium on Theory of Computing, 1995, 342–352.
202. “Line stabbing bounds in three dimensions,” with B. Aronov and S. Suri, in Proceedings Eleventh Annual Symposium on Computational Geometry, 1995, 267–276.
203. “Efficient randomized algorithms for some geometric optimization problems,” with M. Sharir, in Proceedings Eleventh Annual Symposium on Computational Geometry, 1995, 326–335.
204. “Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications,” with A. Efrat and M. Sharir, in Proceedings Eleventh Annual Symposium on Computational Geometry, 1995, 39–50.
205. “The overlay of envelopes and their applications,” with O. Schwarzkopf and M. Sharir, in
Proceedings Eleventh Annual Symposium on Computational Geometry, 1995, 182–189.
206. “Linear approximation of convex objects,” with K. R. Varadarajan, in Proceedings Seventh Canadian Conference on Computational Geometry, 1995, 13–18.
207. “Quasi-planar graphs have a linear number of edges,” with B. Aronov, J. Pach, R. Pollack, and
M. Sharir, in Symposium on Graph Drawing, 1995, 1–7.
208. “Efficient generation of k-directional assembly sequences,” with M. de Berg, D. Halperin, and
M. Sharir, in Proceedings Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996, 122–131.
209. “Approximation algorithms for shortest paths with bounded curvature,” with H. Wang, in
Proceedings Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996, 409–418.
210. “Simplification envelopes,” with J. Cohen, A. Varshney, D. Manocha, G. Turk, F. Brooks, H. Weber, and W. Wright, in SIGGRAPH, 1996, 119–128.
211. “Largest placements and motion planning of a convex polygon,” with N. Amenta, B. Aronov, and M. Sharir, in Proceedings Second Workshop on Algorithmic Foundations of Robotics, 1996.
212. “Binary space partitions for fat rectangles,” with E. Grove, T. M. Murali, and J. S. Vitter, in Proceedings Thirty Seventh Annual IEEE Symposium on Foundations of Computer Science, 1996, 482–491.
213. “Line transversals of balls and smallest enclosing cylinders in three dimensions,” with B. Aronov and M. Sharir, in Proceedings Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997, 483–492.
214. “An efficient algorithm for terrain simplification,” with P. K. Desikan, in Proceedings Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997, 139–147.
215. “Nonholonomic path planning for pushing a disk among obstacles,” with J.-C. Latombe, R. Motwani, and P. Raghavan, in Proceedings IEEE International Conference on Robotics and Automation, 1997, 3124–3129.
216. “On levels in arrangements of lines, segments, planes, and triangles,” with B. Aronov and M. Sharir, in Proceedings Thirteenth Annual Symposium on Computational Geometry, 1997, 30–38.
217. “Cylindrical kinetic and static binary space partitions,” with L. Guibas, T. M. Murali, and J. S. Vitter, in Proceedings Thirteenth Annual Symposium on Computational Geometry, 1997, 39–48.
218. “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.
219. “The discrete 2-center problem,” with M. Sharir and E. Welzl, in Proceedings Thirteenth Annual Symposium on Computational Geometry, 1997, 147–155.
220. “Maintaining structures for moving points,” with L. Guibas, J. Hershberger, and E. Veach, in
Proceedings Fifth Workshop on Algorithms and Data Structures, 1997, 31–44.
221. “Label placement by maximum independent set in rectangles,” with M. van Kreveld and S. Suri, in Proceedings Ninth Canadian Conference on Computational Geometry, 1997.
222. “Approximating shortest paths on polyhedral terrains,” with K. R. Varadarajan, in Proceedings Thirty Eighth Annual IEEE Symposium on Foundations of Computer Science, 1997, 182–191.
223. “Kinetic binary space partitions for intersecting segments and disjoint triangles,” with J. Erickson and L. Guibas, in Proceedings Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, 107–116.
224. “I/O-efficient algorithms for contour line extraction and planar graph blocking,” with L. Arge, T.
M. Murali, K. R. Varadarajan, and J. S. Vitter, in Proceedings Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, 117–126.
225. “Exact and approximation algorithms for clustering,” with C. M. Procopiuc, in Proceedings Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, 658–667.
226. “Efficient searching with linear constraints,” with L. Arge, J. Erickson, P. G. Franciosa, J. S. Vitter, in Proceedings Seventeenth Annual Symposium on Principles of Database Systems, 1998, 169–178.
227. “Curvature-constrained shortest paths in a convex polygon,” with T. Biedl, S. Lazard, S. Robbins,
S. Suri, and S. Whitesides, in Proceedings Fourteenth Annual Symposium on Computational Geometry, 1998, 392–401.
228. “A new algorithm for constructing binary space partitions for orthogonal rectangles,” with T. M. Murali and J. S. Vitter, in Proceedings Sixth European Symposium on Algorithms, 1998, 211–222.
229. “Parametric and kinetic minimum spanning trees,” with D. Eppstein, L. J. Guibas, and M. Henzinger, in Proceedings Thirty Ninth Annual IEEE Symposium on Foundations of Computer Science, 1998, 596–605.
230. “I/O-efficient dynamic point location in monotone subdivisions,” with L. Arge, G. Brodal, J. S. Vitter, in Proceedings Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, 11–20.
231. “Approximation algorithms for bipartite and non-bipartite matching in the plane,” with K. R. Varadarajan, in Proceedings Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, 805–814.
232. “Motion planning of a ball amid segments in three dimensions,” with M. Sharir, in Proceedings Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, 21–30.
233. “A simple and efficient algorithm for high quality line labeling,” with L. Knipping, M. van Kreveld, T. Strijk, and A. Wolff, GIS Research UK: 7th National Conference, 1999. (Also appears in the Fifteenth European Workshop on Computational Geometry, 1999.)
234. “Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions,” with M. Sharir, in Proceedings Fifteenth Annual Symposium on Computational Geometry, 1999, 143–153.
235. “Exact and approximation algorithms for the minimum width annuli and shells,” with B. Aronov,
S. Har-Peled, and M. Sharir, in Proceedings Fifteenth Annual Symposium on Computational Geometry, 1999, 380–389.
236. “Lower bounds for kinetic planar subdivisions,” with J. Basch, M. de Berg, L. J. Guibas, and J. Hershberger, in Proceedings Fifteenth Annual Symposium on Computational Geometry, 1999, 247–254.
237. “Output-sensitive algorithms for uniform partitions of points,” with B. Bhattacharya and S. Sen, in Proceedings Tenth Annual International Symposium on Algorithms and Computation, 1999, 403–414.
238. “Approximation algorithms for projective clustering,” with C. M. Procopiuc, in Proceedings Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000, 538–547.
239. “Exact and approximation algorithms for minimum-width cylindrical shells,” with B. Aronov and M. Sharir, in Proceedings Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000, 510–517.
240. “Approximation algorithms for layered manufacturing,” with P. K. Desikan, in Proceedings Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000, 528–537.
241. “Deformable free space tiling for kinetic collision detection,” with J. Basch, L. J. Guibas, J. Hershberger, and L. Zhang, in Fourth Workshop on Algorithmic Foundations of Robotics, 2000.
242. “Indexing moving points,” with L. Arge and J. Erickson, in Proceedings Nineteenth Annual Symposium on Principles of Database Systems, 2000, 175–186.
243. “Computing approximate shortest paths on convex polytopes,” with S. Har-Peled and M. Karia, in Proceedings Sixteenth Annual Symposium on Computational Geometry, 2000, 270–279.
244. “Computing the penetration depth of two convex polytopes in 3D,” with L. J. Guibas, S. Har- Peled, A. Rabinovitch, and M. Sharir, in Proceedings Seventh Scandinavian Workshop on Algorithm Theory, 2000, 328–338.
245. “Polygon decomposition for efficient construction of Minkowski sums,” with E. Flato and D. Halperin, in Proceedings Eighth European Symposium on Algorithms, 2000, 20–31.
246. “Maintaining approximate extent measures of moving points,” with S. Har-Peled, in Proceedings Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, 2001, 148–157.
247. “Minimal trap design,” with A. Collins and J. Harer, in Proceedings IEEE International Conference on Robotics and Automation, 2001, 2243–2248.
248. “On the numbers of congruent simplices in a point set,” in Proceedings Seventeenth Annual Symposium on Computational Geometry, 2001, 1–9.
249. “Box-trees and R-trees with near-optimal query time,” with M. de Berg, J. Gudmundsson, M. Hammar, and H. J. Haverkort, in Proceedings Seventeenth Annual Symposium on Computational Geometry, 2001, 124–133.
250. “A framework for index bulk loading and dynamization,” with L. Arge, O. Procopiuc, and
J. S. Vitter, in Proceedings Twenty-Eighth International Colloquium on Automata, Languages, and Programming, 2001, 115–127.
251. “Time responsive external data structures for for moving points,” with L. Arge and J. Vahrenhold, in Proceedings Seventh Workshop on Algorithms and Data Structures, 2001, 50–61.
252. “Reporting all intersecting pairs of polytopes in two and three dimensions,” with M. de Berg,
S. Har-Peled, M. Overmars, M. Sharir, and J. Vahrenhold, in Proceedings Seventh Workshop on Algorithms and Data Structures, 2001, 122–134.
253. “Occlusion culling for fast walkthrough in urban areas,” with S. Har-Peled and Y. Wang, in
Eurographics, 2001.
254. “On the complexity of many faces in arrangements of circles,” with B. Aronov and M. Sharir, in
Proceedings Forty Second Annual IEEE Symposium on Foundations of Computer Science, 2001, 74–83.
255. “Pseudoline arrangements: Duality, algorithms, and applications,” with M. Sharir, in Proceedings Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002, 800–809.
256. “Computing the writhing number of a polygonal knot,” with H. Edelsbrunner and Y. Wang, in
Proceedings Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002, 791–799.
257. “STAR-tree: An efficent self-adjusting index for moving points,” with C. M. Procopiuc and
S. Har-Peled, in Proceedings Fourth Workshop on Algorithms Engineering and Experiments, 2002, 178–193.
258. “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, 418–427.
259. “Near-linear time approximation algorithms for curve simplification,” with S. Har-Peled, N. Mustafa, and Y. Wang in Proceedings Tenth European Symposium on Algorithms, 2002, 29–41.
260. “Translating a planar object to maximize point containment,” with T. Hagerup, R. Ray, M. Sharir,
M. Smid, and E. Welzl. in Proceedings Tenth European Symposium on Algorithms, 2002, 42–53.
261. “Range searching in categorical data: Colored range searching on grid,” with S. Govindrajan and S. Muthukrishnan, in Proceedings Tenth European Symposium on Algorithms, 2002, 17–28.
262. “Kinetic medians and kd-trees,” with J. Gao and L. J. Guibas, in Proceedings Tenth European Symposium on Algorithms, 2002, 5–16.
263. “Approximation algorithms for k-line center,” with C. M. Procopiuc and K. R. Varadarajan, in
Proceedings Tenth European Symposium on Algorithms, 2002, 54–63.
264. “A near-quadratic algorithm for fence design,” with R.-P. Berretty and A. D. Collins, Proceedings Fifth Workshop on Algorithmic Foundations of Robotics, 2002, 347–362.
265. “CRB-tree: An efficient indexing scheme for range aggregate queries,” with S. Govindarajan and L. Arge, Proceedings Ninth International Conference on Database Theory, 2003, 143–157.
266. “HPRM: Hierarchical PRM,” with A. Collins and J. Harer, Proceedings IEEE International Confer- ence on Robotics and Automation, 2003, 4433–4438.
267. “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, 282–291.
268. “On cache-oblivious multidimensional range searching,” with L. Arge, A. Danner, and B. Holland-Minkley, Proceedings Nineteenth Annual Symposium on Computational Geometry, 2003, 237–245.
269. “Bkd-tree: A dynamic scalable kd-tree,” with O. Procopiuc, L. Arge, and J. S. Vitter, Proceedings Eighth International Symposium on Spatial and Temporal Databases, 2003, 46–65.
270. “Streaming geometric optimization using graphics hardware,” with S. Krishnan, N. H. Mustafa, and S. Venkatasubramanian, in Proceedings Eleventh European Symposium on Algorithms, 2003, 544–555.
271. “I/O-Efficient structures for orthogonal range max and stabbing max queries,” with L. Arge, J. Yang, and K. Yi, in Proceedings Eleventh European Symposium on Algorithms, 2003, 7–18.
272. “Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks,” with M. Overmars and M. Sharir, in Proceedings Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004, 516–525.
273. “Efficient algorithms for bichromatic separability,” with B. Aronov and V. Koltun, in Proceedings Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004, 682–690.
274. “Algorithms for center and Tverberg points,” with M. Sharir and E. Welzl, in Proceedings Twentyth Annual Symposium on Computational Geometry, 2004, 61–67.
275. “On lines avoiding unit balls in three dimensions,” with B. Aronov, V. Koltun, and M. Sharir, in
Proceedings Twentyth Annual Symposium on Computational Geometry, 2004, 36–45.
276. “Practical methods for shape fitting and kinetic data structures using core sets,” with R. Poreddy,
K. Varadarajan, and H. Yu, in Proceedings Twentyth Annual Symposium on Computational Geometry, 2004, 263–272.
277. “A 2D Triangulation with near-quadratic topological changes,” with Y. Wang and H. Yu, in
Proceedings Twentyth Annual Symposium on Computational Geometry, 2004, 180–189.
278. “Extreme elevation on a 2-manifold,” with H. Edelsbrunner, J. Harer, and Y. Wang, in Proceedings Twentyth Annual Symposium on Computational Geometry, 2004, 357–365.
279. “A scalable simulator for forest dynamics,” with S. Govindrajan, M. Dietze, and J. Clark, in
Proceedings Twentyth Annual Symposium on Computational Geometry, 2004, 106–115.
280. “A near-linear constant-factor approximation for Euclidean bipartite matching,” with K. R. Varadarajan, in Proceedings Twentyth Annual Symposium on Computational Geometry, 2004, 247– 252.
281. “k-means projective clustering,” with N. H. Mustafa, in Proceedings Twenty-Third Annual Sympo- sium on Principles of Database Systems, 2004, 155–165.
282. “Independent sets of intersection graphs of convex objects in 2D,” with N. H. Mustafa, in
Proceedings Ninth Scandinavian Workshop on Algorithm Theory, 2004, 127–137.
283. “Efficient tradeoff schemes in data structures for querying moving objects,” with L. Arge, J. Erickson, and H. Yu, in Proceedings Twelfth European Symposium on Algorithms, 2004, 4–15.
284. “Local search heuristic for rigid protein docking,” with V. Choi, H. Edelsbrunner, and J. Rudolph, in Proceedings Fourth Workshop on Algorithms in Bioinformatics, 2004, 218–229.
285. “An optimal dynamic interval stabbing-max data structure?” with L. Arge and K. Yi, in Proceed- ings Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, 803–812.
286. “Lower bound for sparse Euclidean spanners,” with Y. Wang and P. Yin, in Proceedings Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, 670–671.
287. “Coarse and reliable geometric alignment for protein docking,” with Y. Wang, P. Brown, H. Edelsbrunner, and J. Rudolph, in Pacific Symposium on Biocomputing, 2005, 66–77.
288. “Guarding a Terrain by Two Watchtowers,” with S. Bereg, O. Daescu, H. Kaplan, S. Ntafos, and
B. Zhu, in Proceedings Twenty First Annual Symposium on Computational Geometry, 2005, 346–355.
289. “Staying in the middle: Exact and approximate medians in R1 and R2 for moving points,” with
M. de Berg, J. Gao, L. Guibas, and S. Har-Peled, in Proceedings Eighteenth Canadian Conference on Computational Geometry, 2005, 43–46.
290. “Faster algorithms for optimal multiple sequence alignment based on pairwise comparisons,” with Y. Bilu and R. Kolodny, in Proceedings Fifth Workshop on Algorithms in Bioinformatics, 2005, 315–327.
291. “I/O-efficient construction of constrained Delaunay triangulations,” with L. Arge and K. Yi, in
Proceedings Thirteenth European Symposium on Algorithms, 2005, 355–366.
292. “Monitoring continuous band-join queries over dynamic data,” with J. Xie, J. Yang, and H. Yu, in Proceedings Twenty Sixth Annual International Symposium on Algorithms and Computation, 2005, 349–359.
293. “Robust shape fitting via peeling and grating coresets,” with S. Har-Peled and H. Yu, in Proceed- ings Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006, 182–191.
294. “Model-driven dynamic control of embedded wireless sensor networks,” with P. Flikkema, J. Clark, C. Ellis, A. Gelfand, K. Munagala, and J. Yang, in Proceedings of the Third International Conference on Computational Science, 2006, 409–416.
295. “I/O-efficient batched union-find and its applications in topological persistence and contour trees,” with L. Arge and K. Yi, in Proceedings Twenty Second Annual Symposium on Computational Geometry, 2006, 167–176.
296. “From point cloud to grid DEM: A scalable approach,” with A. Danner and L. Arge, in Proceedings Twelfth International Symposium on Spatial Data Handling, 2006, 771-788.
297. “Scalable continuous query processing by tracking hotspots,” with J. Xie, J. Yang, and H. Yu, in
Proceedings , Annual IEEE International Conference on Very Large Databases 2006, 31–42.
298. “Out-of-order event processing in kinetic data structures,” with M. A. Abam, M. de Berg, and H. Yu, in Proceedings Fourteenth European Symposium on Algorithms, 2006, 624–635.
299. “On bipartite matching under the rms distance,” with J. Phillips, in Proceedings Seventeenth Canadian Conference on Computational Geometry, 2006.
300. “Segmenting motifs in protein-protein interface surfaces,” with J. Phillips and J. Rudolph, in
Proceedings Sixth Workshop on Algorithms in Bioinformatics, 2006, 207–218.
301. “Computing a center-transversal line,” with S. Cabello, J.A. Sellare`s, and M. Sharir, in Proceedings Twenty Sixth Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2006, 93–104.
302. “Computing the volume of the union of cubes,” with H. Kaplan and M. Sharir, in Proceedings Twenty Third Annual Symposium on Computational Geometry, 2007, 294–301.
303. “Similar simplices in a d-dimensional point set,” with R. Apfelbaum, G. Purdy, and M. Sharir, in
Proceedings Twenty Third Annual Symposium on Computational Geometry, 2007, 232–238.
304. “Embeddings of surfaces, curves, and moving points in Euclidean space ,” with S. Har-Peled and
H. Yu, in Proceedings Twenty Third Annual Symposium on Computational Geometry, 2007, 381–389.
305. “A space-optimal data-stream algorithm for coresets in the plane,” with H. Yu, in Proceedings Twenty Third Annual Symposium on Computational Geometry, 2007, 1–10.
306. “From data reverence to data relevance: Model-mediated wireless sensing of the physical environment,” with P. G. Flikkema, J. S. Clark, C. S. Ellis, A. Gelfand, K. Munagala, and J. Yang, Proceedings of the Fourth International Conference on Computational Science, 2007, 988–994.
307. “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 Geographic Information Systems, 2007, 28–37.
308. “I/O efficient algorithms for computing contour lines in a terrain,” with L. Arge, T. Mølhave, and B. Sadri, in Proceedings Twenty Fourth Annual Symposium on Computational Geometry, 2008, 129–138.
309. “A geometric approach for untangling a mesh using local surgery,” with B. Sadri, and H. Yu, in
Proceedings Twenty Fourth Annual Symposium on Computational Geometry, 2008, 288–297.
310. “ProSem: Scalable wide-area publish/subscribe,” with B. Chandramouli, J. Yang, A. Yu, and
Y. Zhang, in Proceedings ACM SIGMOD International Conference on Management of Data, 2008, 1315–1318.
311. “Stabbing convex polygons with a polygon or a segment,” with D. Chen, S. Ganjugunte, E. Misiolek, M. Sharir, and K. Tang, in Proceedings Sixteenth European Symposium on Algorithms, 2008, 52–63.
312. “An efficient algorithm for Euclidian 2-center with outliers,” with J. Phillips, in Proceedings Sixteenth European Symposium on Algorithms, 2008, 64–75.
313. “On approximate geodesic-distance queries amid deforming point clouds,” with A. Efrat, R. Sharathkumar, and H. Yu, in Proceedings Eighth Workshop on Algorithmic Foundations of Robotics, 2008, 351–365.
314. “Approximate Euclidean shortest paths amid convex obstacles,” with R. Sharathkumar and H. Yu, in Proceedings Twentyth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, 283–292.
315. “Near-linear approximation algorithms for geometric hitting sets,” with E. Ezra and M. Sharir, in Proceedings Twenty Fifth Annual Symposium on Computational Geometry, 2009, 23–32.
316. “Indexing uncertain data,” with S.-W. Cheng, Y. Tao, and K. Yi, in Proceedings Twenty Eighth Annual Symposium on Principles of Database Systems, 2009, 137–146.
317. “Efficient sensor placement for surveillance problems,” with E. Ezra and S. Ganjugunte, in Proceedings Fifth IEEE International Conference on Distributed Computing in Sensor Systems (best paper), 2009, 301–314.
318. “Generating wide-area content-based publish/subscribe workloads,” with A. Yu and J. Yang, in
5th International Workshop on Networking Meets Databases, 2009.
319. “Streaming algorithms for extent problems in high dimensions,” with R. Sharathkumar, in
Proceedings Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, 1481–1489.
320. “Lipschitz unimodel and isotonic regression on paths and trees,” with J. Phillips, and B. Sadri, in Proceedings Ninth Annual Latin American Theoretical Informatics Symposium, 2010, 384–396.
321. “On channel-discontinuity-constraint routing in wireless networks” with S. Sankararaman, A. Efrat, and S. Ramasubramanian, in Proc. IEEE INFOCOM, 2010, 481–485.
322. “Computing similarity of piecewise-linear functions,” with B. Aronov, M. van Kreveld, M. Lo¨ ffler, and R. I. Silveira, in Proceedings Twenty-Sixth Annual Symposium on Computational Geome- try, 2010, 375–383. (Also appears in Twenthy Fifth European Workshop on Computational Geometry, 2009.)
323. “An improved algorithm for computing the volume of the union of cubes,” in Proceedings Twenty-Sixth Annual Symposium on Computational Geometry, 2010, 230–239.
324. “The 2-center problem in three dimensions,” with R. Ben Avraham and M. Sharir, in Proceedings Twenty-Sixth Annual Symposium on Computational Geometry, 2010, 87–96.
325. “Kinetic stable Delaunay graphs,” with J. Gao, L. Guibas, H. Kaplan, V. Koltun, N. Rubin, and M. Sharir, in Proceedings Twenty-Sixth Annual Symposium on Computational Geometry, 2010, 127–136.
326. “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.
327. “Stability of ε-kernels,” with J. Phillips and H. Yu, in Proceedings Eighteenth European Symposium on Algorithms, 2010, 487–499.
328. “A probabilistic model for network vulnerability under physical attack,” with A. Efrat, S. K. Ganjugunte, D. Hay, S. Sankararaman, G. Zussman, Military Communications Conference, 2010.
329. “Natural neighbor interpolation based grid DEM construction using a GPU,” with A. Beutel and T. Mølhave, in Proceedings Nineteenth ACM Symposium on Advances in Geographic Information Systems (best paper), 2010, 172–181.
330. “I/O-efficient contour queries on terrains,” with T. Mølhave and B. Sadri, in Proceedings Twenty- Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011, 268–284.
331. “(Approximate) uncertain skylines,” with P. Afshani, L. Arge, K. D. Larsen, and J. M. Phillips, in Proceedings Fourteenth International Conference on Database Theory, 2011, 186–196. (Also appeared in Third Workshop on Massive Data Algorithmics, 2011.)
332. “Subscriber assignment for wide-area content-based publish/subscribe system,” with A. Yu and J. Yang, in Proceedings Twenty-Seventh IEEE International Conference on Data Engineering, 2011, 267–278.
333. “The resilience of WDM networks to probabilistic geographical failures,” with A. Efrat, S. Gan- jugunte, D. Hay, S. Sankararaman, G. Zussman, in Proceedings Thirtyth International Conference on Computer Communications, 2011, 1521–1529.
334. “Exploiting temporal coherence in forest dynamics simulation,” with T. Mølhave, H. Yu, and J. Clark, in Proceedings Twenty-Seventh Annual Symposium on Computational Geometry, 2011, 77–86.
335. “Distributed localization and clustering using data correlation and the Occam’s razor principle,” with A. Efrat, C. Gniady, J.S.B. Mitchell, G. R. Sabhnani, and V. Plishchuk, in Proceedings Seventh IEEE International Conference on Distributed Computing in Sensor Systems, 2011, 1–8.
336. “TerraNNI: Natural neighbor interpolation on a 3D grid using a GPU,” with A. Beutel, T. Mølhave, A. P. Boedihardjo, and J. A. Shine, in Proceedings Twentieth ACM Symposium on Advances in Geographic Information Systems, 2011, 64–74. (Also appeared in Third Workshop on Massive Data Algorithmics, 2011.)
337. “Algorithms for the transportation problem in geometric settings,” with R. Sharathkumar, in
Proceedings Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012, 306–317.
338. “Processing and notifying range top-k subscriptions,” with A. Yu, and J. Yang, in Proceedings Twenty-Eighth IEEE International Conference on Data Engineering, 2012, 810–821.
339. “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, 385–394.
340. “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, 397–408.
341. “Mergeable summaries,” with G. Cormode, Z. Huang, J. M. Phillips, Z. Wei, and K. Yi, in Proceedings Thirty-First Annual Symposium on Principles of Database Systems, 2012, 23–34. (Also appeared in Third Workshop on Massive Data Algorithmics, 2011.)
342. “Nearest-neighbor searching under uncertainty,” with A. Efrat, S. Sankararaman, and W. Zhang, in Proceedings Thirty-First Annual Symposium on Principles of Database Systems, 2012, 225–236.
343. “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, 1487–1495.
344. “On range searching with semialgebraic sets II,” with J. Matousˇek and M. Sharir, in Proceedings Fifty-Third Annual IEEE Symposium on Foundations of Computer Science, 2012, 420–429.
345. “Computing the discrete Fre´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, 156–167.
346. “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, 4098–4105.
347. “Nearest-neighbor searching under uncertainty II,” with B. Aronov, S. Har-Peled, J. Phillips,
K. Yi, and W. Zhang, in Proceedings Thirty-Second Annual Symposium on Principles of Database Systems, 2013, 115–126.
348. “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, 177–186.
349. “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.
350. “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.
351. “Top-k preferences in high dimensions,” with A. Yu and J. Yang, in Proceedings Twenty-Ninth IEEE International Conference on Data Engineering, 2014, 748–759.
352. “Toward computational fact checking,” with Y. Wu, C. Li, J. Yang, and C. Yu, in Proceedings Fortyth Annual IEEE International Conference on Very Large Databases, 2014, 589–600.
353. “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.
354. “Near-linear algorithms for geometric hitting sets and set covers,” with J. Pan, in Proceedings Thirtyth Annual Symposium on Computational Geometry, 2014, 271–280.
355. “iCheck: computationally combating ”lies, d-ned lies, and statistics,” with Y. Wu, B. Walenz,
P. Li, A. Shim, E. Sonmez, C. Li, and J. Yang, Cong Yu, Proceedings ACM SIGMOD International Conference on Management of Data, 2014, 1063–1066.
356. “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.
357. “Convex hull under uncertainty,” with S. Har-Peled, S. Suri, H. Tildiz, and W. Zhang, in
Proceedings Twenty-Second European Symposium on Algorithms, 2014, 37–48.
358. “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.
359. “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.
360. “Computing the Gromov-Hausdorff distance for metric trees,” with K. Fox, A. Nath, A. Sidiropou- los, and Y. Wang, in Proceedings Fortyth Annual International Symposium on Algorithms and Compu- tation, 2015, 529–540.
361. “On 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.
362. “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.
363. “Range-max queries on uncertain data,” with N. Kumar, S. Sintos, and S. Suri, in Proceedings Thity-Fifth Annual Symposium on Principles of Database Systems, 2016, 465–476.
364. “Parallel algorithms for constructing range and nearest-neighbor searching data structures,” with K. Fox, K. Munagala, and A. Nath, in Proceedings Thity-Fifth Annual Symposium on Principles of Database Systems, 2016, 429–440.
365. “Markov jump processes for trajectory data,” with J. Pan, V. Rao, and A. Gelfand, in Proceedings Thirty-Third International Conference on Machine Learning, 2016.
366. “An efficient algorithm for placing electric vehicle charging stations,” with J. Pan and W. Victor, Proceedings Forty-First Annual International Symposium on Algorithms and Computation, 2016, 7:1–7:12.
367. “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.
368. “Parallel algorithms for constructing Delaunay triangulation and contour tree,” 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.
369. “Faster algorithms for the geometric transportation problem,” with K. Fox, D. Panigrahi, K.
R. Varadarajan, and A. Xiao, Proceedings Thirty-Third International Symposium on Computational Geometry, 2017, 7:1–7:16
370. “Efficient algorithms for k-regret minimizing sets,” with N. Kumar, S. Sintos, and S. Suri,
Proceedings Sixteenth Annual Symposium on Experimental Algorithms, 2017, 7:1–7:23.
371. “Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats,” with N. Rubin and
M. Sharir, Proceedings Twenty-Fifth European Symposium on Algorithms, 2017, 4:1–4:13.
372. “Dynamic Reeb graphs of triangulated 2-manifolds,” with K. Fox and A. Nath, Proceedings Thirty-Seventh Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017, 8:1–8:14.
373. “Flood risk analysis on terrains,” with M. Rav and A. Lowe, Proceedings Twenty-Sixth ACM Symposium on Advances in Geographic Information Systems, 2017, 36:1–36:10.
374. “Approximation algorithms for subtrajectory clustering,” with K. Fox, K. Munagala, A. Nath, and J. Pan, Proceedings Thirty-Seventh Annual Symposium on Principles of Database Systems, 2018, 75–87.
375. “Improved Dynamic Geodesic Nearest Neighbor Searching in a Simple Polygon,” with L. Arge and F. Staals, Proceedings Thirty-Fourth International Symposium on Computational Geometry, 2018, 4:1–4:14.
376. “Union of hypercubes and 3D Minkowski sums with random sizes,” with H. Kaplan and M. Sharir, Proceedings Forty-Fifth International Colloquium on Automata, Languages, and Programming, 2018, 10:1–10:15.
377. “Computing Shortest Paths in the Plane with Removable Obstacles,” with N. Kumar, S. Sintos, and S. Suri, Proceedings Sixteenth Scandinavian Workshop on Algorithm Theory, 2018, 5:1–5:15.
378. “Flood risk analysis on terrains under the multi-flow-direction model,” with A. Lowe, Proceedings Twenty-Seventh ACM Symposium on Advances in Geographic Information Systems (best paper award), 2018, 53–62.
379. “Approximate minimum-weight matching with outliers under translation,” with H. Kaplan, G. Kipper, W. Mulzer, G. Rote, M. Sharir, and A. Xiao, Proceedings Forty-Third Annual International Symposium on Algorithms and Computation, 2018, 26:1–26:13.
380. “An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications,” with B. Aronov, E. Ezra, and J. Zahl, Proceedings Thirty-Fifth International Symposium on Computational Geometry, 2019, 5:1–5:14.
381. “Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead,” with
R. Cohen, D. Halperin, and W. Mulzer, Proceedings Thirty-Fifth International Symposium on Computational Geometry, 2019, 26:1–26:15.
382. “Geometric partial matchings and unbalanced transportation problem,” with H.-C. Chang and A. Xiao, Proceedings Thirty-Fifth International Symposium on Computational Geometry, 2019, 6:1–6:14.
383. “ Efficient Indexes for diverse top-k range queries,” with S. Stavros and A. Steiger, submitted to
Proceedings Thirty-Nineth Annual Symposium on Principles of Database Systems, 2019.
384. “Clustering under Perturbation Stability in Near-Linear Time,” with H.-C. Chang, K. Muna- gala, E. Taylor, and E. Welzl, submitted to Proceedings Thirty-Sixth International Symposium on Computational Geometry, 2020.
385. “Dynamic geometric set cover and hitting set,” with H.-C. Chang, S. Suri, A. Xiao, and J. Xue, submitted to Proceedings Thirty-Sixth International Symposium on Computational Geometry, 2020.
386. “Durable preference top-k queries on historical data,” with J. Gao, S. Stavros, and J. Yang, submitted to Proceedings ACM SIGMOD International Conference on Management of Data, 2020.
Conference Presentations (without proceedings)
387. “A VME bus compatible FFT Processor,” with A. Choudhary and S. Sengupta, Conference on Signal Processing, Cochin, India, 1983.
388. “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.
389. “The paradox of species diversity,” with J. Clark, M. Dietze, and S. Govindrajan, in Ecological Society of America Annual Meeting, 2003.
390. “Modeling and analyzing massive terrain data,” with T. Mølhave, in National Science Foundation TeraGrid Workshop on Cyber-GIS, 2010.
Reports and Columns
391. “Strategic directions in computational geometry,” with R. Tamassia, N. Amato, D. Chen, D. Dobkin, R. Drysdale, S. Fortune, M. Goodrich, J. Hershberger, J. O’Rourke, F. Preparata, J.-R. Sack, S. Suri, I. Tollis, J. S. Vitter, and S. Whitesides, ACM Computing Surveys 28 (1996), 591–606.
392. “Simple and practical geometric algorithms,” with S. Suri, ACM Computing Surveys 28 (1996).
393. “Computational geometry column 34,” with J. O’Rourke, International Journal of Computational Geometry and Applications, 8 (1998), 637–642. (Also appeared in SIGACT News, 29 (1998), 27–33.)
394. “Open problems presented at SCG’98,” with S. Khuller and J. O’Rourke, Journal of Algorithms, 30 (1999), 449–453.
395. “Guest editors’ foreword,” with S. A. Cook, Journal of Computer and Systems Sciences, 58 (1999), 259.
396. “Guest editors’ foreword,” International Journal of Computational Geometry and Applications, 9 (1999), 325.
397. “Guest editors’ foreword,” with D. Halperin and R. Pollack, Discrete and Computational Geometry, 25 (2001), 505–506.
398. “Guest editors’ foreword,” Discrete and Computational Geometry, 26 (2001), 185–186.
399. “Guest editors’ foreword,” Computational Geometry: Theory and Applications, 24 (2003), 49.
400. “Emerging challenges in computational topology,” with M. Bern, D. Eppstein, N. Amenta, P. Chew, K. Clarkson, T. Dey, D. P. Dobkin, H. Edelsbrunner, C. Grimm, L. P. Guibas, J. Harer,
J. Hass, A. Hicks, C. K. Johnson, G. Lerman, D. Letscher, P. Plassmann, E. Sedgwick, J. Snoeyink, J. Weeks, C. Yap, and D. Zorin, ACM Computing Research Repository, .
401. “Rejoinder to Clark et al (2007): Response to Chesson and Rees,” with J. Clark, Ecology Letters 10 (2007), 661–662.
402. “Computational Geometry (Dagstuhl Seminar 11111),” with K. Mehlhorn and M. Teillaud, Dagstuhl Reports 1(3):2011, 19–41.
Technical Reports
403. “Geometric Algorithms,” Technical Report TRCS85-17, Department of Computer Science, Santa Barbara, 1985.
404. “Multiterminal flows in planar networks,” with M. T. Shing, Technical Report TRCS86-07, Department of Computer Science, University of California, Santa Barbara, 1986.
405. “An efficient multidimensional searching technique and its applications,” with M. Sharir and S. Toledo, Technical Report CS-1993-20, Department of Computer Science, Duke University, 1993.
406. “Multiresolution hierarchy generation of polygonal models,” with F. Brooks, A. Varshney, H. Weber, and W. Wright, Technical Report CS-1995-20, Department of Computer Science, Duke University, 1995.
407. “Range searching,” Technical Report CS-1996-05, Department of Computer Science, Duke University, 1996.
Selected Invited Talks
2019 Modeling and analyzing large geospatial data, Workshop on Data Science in Low-Dimensonal Spaces, Institute of Computational and Experimental Mathematics, Brown University, Providence, RI.
Algorithms for geometric similarity, Institute of Science and Technology, Vienna, Austria.
Stable Clustering, Tel Aviv University, Tel Aviv, Israel.
Flood-risk analysis on terrains, Keynote Talk at the Conference on Innovative Algorithms for Big Data, Research Institute of Mathematical Sciences, Kyoto, Japan.
2018 Improved dynamic geodesic nearest neighbor searching in a simple polygon, Tel Aviv University, Tel Aviv, Israel.
Algorithms for geometric similarity, University of Texas, Dallas, TX.
2017 An efficient approximation algorithm for Geometric transportation, Tel Aviv University, Tel Aviv, Israel.
Algorithms for geometric similarity, Symposium on Algorithms and Discrete Structures, St. John’s, Canada.
2016 An efficient algorithm for dynamic time warping between two curves, Tel Aviv University, Tel Aviv, Israel.
Shape Similarity, Workshop on Geometric Optimization, Shannon Village, Japan.
Range searching: From answering questions to questioning answers, The Mathematics of Jirˇ´ı Matousˇek, Prague, Czech Republic.
2015 Geometric hitting sets, Tel Aviv University, Tel Aviv, Israel.
Range searching: From answering questions to questioning answers, Distinguished Lecture Series, Department of Computer Science, Virginia Tech, VA.
2014 Range searching: Theory and Practice, Distinguished Lecture Series, Department of Computer Science, University of Minnesota, MN.
Arrangements, geometric optimization, and range searching, The Goodman-Pollack Fest/Feast, New York University, NY.
2013 Random racetracks, Workshop on Geometric Algorithms, Dagstuhl, Germany.
Range searching and its relatives, Workshop on Computational Geometry: Theory and Practice, Rio de Jeniro, Brazil.
Range searching and its relatives, Aarhus University, Aarhus, Denmark.
2012 Near-linear approximation algorithm for geometric bipartite matching, Bernoulli Conference on Discrete and Computational Geometry, EPFL, Lausanne, Switzerland.
Geometric arrangements and their applications, University of North Carolina, Greensboro, NC.
Geometric computing under uncertainty, Department of Mathematics, Duke University, Durham, NC.
Near-linear approximation algorithm for geometric bipartite matching, Tel Aviv University, Tel Aviv, Israel.
Semialgebraic range searching, Tel Aviv University, Tel Aviv, Israel.
I/O and geometry: Terrain modeling and analysis, Workshop on Memory Sensitive Algorithms, New York University, New York.
Geometric similarity, Workshop on Geometry and Learning (in conjunction with Twenty-Eighth Annual Symposium on Computational Geometry), Chapel Hill, NC.
Algorithms for geometric similarity, Canadian Conference on Computational Geometry, Prince Edward Island, Canada.
Query processing over uncertain data, Pennsylvania State University, State College, PA.
Scalable techniques for high-resolution geo-spatial data, Army Research Office Workshop on Human- Centric Computing with Collective Intelligence, Tempe, AZ.
Algorithms for geometric similarity, Georgia Tech, Atlanta, GA.
2011 STREAM: Processing massive terrain data sets, Hong Kong University of Science and Technology, Hong Kong.
Geometric hitting sets and independent sets, Hong Kong University of Science and Technology, Hong Kong.
STREAM: Processing massive terrain data sets, University of Sydney, Sydney, Australia.
Euclidean minimum weight matching: Old and new results, ETH, Zu¨ rich, Switzerland.
I/O efficient algorithms for answering contour queries, EPFL, Laussane, Switzerland.
I/O efficient algorithms for answering contour queries, Tel Aviv University, Tel Aviv, Israel.
Scalable simulation of forest dynamics, Conference on Biodiversity in the Silicon Age, Royal Danish Academy of Sciences and Letters, Copenhagen, Denmark.
Compact data structures for shortest paths, Workshop on Rcenet Progress in Robotics, San Francisco, CA.
Distributed summaries, Pennsylvania State University, State College, PA.
2010 STREAM: Processing massive terrain data sets, State University of New York, Buffalo, NY.
An odyssey through curved world: Arrangements, envelopes, and unions, Tel Aviv University, Tel Aviv, Israel.
Geometry in motion: KDS, arrangements, and core sets, Stanford University, Stanford, CA.
Geometry computation on uncertain data, Bernoulli Conference on Discrete and Computational Geometry, EPFL, Lausanne, Switzerland.
Geometric summaries: Coresets and beyond, Indian Institute of Sciences, Banglore, India.
STREAM: Processing massive terrain data sets, Indian Institute of Technology, New Delhi, India.
Four lectures on geometric data structures, Short course on Geometric Computing, New Delhi, India.
A geometry framework for network resilience analysis, Pennsylvania State University, State College, PA.
Coping with uncertain data: Range searching and skylines, Workshop on Geometric Computing, IMPECS, IIT Delhi, India.
STREAM: Processing massive terrain data sets, Indian Institute of Technology, Kanpur, India.
2009 Approximate Euclidean shortest paths amid convex obstacles, Courant Institute, New York.
Hitting set, ε-nets, and union of objects, Department of Mathematics, Duke University, Durham.
Approximate Euclidean shortest paths amid convex obstacles, Workshop on Geometric Algorithms, Dagstuhl, Germany.
Geometric summaries: Coresets and beyond, Workshop on Combinatorial and Computational Ge- ometry, Budapest, Hungary.
STREAM: Processing massive terrain data sets, ARO-ERDC Review Meeting, Construction Engi- neering Research Laboratory, Champaign, IL.
Exploiting geometry in sensor coverage and communication Pennsylvania State University, State College, PA.
STREAM: Processing massive terrain data sets, Department of Computer Science, Ohio State Uni- versity, Columbus, OH.
High dimensional core sets, Workshop on massive data sets, IIT, Kanpur, India.
2008 Computing contour maps and answering contour queries, Workshop on Data Structures, Dagstuhl, Germany.
Modeling and analyzing massive terrain data sets, Workshop on Algorithms for Modern Massive Data Sets, Stanford University, Stanford, CA.
Coping with geometry in urban sensor network design, Pennsylvania State University, State College, PA.
STREAM: Processing massive terrain data sets, ARO-ERDC Review Meeting, Topographic Engi- neering Center, Alexandria, VA.
2007 Core sets in the streaming model, Workshop on Computational Geometry, Dagstuhl, Germany.
Modeling and analyzing massive terrain data sets, Annual Symposium of Geometric Processing, Barcelona, Spain.
Modeling and analyzing large terrain data sets, University of Utah, Salt Lake City, UT.
Core sets: Old and new results, Hong Kong University of Science and Technology, Hong Kong.
Modeling and analyzing large terrain data sets, International Symposium on Algorithms and Computation, Sendai, Japan.
2006 I/O-efficient union-find with applications to terrain analysis, Workshop on Data Structures, Dagstuhl, Germany.
Comparing networks, Systems Biology Seminar, Duke University, Durham, NC.
Shape fitting using coresets, City University of New York, New York, NY.
I/O-efficient union-find with applications in terrain modeling, Tel Aviv University, Tel Aviv, Israel.
Geometric approximation via core sets, Workshop on Algorithms, Nachsholim, Israel.
Kinetic algorithms: Approximation and trade-offs, Discrete and Computational Geometry: Twenty Years Later, Snowbird, UT.
Flom elevation data to watershed hierarchy, Army Research Lab, Vicksburg, MS.
Core sets in the streaming model, Workshop on data streaming, IIT, Kanpur, India.
2005 Geometric approximation via core sets, Department of Computer Science, Stanford University, CA.
Modeling and analyzing massive terrain data, Army Research Lab, Vicksburg, MS. Modeling and analyzing massive terrain data, Army Research Lab, Aberdeen, MD. Coreset for the extent of shallow levels, ETH, Zu¨ rich, Switzerland.
Protein docking using elevation, 2nd Joint Meeting of AMS, DMV, O¨ MG, Mainz, Germany.
Modeling and analyzing massive terrain data, Topographic Engineering Center, Alexandria, VA.
2004 Querying moving points, Workshop on Dynamic Algorithms, Atlanta, GA.
Handling geometric data streams, Workshop on Data Structures, Dagstuhl, Germany.
Extreme elevations on a 2-manifold, AMS Meeting, Rider University, Lawrenceville, NJ.
Biology and Computation: Algorithms and Modeling, Frontiers in Biology, Duke University, Durhmam, NC.
Geometric approximation via core sets, Distinguished Lecture Series, University of Texas, Dallas, TX.
Efficient tradeoff schemes in data structures for querying moving objects, Workshop on Algorithms for Dynamic Data, Chennai, India.
2003 Hausdorff distance under translation for balls, Workshop on Computational Geometry, Dagstuhl, Germany.
Geometric approximation algorithms via core sets, European Conference on Computational Geome- try, Bonn, Germany.
Geometric clustering, University of Illinois, Urbana-Champaign, Illinois
Geometric approximation algorithms via core sets, Bell Labs, New Jersey Geometric approximation algorithms via core sets, Vienna Institute of Technology, Vienna
Geometric approximation algorithms via core sets, Hungarian Academy of Science, Budapest
Geometric approximation algorithms via core sets, Workshop on the Mathematical Foundations of Geometric Algorithms, MSRI, Berkeley, California
Geometric approximation algorithms via core sets, Computational Geometry Day, University of North Texas, Dentaon, Texas
2002 Range searching for moving points, Workshop on Data Structures, Dagstuhl, Germany.
Pseudo lines: Duality, algorithms, and applications, Max-Planck Institute, Saarbru¨ cken, Germany
Euclidean minimum-weight bipartite matching, Workshop on Geometric Graphs, DIMACS, New Jersey.
Data structures for moving objects, Distinguished Lecture Series, University of British Columbia, Vancouver, Canada.
2001 Data structures for moving objects, Distinguished Lecture Series, Ohio State University, Columbus, Ohio.
Data structures for moving objects, Aarlborg University, Aarlborg, Denmark.
Arrangements: Combinatorial and algorithmic applications, The Goodman-Pollack Two-Thirds-Of-A- Century Fest, Courant Institute, New York.
Data structures for moving objects, Workshop on Computational Geometry, Dagstuhl, Germany.
Algorithms and data structures for moving objects, Summer School on Dynamic Algorithms, Univer- sity of Paderborn, Paderborn, Germany.
On the number of congruent simplices in a point set, ETH, Zu¨ rich, Switzerland.
Range searching: A survey, Stanford University, Stanford.
Geometric clustering: A review, Stanford University, Stanford.
An efficient algorithm for fence design, University of California, Berkeley.
2000 Handling massive geo-spatial data, Army Research Office MURI Advisory Board, Duke University, Durham, North Carolina.
Efficient algorithms for geometric clustering: An overview, Tel Aviv University, Tel Aviv, Israel.
Maintaining approximate extent measures, Utrecht University, Utrecht, The Netherlands. Efficient algorithms for geometric clustering: An overview, INRIA, Sophia-Antipolis, France. Indexing moving objects, Max-Planck Institute, Saarbru¨ cken, Germany.
Geometric clustering problems: A review, NC State University, Raleigh, NC.
Efficient algorithms for geometric clustering: An overview, Computational Geometry Workshop, New Delhi, India.
1999 Pipes, cigars, and kreplach, Workshop on Computational Geometry, Dagstuhl, Germany.
Efficient techniques in geometric optimization: An overview, Israeli Workshop on Computational Geometry, Israel.
Approximate representation and topology, NSF Workshop on Computational Topology, Miami, Florida.
I/O-efficient dynamic point location, Workshop on Computational Cartography, Dagstuhl, Ger- many.
Efficient algorithms for clustering: An overview, University of North Carolina, Chapel Hill, North Carolina.
1998 On the complexity of the union of congruent cylinders, New York University, New York, New York.
Arrangements and their applications, Discrete Math Day, Carleton University, Ottawa, Canada.
On the complexity of the union of congruent cylinders, Workshop on Geometry and Combinatorics, Charles University, Prague, Czech Republic.
Handling massive geo-spatial data, Army Research Office MURI Advisory Board, Brown University, Providence, Rhode Island.
1997 Geometric techniques and applications, Army Research Office MURI Advisory Board, University of Pennsylvania, Philadelphia, Pennsylvania.
Binary space partitions, Workshop on Computational Geometry, Dagstuhl, Germany.
Binary space partitions: Old and new results, Computational Geometry Day, New York University, New York City, New York.
Binary space partitions: Old and new results, University of Warwick, Coventry, UK.
The discrete 2-center problem, Workshop on Efficient Algorithms, Mathematisches Forsch-ungsinstitut Oberwolfach, Germany.
1996 Algorithmic techniques and applications, Army Research Office MURI Advisory Board, Johns Hopkins University, Baltimore, Maryland.
Surface simplification problems, C. N. R., Pisa, Italy.
Surface simplification problems, E. T. H., Zu¨ rich, Switzerland.
Binary space partition for fat rectangles, Tel Aviv University, Tel Aviv, Israel.
On k-directional assembly, SIAM Conference on Discrete Mathematics, Baltimore, Maryland.
Curvature constrained motion planning, University of Rochester, Rochester, New York.
On k-directional assembly, Workshop on Hot Topics in Computational Geometry, Princeton University, Princeton, New Jersey.
Approximate shortest paths on a convex polytope, Computational Geometry: Ten Years Later, Mt. Holyoke, New Hampshire.
Binary space partition for fat rectangles, IBM Almaden, San Jose, California.
Approximate shortest paths on a convex polytope, 914th American Mathematical Society Meeting, Lawrenceville, New Jersey.
Surface simplification problems, Workshop on Computational Cartography, Dagstuhl, Germany.
1995 Randomized algorithms for some geometric optimization problems, Workshop on Computational Geometry, Dagstuhl, Germany.
Curvature constrained motion planning, Israeli Workshop on Computational Geometry, Eilat, Israel.
Curvature constrained motion planning, Technion, Haifa, Israel.
Approximation algorithms for surface simplification, Ionian Workshop on Geometry and Vision, Corfu, Greece.
1994 Computing many faces in arrangements of lines and segments, 892nd American Mathematical Society Meeting, Brooklyn, New York.
An approximation algorithm for surface reconstruction, University of Tokyo, Tokyo, Japan.
Minimum width annulus and related problems, Fourth International Workshop on Computational Geometry and Discrete Algorithms, Osaka, Japan.
Randomized algorithms for some geometric optimization problems, Ninth Mini-Conference on Discrete Mathematics, Clemson University, Clemson, South Carolina.
1993 Ray shooting among convex polytopes in 3D, New York University, New York City, New York.
Can visibility graphs be represented compactly, Workshop on Computational Geometry, Dagstuhl, Germany.
Can visibility graphs be represented compactly, Tel Aviv University, Tel Aviv, Israel.
Can visibility graphs be represented compactly, Charles University, Prague, Czech Republic.
Surface approximation and geometric partitions, Charles University, Prague, Czech Republic.
Computing many faces in arrangements of lines and segments, Utrecht University, Utrecht, The Netherlands.
Computing many faces in arrangements of lines and segments, Technion, Haifa, Israel.
Overlay of envelopes and their applications, Tel Aviv University, Tel Aviv, Israel
1992 Dynamic half-space range searching and its applications, Computational Geometry Day, New York City, New York University, New York.
1991 Counting circular arc intersections, New York University, New York City, New York.
1990 Applications of a new space partitioning technique, Computational Geometry Day, New York University, New York.
Partitioning arrangements of curves, DIMACS Workshop on Arrangements, Rutgers University, Piscataway, New Jersey.
1989 Spanning trees with low stabbing number, DIMACS Workshop on Geometric Complexity, Princeton University, Princeton, New Jersey.
Grants
|2019 |National Science Foundation, “NSF-BSF:AF:Small:Efficient Algorithms for Multi-Robot Multi- Criteria Optimal Motion Planning,” |
| |with D. Halperin (Israeli PI), $500,000 (pending). |
|2019 |National Science Foundation, “Collaborative Research:AF:Medium: Computing Fair Outcomes for Societal Decision Making,” with B.|
| |Fain, K. Munagala, and S. Suri, $1,200,000 (pending). |
|2018 |National Science Foundation, “III:Small:Durability queries in databases,” with J. Yang (PI), |
| |$500,000. |
2015 National Science Foundation, “A New Era of Discrete and Computational Geometry,” travel grant proposal, $26,000.
2015 National Science Foundation, BIGDATA:Collaborative Research:F:From Data geometries to information networks, with E. Cande`s, L. J. Guibas, and M. Maggioni (PI), $1,000,000.
2015 Army Research Office, “Geometric graphs for modeling and analyzing Large Geospatial Data,”
$ 424,000.
2014 National Science Foundation, “AF:Medium:Collaborative:Algorithmic foundations for trajectory collection analysis,” with L. J. Guibas and C. Tomasi, $ 1,200,000.
2014 National Science Foundation, “III: Medium: Collaborative Reserach: From answering questions to questioning answers (questions): Perturbation analysis for database queries,” with J. Yang (PI), J. Hamilton, and C. Li, $1,200,000.
2013 Army Research Office, STTR Phase I: Construction of 3D models from big data sets, with T. Mølhave, $150,000.
2013 National Science Foundation, “Algorithms for Geometric Optimization,” $32,000.
2013 US-Israel Binational Science Foundation, “Algorithms for Geometric Optimization,” with M. Sharir (PI), $120,000.
2011 National Science Foundation, “AF:Medium:Collaborative Research: Uncertainty Aware Geo- metric Computing,” With L. Guibas and S. Suri, $ 900,000.
2011 Army Research Office, “Algorithmic Challenges with Massive Data Sets,” with S. Babu, $39,700.
2010 National Science Foundation, “IGERT: Training program in wireless sensor networks (WISeNet),” with S. Ferari (PI), G. Katul, J. Albertson, R. Parr (and several other participating faculty),
$3,127,960.
2010 Army Research Laboratories, “Hierarchical representation of spatio-temporal data,” with J. Rogers, J. Shine, and A. Boedihardjo (PI), $ 850,000.
2010 National Science Foundation, “AF:Large:Collaborative: Compact representations and efficient algorithms for distributed geometric data,” with L. Guibas and P. Indyk, $ 1,300,000.
2009 National Science Foundation, “CDI-Type II: Integrating algorithmic and and stochastic modeling techniques for environmental prediction,” with J. S. Clark and A. Gelfand, $ 1,592,000.
2008 Army Research Office, “STREAM: Scalable techniques for high resolution elevation data analysis and modeling,” with H. Mitasova, $ 450,000.
2007 National Institute for General Medicine, “Duke Center for Systems Biology,” with P. Benfey (PI) and fifteen co-PIs, $14.5M.
2007 US-Israel Binational Science Foundation, “Arrangements in computational geometry and their applications,” with B. Aronov, J. Pach, and M. Sharir (PI), $142,000.
2007 National Science Foundation, “III-COR: Scalable Publish/Subscribe: Unifying Data Processing and Dissemination,” with J. Yang (PI), $450,000.
2007 Department of Education, “Doctoral Program in Management and Analysis of Large Data Acquired from Sensors,” with S. Babu, D. Bell, J. Chase, C. Ellis, J. Forbes, R. Lucic, J. Harer, R. Parr, C. Tomasi, $383,643.
2007 Army Research Office, Multidisciplinary Research Program of the University Research Initiative, subcontracted from Penn State University as a part of a $2,500,000 grant with participating institutions Penn State, Ohio State, and Harvard, $550,000.
2007 National Science Foundation, “Collaborative Research: Large-scale analysis of sensor-based geometric data,” $250,000.
2006 National Science Foundation, “DDDAS-TMRP: Dynamic sensor networks: Enabling the mea- surement, modeling, and prediction of biophysical changes in a landscape,” with J. Clark (PI), C. Ellis, K. Munagala, P. Flikkema, and J. Yang, $1,670,000.
2004 Army Research Office, “Modeling and analyzing terrain data acquired by modern mapping techniques,” with L. Arge and H. Mitasova, $450,000.
2003 National Science Foundation, “BDEI: Integration of data and models to assess forest diversity,” with J. Clark.
2003 US-Israel Binational Science Foundation, “Geometric arrangements and their applications,” with
B. Aronov, J. Pach, and M. Sharir (PI), $76,000.
2003 Army Research Office, “Real-time sensor networks,” with D. Brady (PI), X. Sun, J. Harer,
$1,650,831.
2002 National Science Foundation, Research Experience for Undergraduate Supplement, $10,000. 2002 National Science Foundation, “ECS: Distributed multiscale geometric processing on real-time
sensor networks and radiation fields,” with D. Brady (PI), J. Harer, and X. Sun, $150,000.
2002 National Science Foundation, “Collaborative proposal: Motion – models, algorithms, and complexity,” CCR-02-04118, $255,000.
2001 National Science Foundation, “BDEI: Computation and uncertainty in ecological forecasting,” with J. Clark (PI) and M. Lavine, EIA-01-31905, $93,200.
2000 National Science Foundation, “Computational geometry for structural biology and bioinfor- matics,” CCR-00-86013, with H. Edelsbrunner (PI), L. J. Guibas, H. Hellinga, J.-C. Latombe, M. Levitt, F. P. Brooks, C. W. Carter, J. S. Snoeyink, and S. Bililigen, $7,200,000.
2000 Army Research office, “Algorithmic issues in modeling motion,” DAAD19-00-1-0478, with L. J. Guibas, $5,000.
2000 National Science Foundation, “Algorithmic issues in modeling motion,” CCR-00-83-033, with L. J. Guibas, $25,000.
1999 National Science Foundation, “Duke mathematics program for vertically integrated, interdisci- plinary research,” with the Duke Math Department.
1999 Los Alamos Research Laboratory, “Models and algorithms for several levels of memory,” with L. Arge and J. S. Vitter, $50,000.
1999 National Science Foundation, Research Experience for Undergraduate Supplement, $5000. 1999 National Science Foundation, “Data-intensive computing with spatial models,” with J. Chase
(PI), L. Arge, H. Edelsbrunner, C. Ellis, A. Lebeck, and A. Vahdat, EIA-9972879, $2,300,000.
1998 US Department of Education, “Graduate assistance in areas of national need for fellowships in experimental computer science,” with C. Ellis, L. Arge, O. Astrachan, J. Chase, G. Kedem, A. Lebeck, M. Littman, J. S. Vitter (PI), $500,000.
1998 National Science Foundation, “Geographic information systems on high-speed clusters: A vertically integrated approach,” with L. Arge, J. Chase (PI), P. Halpin, D. Urban, and J. S. Vitter, EIA–9870724, $771,082.
|1998 |National Science Foundation, “Simple and efficient geometric algorithms and their applications,” CCR–9732787, $237,609. |
|1998 |US-Israeli Binational Science Foundation Grant, “Arrangements and their applications in com- putational geometry,” with B. |
| |Aronov, J. Pach, and M. Sharir (PI), $78,000. |
|1997 |National Science Foundation, Research Experience for Undergraduate Supplement $5,000. |
|1997 |National Science Foundation, NYI Matching Funds, $17,500. |
|1997 |National Science Foundation, International Cooperative Activities, “Efficient and applicable geometric Algorithms,” $33,653. |
|1996 |National Science Foundation, Research Experience for Undergraduate Supplement, $5,000. |
|1996 |National Science Foundation, “Curious: Center for undergraduate education and research: Integration through performance and |
| |visualization,” (Co-PI with O. Astrachan, A. Biermann, G. Kedem, A. Lebeck, J. Reif, S. Rodger, D. Rose, X. Sun, and J. S. |
| |Vitter), $405,200. |
|1996 |National Science Foundation, NYI Matching Funds, $25,000. |
|1996 |Alfred P. Sloan Fellow, $35,000. |
|1995 |Army Research Office, Multidisciplinary Research Program of the University Research Initiative (Co-PI with J. S. Vitter), |
| |subcontracted from Center for Geometric Computation at Brown University as a part of a $4,500,000 grant with participating |
| |institutions Brown, Duke, and Johns Hopkins Universities, $1,500,000 (including two option years). |
|1995 |US-Israeli Binational Science Foundation Grant (Co-PI with B. Aronov, L. Guibas, and M. Sharir), |
| |$79,500. |
|1994 |Xerox Corporation, NYI Matching Funds, $22,500. |
|1994 |National Science Foundation, NYI Matching Funds, $22,500. |
|1993 |National Science Foundation Grant, CCR–93–01259, $70,000. |
|1993 |National Science Foundation Grant (NYI), CCR–93–57814, $125,000. |
|1991 |National Science Foundation Grant, CCR–91–06514, $38,617. |
Editorial Activities
2017– Member, Editorial Board, ACM Book Series. 2014–17 Member, Editorial Board, Geoinformatica.
2009–19 Member, Editorial Board, SIAM Journal on Computing. 2007–15 Member, Editorial Board, ACM Transactions on Algorithms.
2003 Guest Co-Editor, Computational Geometry: Theory and Applications 24 (2), special issue for the
Fourth CGC Workshop on Computational Geometry.
2000–01 Guest Editor, Discrete and Computational Geometry 26 (2001), special issue for the Proceedings Sixteenth Annual Symposium on Computational Geometry.
2000–01 Guest Co-Editor, Discrete and Computational Geometry 25 (2001), special issue for the Sharir Fest. 2000–10 Member, Editorial Board, International Journal of Computational Geometry and Applications.
1999 Guest Editor, International Journal of Computational Geometry and Applications 9 (4& 5), special issue for the First CGC Workshop on Computational Geometry.
1999 Guest Co-Editor, Journal of Computer and System Sciences 58 (2), special issue for Proceedings Thirty Sixth Annual IEEE Symposium on Foundations of Computer Science.
1999– Member, Editorial Board, Computational Geometry: Theory and Applications.
1998–2010 Member, Editorial Board, ORDER, The Journal on the Theory of Ordered Sets and Its Applications.
1997– Member, Editorial Board, Discrete and Computational Geometry.
1994–2000 Member, Editorial Board, Chicago Journal of Theoretical Computer Science.
Professional Activities
|2019 |Member, External Review Committee, Department of Computer Science, Rice University. |
|2019 |Senior Member, Program Committee, Twenty-Seventh ACM SIGSPATIAL International Conference on Advances in Geographic Information|
| |Systems, Chicago, IL. |
|2018-19 |Co-Organizer (with B. Aronov and E. Ezra), Workshop on Algebraic Methods in Discrete and Computational Geometry, Portland, OR.|
|2018 |Senior Member, Program Committee, Twenty-Sixth ACM SIGSPATIAL International Conference on Advances in Geographic Information |
| |Systems, Seattle, WA. |
|2017-18 |Member, Program Committee, Forty-Fourth Annual IEEE International Conference on Very Large Databases, Rio de Janeiro, Brazil. |
|2017 |Senior Member, Program Committee, Twenty-Fifth ACM SIGSPATIAL International Conference on Advances in Geographic Information |
| |Systems, Los Angeles, CA. |
|2017 |Member, Program Committee, Forty-Fourth International Colloquium on Automata, Languages, and Programming, Warsaw, Poland. |
|2016-17 |Member, Program Committee, Twenty Seventh Annual ACM-SIAM Symposium on Discrete Algo- rithms, San Diego, CA. |
|2016 |Member, Program Committee, Twelfth Workshop on Algorithmic Foundations of Robotics, San Francisco, CA. |
|2016 |Member, Program Committee, Twenty-Fourth ACM SIGSPATIAL International Conference on Advances in Geographic Information |
| |Systems, San Francisco, CA. |
|2015-16 |Co-organizer, Conference on A New Era of Discrete and Computational Geometry, Ascona, Switzer- land. |
|2015-16 |Member, Program Committee, Thirty-Fifth Annual Symposium on Principles of Database Systems, San Francisco, CA. |
|2015 |Member, Program Committee, Twenty-Third ACM SIGSPATIAL International Conference on Ad- vances in Geographic Information |
| |Systems, Seattle, WA. |
|2015 |Member, Program Committee, Eleventh IEEE International Conference on Distributed Computing in Sensor Systems, Cambridge, MA. |
|2014 |Member, Senior Program Committee, Twenty-Second ACM SIGSPATIAL International Conference on Advances in Geographic |
| |Information Systems, Dallas, TX. |
2014 Member, Program Committee, Twenty Fourth Annual ACM-SIAM Symposium on Discrete Algo- rithms, San Diego, CA.
2014 Member, Program Committee, Eighteenth International Conference on Database Theory, Brussels, Belgium.
2013-14 Member, Program Committee, Forty-First International Colloquium on Automata, Languages, and Programming, Copenhagen, Denmark.
2013-14 Member, Program Committee, 2014 ACM SIGMOD International Conference on Management of Data, Snowbird, UT.
2013 Member, Program Committee, Twenty-Fourth Annual International Symposium on Algorithms and Computation, Hong Kong.
2013 Member, Program Committee, MASSIVE 2013: Third Workshop on Massive Data Algorithmics, Sophia Antipolis, France.
2012-13 Member, Program Committee, Ninth IEEE International Conference on Distributed Computing in Sensor Systems, Cambridge, MA.
2011-12 Co-Organizer (with S. Babu and S. Muthukrishnan), Workshop on Big Data at Large: Applications and Algorithms, Durham, NC.
2011-12 Member, Review And Site-Visit Panel for Institute of Theoretical Computer Science, Simons Founda- tion, New York, NY.
2011-12 Member, Program Committee, Twenty-Eighth Annual Symposium on Computational Geometry, Chapell Hill, NC.
2011 Member, Program Committee, MASSIVE 2011: Third Workshop on Massive Data Algorithmics, Paris.
2010-11 Co-Organizer (with K. Mehlhorn and M. Teillaud), Workshop on Computational Geometry, Dagstuhl, Germany.
2010-11 Member, Program Committee, Seventh IEEE International Conference on Distributed Computing in Sensor Systems, Barcelona, Spain.
2010 Co-Organizer (with N. Garg and S. Sen), School on Geometric Computing, IIT Delhi, India.
2010 Co-Organizer (with M. Sagaroff and S. Sen), Workshop on Geometric Computing, IIT Delhi, India. 2010– Member, Steering Committee, International Conference on Theory and Practice of Algorithms in
(Computer) Systems.
2010– Member, Advisory Board, Center for Education Initiative, Japan Institute of Science and Technol- ogy, Japan.
2010 Member, Program Committee, MASSIVE 2010 : Second Workshop on Massive Data Algorithmics, Salt Lake City, UT.
2009–10 Member, Program Committee, Twenty-Ninth Annual Symposium on Principles of Database Systems, Indianapolis, IN.
2009–10 Member, Program Committee, Twelfth Scandinavian Symposium on Algorithm Theory, Bergen, Norway.
2009 Member, Program Committee, MASSIVE 2009 : First Workshop on Massive Data Algorithmics, Aarhus University, Denmark.
2009– Member, Advisory Board, MADALGO, Aarhus University, Denmark.
2008-09 Co-Organizer (with H. Alt and M. Teillaud), Workshop on Computational Geometry, Dagstuhl, Germany.
2008–09 Member, Program Committee, Fifth IEEE International Conference on Distributed Computing in Sensor Systems, Marina Del Rey, Spain.
2006–09 Member, Computational Geometry Steering Committee.
2006–11 Member, Advisor Board, Max Planck Institute, Saarbru¨ cken, Germany.
2006–10 Member, Advisory Board, Department of Computer Science, Virginia Tech, Blacksburg, VA.
2006 External Reviewer, Department of Computer Science, The University of Warwick, Coventry, UK. 2006 External Reviewer, Graduate Program of City University of New York, New York.
2006 Member, Program Committee, Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana.
2006 Member, Program Committee, Robotics: Science and Systems.
2006-07 Organizer, Workshop on Computational Geometry, Dagstuhl, Germany.
2006 Member, Video Program Committee, Twenty Second Annual Symposium on Computational Geometry, Sedona, AZ.
2005–06 Member, Program Committee, Tenth Scandinavian Symposium on Algorithm Theory, Riga, Latvia. 2005–06 Member, Program Committee, Proceedings Fourteenth European Symposium on Algorithms, Zu¨ rich,
Switzerland.
2005–06 Member, Program Committee, Twenty-Fifth Annual Symposium on Principles of Database Systems, Chicago, IL.
2005 Member, Program Committee, Workshop on Algorithms in Bioinformatics, Mallorca, Spain.
2005 Member, National Institute of Health, Work Study Group for National Center on Bioinformatics, Bethesda, MD.
2004–05 Member, Program Committee, Ninth Symposium on Algorithms and Data Structures, Waterloo, Canada.
2004 Co-Organizer, Workshop on Dynamic Algorithms, Chennai, India. 2004 Co-Organizer, Workshop on BioGeometry, Brooklyn, NY.
2004 Member, Program Committee, Workshop on Algorithms in Bioinformatics, Bergen, Norway.
2003–06 Chair, Computational Geometry Steering Committee.
2003 Co-Organizer, Workshop on the Mathematical Foundations of Geometric Algorithms, MSRI, Berkeley, CA.
2002 Member, National Science Foundation Review Panel.
2002 Member, Program Committee, Fifth Workshop on Discrete Algorithms for Mobile Computing, Atlanta, GA.
2002 Member, Program Committee, Fifth Workshop on Algorithmic Foundations of Robotics, Nice, France.
2002-03 Organizer, DIMACS Workshop on Geometric Optimization, Rutgers University, New Brunsewick, NJ.
2002 Organizer, DIMACS Workshop on Modeling Motion, Rutgers University, New Brunsewick, NJ.
2001-02 Member, Program Committee, Thirty Fourth Annual ACM Symposium on Theory of Computing, Quebec City, Quebec.
2001-02 Member, Program Committee, Eighteenth Annual Symposium on Computational Geometry, Barcelona, Spain.
2001 Member, Program Committee, Sixth CGC Workshop on Computational Geometry, Polytech Univer- sity, Brooklyn.
2001 Member, Program Committee, Proceedings Ninth European Symposium on Algorithms, Aarhus, Denmark.
2000 Member, Program Committee, Fifth CGC Workshop on Computational Geometry, StonyBrook, StonyBrook.
2000 Organizer, Computational Geometry Workshop, New Delhi, India.
2000 Organizer, Workshop on Algorithmic Issues in Modeling Motion, Durham, NC. 2000 Organizer, Computational Geometry Workshop: Sharir Fest, Hong Kong.
2000 Member, Program Committee, Twentieth Annual Conference on Foundations of Software Technology and Theoretical Computer Science, New Delhi, India.
1999–01 General Secretary and Member, Computational Geometry Steering Committee. 1999–00 Program Chair, Sixteenth Annual Symposium on Computational Geometry, Hong Kong.
1999 Member, Program Committee, Fourth CGC Workshop on Computational Geometry, Baltimore, MD.
1999 Member, Program Committee, Fourth Workshop on Algorithmic Foundations of Robotics, Dartmouth, New Hampshire.
1999 Member, National Science Foundation Review Panel.
1999 Member, Program Committee, Fifteenth Annual Symposium on Computational Geometry, Miami, FL.
1998–04 Member, Steering Committee, Workshop on Algorithmic Foundations of Robotics.
1998 Member, Program Committee, Third CGC Workshop on Computational Geometry, Providence, RI. 1998 Member, Program Committee, Third Workshop on Randomized Parallel Computing, Orlando, FL. 1998 Program Chair and Co-Organizer, Third Workshop on Algorithmic Foundations of Robotics, Houston,
TX.
1997 Organizer, Second CGC Workshop on Computational Geometry, Durham, NC.
1996 Member, Program Committee, First CGC Workshop on Computational Geometry, Baltimore, MD. 1996 Member, Computational Geometry Working Group at ACM Workshop on Strategic Directions in
Computing Research, Massachusetts Institute of Technology, Cambridge, MA.
1996 Member, National Science Foundation Review Panel.
1996 Member, Program Committee, Twelfth Annual Symposium on Computational Geometry, Philadel- phia, PA.
1995 Member, Program Committee, Thirty Sixth Annual IEEE Symposium on Foundations of Computer Science, Milwaukee, WI.
1994 Member, Program Committee, Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA.
1993 Co-Organizer, Workshop on Computational Geometry, Raleigh, NC.
1992 Member, Program Committee, Eighth Annual Symposium on Computational Geometry, Berlin, Germany.
1989– Reviewed books for Addison Welsley, Cambridge University Press, McGraw Hill.
1989– Reviewed proposals for National Science Foundation, Army Research Office, Israeli Science Foundation, US-Israeli Binational Science Foundation, Hong Kong Research Grant Council, National Science and Engineering Research Council (Canada), and Office of Naval Research.
1986– Refereed papers for various journals and conferences including ACM Computing Surveys, ACM Symposium on Computational Geometry, ACM Symposium on Computational Learning Theory, ACM- SIAM Symposium on Discrete Algorithms, ACM Symposium on Management of Data, ACM Symposium on Principles of Database Systems, ACM Symposium on Theory of Computing, ACM Transactions on Graphics, Algorithmica, Applied Mathematics Letters, Combinatorica, Computational Geometry: Theory and Applications, Computer, Computers and Mathematics with Applications, Discrete and Applied Mathematics, Discrete and Computational Geometry, Discrete Mathematics, European Symposium of Algorithms, Foundations of Software Technology and Theoretical Computer Science, GeoInformatica, IEEE Conference on Very Large Database Systems, IEEE Symposium on Foundations of Computer Science, IEEE Transactions on Circuits Design, IEEE Transactions on Knowledge and Data Engineering, IEEE Transactions on Pattern Analysis and Machine Intelligence, IEEE Transactions on Robotics and Automation, Information Processing Letters, International Journal on Computational Geometry and Applications, International Journal of Computing, International Journal of GIS, Journal of the ACM, Journal of Algorithms, Journal of Combinatorial Theory, Journal of Computer and System Sciences, Location Science, Networks, ORSA Journal on Computing, Scandinavian Workshop on Algorithm Theory, SIAM Journal on Computing, SIAM Journal on Discrete Mathematics, SIGGRAPH, Theoretical Computer Science, Workshop on Algorithms and Data Structures.
Professional Affiliations
2014– American Association for the Advancement of Science. 2000– ACM Special Interest Group on Management of Data. 1999– Institute of Electrical and Electronics Engineering.
1996–2012 Society of Industrial and Applied Mathematics. 1995–2000 ACM Special Interest Group on Graphics.
1991– ACM Special Interest Group on Algorithms and Computation Theory. 1991– Association of Computing Machinery.
Service to the University
2019 Member, Undergraduate Quality Enhancement Plan (QEP) Committee.
2017–20 Ex-officio Member, Departmental Committees (nine), Department of Computer Science. 2016-17 Member, Ad hoc Undegraduate Program Committee, Department of Computer Science.
2016-17 Member, Ad hoc Faculty Search Committee, Department of Computer Science.
2016 Member, Ad hoc Reappointment Review Committee (Debmalya Panigrahi), Department of Computer Science.
2015-16 Chair, Ad hoc Faculty Search Committee, Department of Computer Science.
2015 Chair, Ad hoc Reappointment Review Committee (Owen Astrachan), Department of Computer Science.
2015 Chair, Ad hoc Promotion Review Committee (Kamesh Munagala), Department of Computer Science.
2014-16 Member, Ad hoc MS Exam Committee, Department of Computer Science.
2014-15 Chair, Ad hoc Graduate Program Committee, Department of Computer Science. 2014–17 Member, Arts and Sciences Distinguished Professors Committee.
2014–17 Member, Academics Priority Committee.
2014–17 Member, Arts and Sciences Budget Advisory Committee.
2013-14 Member, Ad hoc Graduate Admissions Committee, Department of Computer Science. 2012-15 Member, University Grievance and Harassment Board.
2012-13 Chair, Ad hoc Graduate Program Committee, Department of Computer Science. 2012 Chair, Ad hoc Promotion Review Committee, Department of Computer Science.
2011-12 Chair, Ad hoc Reappointment Review Committee for the Dean of Engineering. 2011–12 Member, Faculty Search Committee, Department of Computer Science.
2011 Chair, Ad hoc Tenure Review Committee, Department of Computer Science.
2009–10 Member, Provost Blue-Sky-Dinner Planning Committee. 2007-08 Member, A&S Senior Associate Dean Search Committee.
2007–09 Member, University Corporate Relations Executive Committee. 2005–06 Chair, Ad hoc A&S Committee for Integration Across Scale in Sciences.
2004–10 Ex-officio Member, Departmental Committees (eight), Department of Computer Science. 2004–10 Chair, Executive Committee, Department of Computer Science.
2004–05 Chair, Ad hoc Committee for Future Directions of Center of Bioinformatics and Computational Biology.
2002–03 Chair, Ad hoc Committee for Strategic Planning, Department of Computer Science. 2002–03 Member, Academic Priorities Committee.
2001–02 Member, Faculty Search Committee, Department of Computer Science.
2001–04 Member, Steering Committee, Center for Bioinformatics and Computational Biology.
2000–01 Member, Search Committee, Director of the Center for Bioinformatics and Computational Biology.
2000-01 Member, Science and Engineering Advisory Committee.
2000–04 Member, Global Change Initiative Steering and Executive Committees.
2000 Chair, Tenure Review Committee, Department of Computer Science.
1999–00 Member, Faculty Search Committee, Department of Computer Science. 1998–99 Chair, Faculty Search Committee, Department of Computer Science.
1998– Member, Space Allocation Committee, Department of Computer Science. 1997–98 Member, Faculty Search Committee, Department of Computer Science. 1997–04 Member, Teaching Assistants Committee, Department of Computer Science. 1997–98 Chair, Graduate Recruiting Committee, Department of Computer Science. 1996–98 Colloquium Chair, Department of Computer Science.
1996–99 Member, Undergraduate Curriculum Committee, Department of Computer Science. 1996–2002 Member, Industrial Partners Program Committee, Department of Computer Science.
1994–96 Member, University Ethics Committee.
1994–99 Member, Graduate Admissions Committee, Department of Computer Science. 1993–94 Member, Faculty Search Committee, Department of Computer Science.
1993 Colloquium Chair, Department of Computer Science.
1993 Member, Ad hoc Graduate Curriculum Committee, Department of Computer Science. 1992 Member, Ad hoc Prelim Exam Revision Committee, Department of Computer Science.
1991–93 Member, Graduate Admissions Committee, Department of Computer Science. 1991–94 Member, Qualifying Exam Committee, Department of Computer Science.
Teaching
|2019 |Design and Analysis of Algorithms, COMPSCI 532 (Fall). |
|2018 |Geometric Algorithms, COMPSCI/CBB 634 (Fall). |
|2016 |Geometric Algorithms, COMPSCI/CBB 634 (Spring). Design and Analysis of |
| |Algorithms, COMPSCI 532 (Fall). |
|2015 |Complexity Theory, COMPSCI 296 (Spring). |
| |Design and Analysis of Algorithms, COMPSCI 330 (Fall). |
|2014 |Geometric Algorithms, COMPSCI/CBB 634 (Spring). Design and Analysis of |
| |Algorithms, COMPSCI 532 (Fall). |
|2013 |Design and Analysis of Algorithms, COMPSCI 330 (Spring). Applied Algorithms, |
| |COMPSCI 590 (Spring). |
|2012 |Design and Analysis of Algorithms, CPS 130 (Spring). Design and Analysis of |
| |Algorithms, COMPSCI 530 (Fall). |
|2011 |Computational Geometry, CPS/CBB 234 (Fall). |
|2010 |Geometric Algorithms, CSL 852 (IIT Delhi) (co-taught with Sandeep Sen.) |
|2009 |Design and Analysis of Algorithms, CPS 230 (Fall). |
|2008 |Computational Geometry, CPS 234 (Fall). |
|2007 |Geometric Optimization, CPS 296 (Spring). |
|2005 |Computational Geometry, CPS 234 (Fall). |
|2004 |Shape Analysis, CPS 296 (Spring). |
|2003 |Computational Complexity, CPS 240 (Spring). |
| |Algorithms in Computational Biology, CPS260/BGT204 (Fall). |
|2002 |Ecological Forecasting, CPS 296 (Spring) |
| |(jointly with J. Clark, M. Lavine, and D. Urban). |
|2001 |Computational Complexity, CPS 240 (Spring). |
|2000 |Randomized Algorithms, CPS 237 (Spring). Introduction to Computer Graphics, CPS 124, 296|
| |(Fall). |
|1999 |Computational Complexity, CPS 240 (Spring). Computational Geometry, CPS 234 (Spring) |
| |(jointly with Julien Basch). |
| |Introduction to Computer Graphics, CPS 124, 296 (Fall). |
|1998 |Randomized Algorithms, CPS 237 (Spring). Introduction to Computer Graphics, CPS 124, 296|
| |(Fall). |
|1997 |Computational Geometry, CPS 234 (Spring). Introduction to Computer Graphics, CPS 196, |
| |296 (Fall). |
|1996 |Computational Complexity, CPS 240 (Spring). Analysis of Algorithms, CPS 130 (Fall). |
|1995 |Computational Complexity, CPS 240 (Spring). Randomized Algorithms, CPS 296 (Fall). |
|1994 |Formal Languages and Theory of Computation CPS 225 (Spring). Computational Complexity, |
| |CPS 265 (Spring). |
| |Computational Geometry, CPS 234 (Fall). |
|1993 |Computational Geometry, CPS 240 (Spring). |
|1992 |Program Analysis and Data Structures, CPS 103 (Spring). Design and Analysis of |
| |Algorithms, CPS 205 (Fall). |
|1991 |Computational Geometry, CPS 265 (Spring). Design and Analysis of Algorithms, CPS 224 |
| |(Fall). |
|1990 |Program Analysis and Data Structures, CPS 102 (Fall). |
II. Postdoctoral Assistants
Lars Arge, Julien Basch, Hsien-Chih Chang, Jeff Erickson, Esther Ezra, Kyle Fox, Sathish Govin- drajan, Sariel Har-Peled, Xiao Hu, Thomas Mølhave, Jeff Phillips, Bardia Sadri, Swaminathan Sankararaman, and Hai Yu.
Dissertation Supervision
1993– PhD supervisor for Anne Collins (with J. Harer) (2002), Andrew Danner (with L. Arge) (2006), Pavan K. Desikan (2000), Sathish Govindrajan (2004), Shashidhar Ganjugunte (2011), Aaron Lowe (2021), Nabil Mustafa (2004), Abhinandan Nath (2018), Jiangwei Pan (2016), Salman Parsa (with H. Edelsbrunner) (2014), Jeff Phillips (2009), Cecilia M. Procopiuc (2001), Sharath Kumar Raghvendra (2012), Stavros Sintos (expected 2020), Alex Steiger (expected 2022), Erin Taylor (expected 2023), Kasturi R. Varadarajan (1998), Yusu Wang (2004), Allen Xiao (expected 2020), Ke Yi (2006), Albert Yu (2014), Hai Yu (2006), You Wu (with J. Yang; 2015), Wuzhou Zhang (2015).
1993– MS supervisor for Sukhendu Chakraborty (2006), Stacey Luoma (with J. S. Vitter) (1999), Hangjun Xu (2014).
1998– BS supervisor for Ben Berg (2013), Alex Beutel (2011), Till Brenner (1999), Patrick Chan (2008),
Jeremy Fox (2017), Ethan Yong-Hui Goh (2012), Meetesh Karia (2000), Niel Lebeck (2014),
Michael Strauss (2001), Erin Taylor (2018), John Tran (2003), William Victor (2016), Afanasiy
Yermakov (2013), Rex Ying (2016).
Dissertation Committees
1990– PhD committee member for Mohammad A. Abam (TU, Eindhoven), Deganit Armon, Andrew Bahn (Biochemistry), Rakesh Barve, Robert-Paul Berrety (Utrecht University), Allister Bernard, Karl Bringmann (MPI, Saarbru¨ cken), Cassandra Carley, Michael Casey (Mathematics), Tim Culver (UNC Chapel Hill), Sergio Cabello (Utrecht University), Sergej Deutsch (ECE), Michael Dietze (Biology), Stacey Doyle, Junyang Gao, Xin Guo, Ankur Gupta, Samuel Haney, Hao He, Riko Jacobs (University of Aarhus), Jonathan Jou, Nathaniel Kell, John Keyser (UNC Chapel Hill), Shankar Krishnan (UNC Chapel Hill), Manish Malhotra, Jeff Martin, Dmitriy Morazov, T. M. Murali (Brown University), A. Nagchaudhuri (Mechanical Engineering), Vijay Natarajan, Apostel Natsev, Chikai Ohazama (Biomedical Engineering), Ergys Ristani, Octavian Procopiuc, Hai Shao, Betinna Speckmann (University of British Columbia), Kevin Sun, Zheng Sun, Chittranjan Tripathy, Li Tong, Laura Tuoma, Gokul Vardhan (UNC Chapel Hill), Amitabh Varshney (UNC Chapel Hill), Brett Walenz, Bei Wang, Hongyan Wang, Min Wang, Michael Wolosin (Ecology), Junyi Xie, Peng Yin, Akeshi Yoshida, Guoxian Zhang (MEMS), Yi Zhang.
1990– MS committee member for Yujuan Bao, Patrick Harubin, Akeshi Yoshida, Yuhao Wen, and Guangwei Yuan.
Undergraduate Students
Leslie Anderson (summer intern, Spellman College), Nada Basit (summer intern, Mary Wash- ington College), Mark Bauman, Ben Berg, Alex Beutel, Trill Brenner, Patrick Chan, Alexander Chrisman, John Clyde, Donald Flood, Jeremy Fox, John Hack, Meetesh Karia, Alexander Karwait, Niel Lebeck, Ibrahima Mbaye (summer intern, NC A&T), Bret McMillan, Neill Occhiogrosso, Jay Steele, John Tran, Michael Strauss, Erin Taylor, William Victor, David Winslow, Afanasiy Yermakov, and Rex Ying.
-----------------------
10
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- seton institute of reconstructive surgery
- michigan institute of real estate classes
- sports institute of tucson
- institute of physics iop
- institute of physics uk
- american institute of physics
- american institute of physics citation
- american institute of physics inc
- chicago institute of plastic surgery
- indian institute of public health
- nigerian institute of international affairs
- eric institute of education science