Publications of Pankaj K. Agarwal    :chronological  alphabetical  combined  bibtex listing:

Books

1. P.K. Agarwal, Robotics: The Algorithmic Perspective, edited by L. Kavraki and M. Mason (1998), A. K. Peters, Wellesley
2. M. Sharir and P.K. Agarwal, Davenport-Schinzel Sequences and Their Geometric Applications (1995), Cambridge University Press, Cambridge-New York-Melbourne
3. J. Pach and P.K. Agarwal, Combinatorial Geometry (1995), John Wiley and Sons, New York
4. P. K. Agarwal, Intersection and Decomposition Algorithms for Planar Arrangements, (1991), Cambridge University Press, Cambridge-New York-Melbourne

Papers Published

1. Agarwal, PK; Aronov, B; Ezra, E; Katz, MJ; Sharir, M, Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems, ACM Transactions on Algorithms, vol. 21 no. 3 (June, 2025) [doi]  [abs]
2. Agarwal, PK; Har-Peled, S, Computing Instance-Optimal Kernels in Two Dimensions, Discrete and Computational Geometry, vol. 73 no. 3 (April, 2025), pp. 674-701 [doi]  [abs]
3. Comendul, A; Ruf-Zamojski, F; Ford, CT; Agarwal, P; Zaslavsky, E; Nudelman, G; Hariharan, M; Rubenstein, A; Pincas, H; Nair, VD; Michaleas, AM; Fremont-Smith, PD; Ricke, DO; Sealfon, SC; Woods, CW; Claypool, KT; Jaimes, R, Comprehensive guide for epigenetics and transcriptomics data quality control., STAR Protoc, vol. 6 no. 1 (March, 2025), pp. 103607 [doi]  [abs]
4. Agarwal, PK; Aronov, B; Geft, T; Halperin, D, On Two-Handed Planar Assembly Partitioning with Connectivity Constraints, ACM Transactions on Algorithms, vol. 21 no. 2 (March, 2025) [doi]  [abs]
5. Agarwal, PK; Ezra, E, Line Intersection Searching Amid Unit Balls in 3-Space, Algorithmica, vol. 87 no. 2 (February, 2025), pp. 223-241 [doi]  [abs]
6. Agarwal, PK; Ezra, E; Sharir, M, Semi-Algebraic Off-line Range Searching and Biclique Partitions in the Plane, Discrete and Computational Geometry (January, 2025) [doi]  [abs]
7. Agarwal, PK; Katz, MJ; Sharir, M, On reverse shortest paths in geometric proximity graphs, Computational Geometry Theory and Applications, vol. 117 (February, 2024) [doi]  [abs]
8. Agarwal, PK; Geft, T; Halperin, D; Taylor, E, Multi-robot motion planning for unit discs with revolving areas, Computational Geometry Theory and Applications, vol. 114 (October, 2023) [doi]  [abs]
9. Agarwal, PK; Cohen, R; Halperin, D; Mulzer, W, Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead, ACM Transactions on Algorithms, vol. 18 no. 3 (October, 2022) [doi]  [abs]
10. P.K. Agarwal,, Reporting all intersecting pairs of polytopes in two and three dimensions (2004)  [abs]
11. P.K. Agarwal, C. M. Procopiuc, and S. Har-Peled, STAR-tree: An efficent self-adjusting index for moving points, in Fourth Workshop on Algorithms Engineering and Experiments (2002)
12. P.K. Agarwal, C. M. Procopiuc, M. Jones, and T.M. Murali, Classifcation using projective clustering, ACM SIGMOD International Conference on Management of Data (2002)
13. L. Guibas, J. Hershberger, E. Veach, and P.K. Agarwal, Maintaining structures for moving points, Discrete and Computational Geometry, vol. 26 (2001), pp. 253-374
14. K. R. Varadarajan and P.K. Agarwal, Approximating shortest paths on polyhedral terrains, SIAM Journal on Computing, vol. 30 (2001), pp. 1321-1340
15. H. Wang and P.K. Agarwal, Approximation algorithms for shortest paths with bounded curvature, SIAM Journal on Computing, vol. 30 (2001), pp. 1739-1772
16. J. Basch, L. J. Guibas, J. Hershberger, L. Zhang and P.K. Agarwal, Deformable free space tiling for kinetic collision detection, in Algorithmic Foundations of Robotics, edited by B. Donald, K. Lynch, and D. Russ (2001), pp. 83-96, A.K. Peters, Natick, MA,
17. S. Sen and P.K. Agarwal, Randomized algorithms for geometric optimization, in Handbook of Randomized Computation, edited by J. Pardalos, S. Rajasekaran, J. Reif, and J. Rolim (2001), pp. 151-201, Kluwar Academic Press, The Netherlands
18. P.K. Agarwal, L. Arge and J. Vahrenhold, Time responsive indexing schemes for moving points, in Seventh Workshop on Algorithms and Data Structures (2001)
19. P.K. Agarwal, D. Halperin, and R. Pollack, Guest editors' foreword, Discrete and Computational Geometry, vol. 25 (2001), pp. 505-506
20. P.K. Agarwal, Guest editors' foreword, Discrete and Computational Geometry, vol. 26 (2001), pp. 185-186
21. P.K. Agarwal, On the numbers of congruent simplices in a point set, in Seventeenth Annual Symposium on Computational Geometry (2001)
22. P.K. Agarwal, M. de Berg, S. Har-Peled, M. Overmars, M. Sharir, and J. Vahrenhold, Reporting all intersecting pairs of polytopes in two and three dimensions, in Seventh Workshop on Algorithms and Data Structures (2001)
23. P.K. Agarwal, S. Har-Peled, and Y.Wang, Occlusion culling for fast walkthrough in urban areas, in Eurographics (2001)
24. P.K. Agarwal, M. Dietze, S. Govindarajan, and J. Clark, The extinction debt revisited: population dynamics in a continuous space model, in Ecological Society of America Annual Meeting (2001)
25. L. J. Guibas, S. Har-Peled, A. Rabinovitch, M. Sharir, and P.K. Agarwal, Computing the penetration depth of two convex polytopes in 3D, Nordic J. Computing, vol. 7 (2000), pp. 227-240
26. B. Aronov, S. Har-Peled, M. Sharir, and P.K. Agarwal, Exact and approximation algorithms for the minimum width annuli and shells, Discrete and Computational Geometry, vol. 24 (2000), pp. 687-705
27. M. Sharir and P.K. Agarwal, Davenport-Schinzel sequences and their geometric applications, in Handbook of Computational Geometry, edited by J.-R. Sack and J. Urrutia (2000), pp. 1-47, North-Holland, New York
28. M. Sharir and P.K. Agarwal, Arrangements and their applications, in Handbook of Computational Geometry, edited by J.-R. Sack and J. Urrutia (2000), pp. 49-119, North-Holland, New York
29. L. Knipping, M. van Kreveld, T. Strijk, A. Wolff and P.K. Agarwal, A simple and eÆcient algorithm for high quality line labeling, in Innovations in GIS VII: GeoComputation, edited by P. M. Atkinson and D. Martin (2000), pp. 147-159, Taylor and Francis, London
30. K. R. Varadarajan and P.K. Agarwal, Efficient algorithms for polygon simplification, Discrete and Computational Geometry, vol. 23 (2000), pp. 273-291
31. P.K. Agarwal, J. Basch, L. J. Guibas, J. Hershberger, and L. Zhang, Deformable free space tiling for kinetic collision detection, in Fourth Workshop on Algorithmic Foundations of Robotics (2000)
32. P.K. Agarwal, L. Arge, G. Brodal, and J. S. Vitter, I/O-efficient dynamic point location in monotone subdivisions, in Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (1999)
33. P.K. Agarwal and S. A. Cook, Guest editors' foreword, Journal of Computer and Systems Sciences, vol. 58 (1999), pp. 259
34. P.K. Agarwal, Guest editors' foreword, International Journal of Computational Geometry and Applications, vol. 9 (1999), pp. 325
35. P.K. Agarwal, L. Knipping, M. van Kreveld, T. Strijk, and A.Wolff, A simple and efficient algorithm for high quality line labeling, in GIS Research UK: 7th National Conference (1999) (Also appears in the Fifteenth European Workshop on Computational Geometry, 1999.)
36. P.K. Agarwal, B. Aronov, S. Har-Peled, and M. Sharir, Exact and approximation algorithms for the minimum width annuli and shells, in Fifteenth Annual Symposium on Computational Geometry (1999)
37. J. Erickson and P.K. Agarwal, Geometric range searching and its relatives, in Advances in Discrete and Computational Geometry, edited by B. Chazelle, J. Goodman, and R. Pollack (1998), pp. 1-56, American Mathematical Society, Providence
38. P.K. Agarwal, T. M. Murali, and J. S. Vitter, A new algorithm for constructing binary space partitions for orthogonal rectangles, in Sixth European Symposium on Algorithms (1998)
39. N. Amenta, B. Aronov, M. Sharir, and P.K. Agarwal, Largest placements and motion planning of a convex polygon, in Algorithms for Robotic Motion and Manipulation, pp. 143-154, edited by J.-P. Laumond and M. Overmars (1997), A. K. Peters, Wellesley
40. P.K. Agarwal, Range searching, in CRC Handbook of Discrete and Computational Geometry, edited by J. Goodman and J. O'Rourke (1997), pp. 575-598, CRC Press, NewYork
41. P.K. Agarwal and P. K. Desikan, Fast algorithms for surface simplication and other related problems, in Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (1997)
42. P.K. Agarwal, L. Guibas, T. M. Murali, and J. S. Vitter, Cylindrical kinetic and static binary space partitions, in Thirteenth Annual Symposium on Computational Geometry (1997)
43. P.K. Agarwal, (short communication) with T. M. Murali and J. S. Vitter, Practical techniques for constructing binary space partitions of rectangles, in Thirteenth Annual Symposium on Computational Geometry (1997)
44. P.K. Agarwal, M. Sharir, and E. Welzl, The discrete 2-center problem, in Thirteenth Annual Symposium on Computational Geometry (1997)
45. P.K. Agarwal, L. Guibas, J. Hershberger, and E. Veach, Maintaining structures for moving points, in Fifth Workshop on Algorithms and Data Structures (1997)
46. P.K. Agarwal, M. van Kreveld, and S. Suri, Label placement by maximum independent set in rectangles, in Ninth Canadian Conference on Computational Geometry (1997)
47. P.K. Agarwal and K. R. Varadarajan, Approximating shortest paths on polyhedral terrains, in Thirty Eighth Annual Symposium on Foundations of Computer Science (1997)
48. P.K. Agarwal and H. Wang, Approximation algorithms for shortest paths with bounded curvature, in Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (1996)
49. P.K. Agarwal and S. Suri, Simple and practical geometric algorithms, ACM Computing Surveys, vol. 28 (1996)
50. P.K. Agarwal and S. Suri, Simple and practical geometric algorithms, ACM Computing Surveys, vol. 28 (1996)
51. P.K. Agarwal, M. de Berg, D. Halperin, and M. Sharir, Computing depth orders in multiple directions, in Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (1996)
52. P.K. Agarwal and H. Wang, Approximation algorithms for shortest paths with bounded curvature, in Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (1996)
53. P.K. Agarwal, N. Amenta, B. Aronov, and M. Sharir, Largest placements and motion planning of a convex polygon, in Second International Workshop on Algorithmic Foundations of Robotics (1996)
54. M. Sharir and P.K. Agarwal, Algorithmic techniques for geometric optimization, in Computer Science Today: Recent Trends and Developments, Lecture Notes in Computer Science, vol. 1000; pp. 234-253, edited by J. van Leeuwen (1995), Springer-Verlag, Berlin
55. J. Matousek and P.K. Agarwal, Dynamic half-space searching and its applications, Algorithmica, vol. 14 (1995), pp. 325-345
56. P.K. Agarwal, P. Raghavan, and H. Tamaki, Motion planning for a steering-constrained robot through moderate obstacles, in Twenty Seventh Annual ACM Symposium on Theory of Computing (1995)
57. P.K. Agarwal, B. Aronov and S. Suri, Line stabbing bounds on triangulations in 3D, in Eleventh Annual Symposium on Computational Geometry (1995)
58. P.K. Agarwal, O. Schwarzkopf, and M. Sharir, The overlay of envelopes and their applications, in Eleventh Annual Symposium on Computational Geometry (1995)
59. P.K. Agarwal and K. R. Varadarajan, Linear approximation of convex objects, in Seventh Canadian Conference on Computational Geometry (1995)
60. M. van Kreveld and P.K. Agarwal, Implicit point location in arrangement segments with application to motion planning, International Journal of Computational Geometry and Applications, vol. 4 (1994), pp. 369-383
61. J. Matousek and P.K. Agarwal, Range searching with semialgebraic sets, Discrete and Computational Geometry, vol. 11 (1994), pp. 393-418
62. P.K. Agarwal and S. Suri, Surface approximation and disjoint geometric covers, in Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (1994)
63. P.K. Agarwal and S. Sen, Selection in monotone matrices and kth nearest neighbors, in Fourth Scandinavian Workshop on Algorithm Theory (1994)
64. M. Sharir and P.K. Agarwal, Circular visibility of a simple polygon from a fixed point, International Journal of Computational Geometry and Applications, vol. 3 (1993), pp. 1-25
65. P.K. Agarwal and M. Sharir, Ray shooting among convex polytopes in 3D, in Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (1993)
66. P.K. Agarwal and M. van Kreveld, Polygon and connected component intersection searching, in Third Workshop on Algorithms and Data Structures (1993)
67. P.K. Agarwal and M. Sharir, On the number of views of polyhedral terrains, in Fifth Canadian Conference on Computational Geometry (1993)
68. P.K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number, SIAM Journal on Computing, vol. 21 (1992), pp. 540-570
69. P.K. Agarwal and J. Matousek, Range searching with semialgebraic sets, in Seventeenth Symposium on Mathematical Foundations of Computer Science (1992)
70. P.K. Agarwal, D. Eppstein, and J. Matousek, Dynamic half-space range searching with applications to proximity problems, in Thirty Third Annual Symposium on Foundations of Computer Science (1992)
71. P.K. Agarwal and M. van Kreveld, Implicit point location in arrangement segments with application to motion planning, in Twelfth Conference on Foundations of Software Technology and Theoretical Computer Science (1992)
72. H. Edelsbrunner, O. Schwarzkopf, E. Welzl and P.K. Agarwal, Euclidean minimum spanning tree and bichromatic closest pairs, Discrete and Computational Geometry, vol. 6 (1991), pp. 407-422
73. P.K. Agarwal, Geometric partitioning and its applications, in Discrete and Computational Geometry: Papers from the DIMACS Special Year, edited by J. Goodman, R. Pollack, and W. Steiger (1991), pp. 1-37, American Mathematical Society (Providence, RI.)
74. P.K. Agarwal and M. Sharir, Applications of a new space partitioning technique, in Second Workshop on Algorithms and Data Structures (1991)
75. P.K. Agarwal, M. van Kreveld, and M. Overmars, Storing and searching curved objects, in Seventh Annual Symposium on Computational Geometry (1991)
76. P.K. Agarwal, Partitioning arrangements of lines: I. A deterministic algorithm, Discrete and Computational Geometry, vol. 5 (1990), pp. 449-483
77. P.K. Agarwal, B. Aronov, J. O'Rourke, and C. Schevon, Star unfolding of a polytope with applications, in Second Scandinavian Workshop on Algorithm Theory (1990)
78. P.K. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, Euclidean minimum spanning tree and bichromatic closest pairs, in Sixth Annual Symposium on Computational Geometry (1990)
79. P.K. Agarwal, A. Aggarwal, B. Aronov, S. Kosaraju, B. Shieber, and S. Suri, Computing all external-farthest neighbors for a simple polygon, in First Canadian Conference on Computational Geometry (1989)
80. P.K. Agarwal, An efficient algorithm for partitioning arrangements of lines and its applications, in Fifth Annual Symposium on Computational Geometry (1989)
81. P.K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number, Fifth Annual Symposium on Computational Geometry (1989)
82. P.K. Agarwal and Micha Sharir, Red-blue intersection detection algorithms, with applications to motion planning and collision detection, Fourth Annual Symposium on Computational Geometry (1988)
83. T. Smith, D. Peuquet, and S. Menon, and P.K. Agarwal, KBGIS-II: A knowledge-based geographic information system, International Journal of Geographical Information Systems, vol. 1 (1987), pp. 149-172
84. P.K. Agarwal, A. Choudhary and S. Sengupta, A VME bus compatible FFT Processor, in Conference on Signal Processing (1983) (Cochin, India.)

Papers Submitted

1. P.K. Agarwal, B. Bhattacharya, and S. Sen, Output-sensitive algorithms for uniform partitions of points, in Algorithmica, in press (2002)
2. P.K. Agarwal and M. Sharir, On the numbers of congruent simplices in a point set, to appear in Discrete and Computational Geometry (2002)
3. P.K. Agarwal (invited) with J. Basch, L.J. Guibas, J. Hershberger, and L. Zhang, Deformable free space tiling for kinetic collision detection, submitted to International Journal of Robotics (2002)
4. P.K. Agarwal, C. M. Procopiuc, andand K. R. Varadarajan, An approximation algorithm for computing the two-line center, submitted to Computational Geometry: Theory and Applications (2002)
5. P.K. Agarwal, M. de Berg, S. Har-Peled, M. Overmars, M. Sharir and J. Vahrenhold, Reporting all intersecting pairs of polytopes in two and three dimensions, submitted to Computational Geometry: Theory and Applications (2002)
6. P.K. Agarwal, 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. Y, Emerging challenges in computational topology (2002) (to appear in 2002.)
7. P.K. Agarwal, S. Govindarajan, and L. Arge, CRB-tree: An eÆcient indexing scheme for range aggregate queries (2002) (submitted for publication.)
8. P.K. Agarwal, R. Klein, C. Knauer, and M. Sharir, Computing the detour of polygonal curves (2002) (submitted for publication.)
9. P.K. Agarwal and P. K. Desikan, Fast algorithms for surface simplication and other related problems, submitted to Discrete and Computational Geometry (1999) (Also appears as Technical Report CS-1999-15, Department of Computer Science, Duke University, 1999.)

Other

1. P.K. Agarwal, Range searching, Technical Report CS-1996-05, Department of Computer Science, Duke University (1996)
2. P.K. Agarwal, F. Brooks, A. Varshney, H.Weber, and W. Wright, Multiresolution hierarchy generation of polygonal models, Technical Report CS-1995-20, Department of Computer Science, Duke University (1995)
3. P.K. Agarwal, M. Sharir, and S. Toledo, An efficient multidimensional searching technique and its applications, Technical Report CS-1993-20, Department of Computer Science, Duke University (1993)
4. P.K. Agarwal and M. T. Shing, Multiterminal flows in planar networks, Technical Report TRCS86-07, Department of Computer Science, Santa Barbara (1986)
5. P.K. Agarwal, Geometric Algorithms, Technical Report TRCS85-17, Department of Computer Science, Santa Barbara (1985)