Pankaj K. Agarwal
RJR Nabisco Professor of Computer Science in Trinity College of Arts and Sciences
Computational and combinatorial geometry, computational biology, robotics, spatial databases, geographic molecular information systems, and data structures.
Current Appointments & Affiliations
 RJR Nabisco Professor of Computer Science in Trinity College of Arts and Sciences, Computer Science, Trinity College of Arts & Sciences 2008
 Professor of Computer Science, Computer Science, Trinity College of Arts & Sciences 1998
 Professor of Mathematics, Mathematics, Trinity College of Arts & Sciences 2001
 Faculty Network Member of The Energy Initiative, Duke University Energy Initiative, Initiatives 2012
 Bass Fellow, Computer Science, Trinity College of Arts & Sciences 2005
Contact Information
 Box 90129, Durham, NC 277080129
 D214A Lev Sci Res Ctr, Durham, NC 27708
 pankaj@cs.duke.edu (919) 6606540
 http://www.cs.duke.edu/~pankaj/
 Background

Education, Training, & Certifications
 Ph.D., New York University 1989
 M.S., University of California at Santa Cruz 1986
 B.S.E.E., Indian Institute of Technology (India) 1982

Duke Appointment History
 Chair, Department of Computer Science, Computer Science, Trinity College of Arts & Sciences 2004  2010
 Associate Professor with Tenure, Computer Science, Trinity College of Arts & Sciences 1994  1998
 Associate Professor, Computer Science, Trinity College of Arts & Sciences 1992  1994
 Assistant Professor, Computer Science, Trinity College of Arts & Sciences 1989  1992
 Recognition

Awards & Honors
 Publications & Artistic Works

Selected Publications

Books
 Agarwal, PK, Akutsu, T, Amihood, A, Apostolico, A, Benham, C, Benson, G, Blanchette, M, ElMabrouk, N, Gascuel, O, Giancarlo, R, Guigo, R, Hallet, M, Huson, D, Kucherov, G, Lacey, M, Lagergren, J, Lancia, G, Landau, GM, Lecroq, T, Moret, B, Morishita, S, Mossel, E, Moulton, V, Pachter, L, Reinert, K, Rigoutsos, I, Sagot, MF, Sankoff, D, Schbath, S, Segal, E, Semple, C, Setubal, JC, Sharan, R, Skiena, S, Stoye, J, Ukkonen, E, Vawter, L, Valencia, A, Warnow, T, Wang, L, Casadio, R, and Myers, G. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface. December 1, 2005.

Conference Papers
 Agarwal, PK, Pan, J, and Victor, W. "An efficient algorithm for placing electric vehicle charging stations." December 1, 2016. Full Text
 Nath, A, Fox, K, Agarwal, PK, and Munagala, K. "Massively parallel algorithms for computing TIN DEMs and contour trees for large terrains." October 31, 2016. Full Text
 Ying, R, Pan, J, Fox, K, and Agarwal, PK. "A simple efficient approximation algorithm for dynamic time warping." October 31, 2016. Full Text
 Agarwal, PK, Fox, K, Munagala, K, and Nath, A. "Parallel algorithms for constructing range and nearestneighbor searching data structures." June 15, 2016. Full Text
 Agarwal, PK, Kumar, N, Sintos, S, and Suri, S. "Rangemax queries on uncertain data." June 15, 2016. Full Text
 Agarwal, PK, Fox, K, and Salzman, O. "An efficient algorithm for computing highquality paths amid polygonal obstacles." January 1, 2016.
 Pan, J, Rao, V, Agarwal, PK, and Gelfand, AE. "Markovmodulated marked poisson processes for checkin data." January 1, 2016.
 Zhang, W, Agarwal, PK, and Mukherjee, S. "Contour trees of uncertain terrains." November 3, 2015. Full Text
 Lebeck, N, Mølhave, T, and Agarwal, PK. "Computing highly occluded paths using a sparse network." November 4, 2014. Full Text
 Agarwal, PK, HarPeled, S, Suri, S, YIldIz, H, and Zhang, W. "Convex hulls under uncertainty." January 1, 2014. Full Text
 Agarwal, PK, Xie, J, Yang, J, and Yu, H. "Scalable continuous query processing by tracking hotspots." December 1, 2006.
 Agarwal, PK, Cabello, S, Sellarès, JA, and Sharir, M. "Computing a CenterTransversal Line." Springer, 2006. Full Text
 Agarwal, PK, Edelsbrunner, H, and Wang, Y. "Computing the writhing number of a polygonal knot." ACM/SIAM, 2002.
 Agarwal, PK, Gao, J, and Guibas, LJ. "Kinetic Medians and kdTrees." Springer, 2002. Full Text
 Agarwal, PK, Govindarajan, S, and Muthukrishnan, S. "Range Searching in Categorical Data: Colored Range Searching on Grid." Springer, 2002. Full Text
 Agarwal, PK, Hagerup, T, Ray, R, Sharir, M, Smid, MHM, and Welzl, E. "Translating a Planar Object to Maximize Point Containment." Springer, 2002. Full Text
 Agarwal, PK, HarPeled, S, Mustafa, NH, and Wang, Y. "NearLinear Time Approximation Algorithms for Curve Simplification." Springer, 2002. Full Text
 Agarwal, PK, Procopiuc, CM, and Varadarajan, KR. "Approximation Algorithms for kLine Center." Springer, 2002. Full Text
 Agarwal, PK, and Sharir, M. "Pseudoline arrangements: duality, algorithms, and applications." ACM/SIAM, 2002.
 Procopiuc, CM, Agarwal, PK, and HarPeled, S. "STARTree: An Efficient SelfAdjusting Index for Moving Objects." Springer, 2002. Full Text
 Agarwal, PK, Arge, L, Procopiuc, O, and Vitter, JS. "A Framework for Index Bulk Loading and Dynamization." Springer, 2001. Full Text
 Agarwal, PK, Arge, L, and Vahrenhold, J. "Time Responsive External Data Structures for Moving Points." Springer, 2001. Full Text
 Agarwal, PK, Berg, MD, HarPeled, S, Overmars, MH, Sharir, M, and Vahrenhold, J. "Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions." Springer, 2001. Full Text
 Agarwal, PK, Flato, E, and Halperin, D. "Polygon Decomposition for Efficient Construction of Minkowski Sums." Springer, 2000. Full Text
 Agarwal, PK, Guibas, LJ, HarPeled, S, Rabinovitch, A, and Sharir, M. "Computing the penetration depth of two convex polytopes in 3d." January 1, 2000. Full Text
 Agarwal, PK, Bhattacharya, BK, and Sen, S. "OutputSensitive Algorithms for Uniform Partitions of Points." Springer, 1999. Full Text
 Murali, TM, Agarwal, PK, and Vitter, JS. "Constructing Binary Space Partitions for Orthogonal Rectabgles in Practice." Springer, 1998. Full Text
 Agarwal, PK, Guibas, LJ, Hershberger, J, and Veach, E. "Maintaining the Extent of a Moving Point Set." Springer, 1997. Full Text
 Agarwal, PK, Aronov, B, Pach, J, Pollack, R, and Sharir, M. "QuasiPlanar Graphs Have a Linear Number of Edges." Springer, 1995. Full Text

Journal Articles
 Agarwal, PK, HarPeled, S, Suri, S, Yıldız, H, and Zhang, W. "Convex Hulls Under Uncertainty (Published online)." Algorithmica 79, no. 2 (October 2017): 340367. Full Text
 Agarwal, PK, Aronov, B, HarPeled, S, Phillips, JM, Yi, K, and Zhang, W. "NearestNeighbor Searching Under Uncertainty II." ACM Transactions on Algorithms 13, no. 1 (October 10, 2016): 125. Full Text
 Agarwal, PK, Fox, K, Pan, J, and Ying, R. "Approximating dynamic time warping and edit distance for a pair of point sequences." Leibniz International Proceedings in Informatics, LIPIcs 51 (June 1, 2016): 6.16.16. Full Text
 Yu, A, Agarwal, PK, and Yang, J. "Top$k$ Preferences in High Dimensions." IEEE Transactions on Knowledge and Data Engineering 28, no. 2 (February 1, 2016): 311325. Full Text
 Agarwal, PK, Gao, J, Guibas, LJ, Kaplan, H, Rubin, N, and Sharir, M. "Stable Delaunay Graphs." Discrete & Computational Geometry 54, no. 4 (December 2015): 905929. Full Text
 Agarwal, PK, Kaplan, H, Rubin, N, and Sharir, M. "Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions." Discrete & Computational Geometry 54, no. 4 (December 2015): 871904. Full Text
 Agarwal, PK, Mølhave, T, Revsbæk, M, Safa, I, Wang, Y, and Yang, J. "Maintaining Contour Trees of Dynamic Terrains." Leibniz International Proceedings in Informatics, LIPIcs 34 (June 1, 2015): 796811. Full Text
 Agarwal, PK, Fox, K, Nath, A, Sidiropoulos, A, and Wang, Y. "Computing the GromovHausdorff distance for metric trees." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 9472 (January 1, 2015): 529540. Full Text
 Agarwal, PK, and Sharathkumar, R. "Streaming Algorithms for Extent Problems in High Dimensions." Algorithmica 72, no. 1 (2015): 8398. Full Text
 Salzman, O, Shaharabani, D, Agarwal, PK, and Halperin, D. "Sparsification of motionplanning roadmaps by edge contraction." The International Journal of Robotics Research 33, no. 14 (December 2014): 17111725. Full Text
 Agarwal, PK, HarPeled, S, Kaplan, H, and Sharir, M. "Union of Random Minkowski Sums and Network Vulnerability Analysis." Discrete & Computational Geometry 52, no. 3 (October 2014): 551582. Full Text
 Wu, Y, Agarwal, PK, Li, C, Yang, J, and Yu, C. "Toward computational factchecking." Proceedings of the VLDB Endowment 7, no. 7 (March 1, 2014): 589600. Full Text
 Sankararaman, S, Efrat, A, Ramasubramanian, S, and Agarwal, PK. "On channeldiscontinuityconstraint routing in wireless networks." Ad Hoc Networks 13, no. PART A (February 1, 2014): 153169. Full Text
 Agarwal, PK, HarPeled, S, Suri, S, YIldIz, H, and Zhang, W. "Convex hulls under uncertainty." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8737 LNCS (January 1, 2014): 3748. Full Text
 Agarwal, PK, and Pan, J. "Nearlinear algorithms for geometric hitting sets and set covers." Proceedings of the Annual Symposium on Computational Geometry (January 1, 2014): 271279. Full Text
 Agarwal, PK, and Sharathkumar, R. "Approximation algorithms for bipartite matching with metric and geometric costs." Proceedings of the Annual ACM Symposium on Theory of Computing (January 1, 2014): 555564. Full Text
 Wu, Y, Walenz, B, Li, P, Shim, A, Sonmez, E, Agarwal, PK, Li, C, Yang, J, and Yu, C. "ICheck: Computationally combating "lies, D  Ned Lies, and statistics"." Proceedings of the ACM SIGMOD International Conference on Management of Data (January 1, 2014): 10631066. Full Text
 Yu, A, Agarwal, PK, and Yang, J. "Topk preferences in high dimensions." Proceedings  International Conference on Data Engineering (January 1, 2014): 748759. Full Text
 Agarwal, PK, Aronov, B, Van Kreveld, M, Löffler, M, and Silveira, RI. "Computing correlation between piecewiselinear functions." SIAM Journal on Computing 42, no. 5 (December 26, 2013): 18671887. Full Text
 Agarwal, PK, Matoušek, J, and Sharir, M. "On range searching with semialgebraic sets. II." SIAM Journal on Computing 42, no. 6 (December 23, 2013): 20392062. Full Text
 Lebeck, N, Mølhave, T, and Agarwal, PK. "Computing highly occluded paths on a terrain." GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems (December 1, 2013): 1423. Full Text
 Sankararaman, S, Agarwal, PK, Mølhave, T, Pan, J, and Boedihardjo, AP. "Modeldriven matching and segmentation of trajectories." GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems (December 1, 2013): 234243. Full Text
 Agarwal, PK, Cormode, G, Huang, Z, Phillips, JM, Wei, Z, and Yi, K. "Mergeable summaries." ACM Transactions on Database Systems 38, no. 4 (November 1, 2013). Full Text
 Agarwal, PK, Efrat, A, Ganjugunte, SK, Hay, D, Sankararaman, S, and Zussman, G. "The resilience of WDM networks to probabilistic geographical failures." IEEE/ACM Transactions on Networking 21, no. 5 (January 14, 2013): 15251538. Full Text
 Afshani, P, Agarwal, PK, Arge, L, Larsen, KG, and Phillips, JM. "(Approximate) Uncertain Skylines." Theory of Computing Systems 52, no. 3 (2013): 342366. Full Text
 Agarwal, PK, Arge, L, Govindarajan, S, Yang, J, and Yi, K. "Efficient external memory structures for rangeaggregate queries." Computational Geometry: Theory and Applications 46, no. 3 (2013): 358370. Full Text
 Agarwal, PK, Aronov, B, HarPeled, S, Phillips, JM, Yi, K, and Zhang, W. "Nearest neighbor searching under uncertainty II." Proceedings of the ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems (2013): 115126. Full Text
 Agarwal, PK, Efrat, A, Ganjugunte, SK, Hay, D, Sankararaman, S, and Zussman, G. "The Resilience of WDM Networks to Probabilistic Geographical Failures." IEEE/ACM Transactions on Networking (2013). Full Text
 Agarwal, PK, HarPeled, S, and Yu, H. "EMBEDDINGS OF SURFACES, CURVES, AND MOVING POINTS IN EUCLIDEAN SPACE." SIAM JOURNAL ON COMPUTING 42, no. 2 (2013): 442458. Full Text Link to Item
 Agarwal, PK, Kaplan, H, and Sharir, M. "Union of random minkowski sums and network vulnerability analysis." Proceedings of the Annual Symposium on Computational Geometry (2013): 177186.
 Agarwal, PK, Sharathkumar, R, Agarwal, PK, and Sharathkumar, R. "Streaming Algorithms for Extent Problems in High DimensionsStreaming Algorithms for Extent Problems in High Dimensions (PublishedAccepted)." Algorithmica (2013): 116. Full Text
 Afshani, P, Agarwal, PK, Arge, L, Larsen, KG, and Phillips, JM. "(Approximate) Uncertain Skylines." Theory of Computing Systems (2012): 125. Full Text
 Agarwal, PK, Arge, L, Kaplan, H, Molad, E, Tarjan, RE, and Yi, K. "An optimal dynamic data structure for stabbingsemigroup queries." SIAM Journal on Computing 41, no. 1 (2012): 104127. Full Text
 Agarwal, PK, Avraham, RB, and Sharir, M. "The 2center problem in three dimensions." Computational Geometry: Theory and Applications (2012). Full Text
 Agarwal, PK, Cheng, SW, and Yi, K. "Range searching on uncertain data." ACM Transactions on Algorithms 8, no. 4 (2012). Full Text
 Agarwal, PK, Cormode, G, Huang, Z, Phillips, J, Wei, Z, and Yi, K. "Mergeable summaries." Proceedings of the ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems (2012): 2334. Full Text
 Agarwal, PK, Efrat, A, Sankararaman, S, and Zhang, W. "Nearestneighbor searching under uncertainty." Proceedings of the ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems (2012): 225236. Full Text
 Agarwal, PK, Ezra, E, and Sharir, M. "Nearlinear approximation algorithms for geometric hitting sets." Algorithmica 63, no. 12 (2012): 125. Full Text
 Agarwal, PK, Matoušek, J, and Sharir, M. "On range searching with semialgebraic sets II." Proceedings  Annual IEEE Symposium on Foundations of Computer Science, FOCS (2012): 420429. Full Text
 Sharathkumar, R, and Agarwal, PK. "A nearlinear time εapproximation algorithm for geometric bipartite matching." Proceedings of the Annual ACM Symposium on Theory of Computing (2012): 385394. Full Text
 Sharathkumar, R, and Agarwal, PK. "Algorithms for the transportation problem in geometric settings." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (2012): 306317.
 Wu, Y, Agarwal, PK, Li, C, Yang, J, and Yu, C. "On "one of the few" objects." Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2012): 14871495. Full Text
 Yu, A, Agarwal, PK, and Yang, J. "Subscriber assignment for widearea contentbased publish/subscribe." IEEE Transactions on Knowledge and Data Engineering 24, no. 10 (2012): 18331847. Full Text
 Yu, A, Agarwal, PK, and Yang, J. "Processing and notifying range topk subscriptions." Proceedings  International Conference on Data Engineering (2012): 810821. Full Text
 Yu, A, Agarwal, PK, and Yang, J. "Processing a large number of continuous preference topk queries." Proceedings of the ACM SIGMOD International Conference on Management of Data (2012): 397408. Full Text
 Clark, JS, Agarwal, P, Bell, DM, Flikkema, PG, Gelfand, A, Nguyen, X, Ward, E, and Yang, J. "Inferential ecosystem models, from network data to prediction." Ecol Appl 21, no. 5 (July 2011): 15231536. Link to Item
 Abam, MA, Agarwal, PK, Berg, MD, and Yu, H. "Outoforder event processing in kinetic data structures." Algorithmica (New York) 60, no. 2 (2011): 250273. Full Text
 Afshani, P, Agarwal, PK, Arge, L, Larsen, KG, and Phillips, JM. "(Approximate) uncertain skylines." ACM International Conference Proceeding Series (2011): 186196. Full Text
 Agarwal, PK, Efrat, A, Ganjugunte, S, Hay, D, Sankararaman, S, and Zussman, G. "The resilience of WDM networks to probabilistic geographical failures." Proceedings  IEEE INFOCOM (2011): 15211529. Full Text
 Agarwal, PK, Efrat, A, Gniady, C, Mitchell, JSB, Polishchuk, V, and Sabhnani, GR. "Distributed localization and clustering using data correlation and the Occam's razor principle." 2011 International Conference on Distributed Computing in Sensor Systems and Workshops, DCOSS'11 (2011). Full Text
 Agarwal, PK, Mølhave, T, Yu, H, and Clark, JS. "Exploiting temporal coherence in forest dynamics simulation." Proceedings of the Annual Symposium on Computational Geometry (2011): 7786. Full Text
 Agarwal, PK, Mølhave, T, and Sadri, B. "I/Oefficieiit contour queries on terrains." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (2011): 268284.
 Beutel, A, Mølhave, T, Agarwal, PK, Boedihardjo, AP, and Shine, JA. "TerraNNI: Natural neighbor interpolation on a 3D grid using a GPU." GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems (2011): 6473. Full Text
 Yu, A, Agarwal, PK, and Yang, J. "Subscriber assignment for widearea contentbased publish/subscribe." Proceedings  International Conference on Data Engineering (2011): 267278. Full Text
 Chen, L, Tang, C, Yang, J, Kitsuregawa, M, and Li, Q. "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics): Preface." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6184 LNCS (August 3, 2010).
 Agarwal, PK, Arge, L, and Yi, K. "I/Oefficient batched unionfind and its applications to terrain analysis." ACM Transactions on Algorithms 7, no. 1 (2010). Full Text
 Agarwal, PK, Aronov, B, Kreveld, MV, Löffler, M, and Silveira, RI. "Computing similarity between piecewiselinear functions." Proceedings of the Annual Symposium on Computational Geometry (2010): 375383. Full Text
 Agarwal, PK, BenAvraham, R, and Sharir, M. "The 2center problem in three dimensions." Proceedings of the Annual Symposium on Computational Geometry (2010): 8796. Full Text
 Agarwal, PK, Bereg, S, Daescu, O, Kaplan, H, Ntafos, S, Sharir, M, and Zhu, B. "Guarding a terrain by two watchtowers." Algorithmica (New York) 58, no. 2 (2010): 352390. Full Text
 Agarwal, PK, Efrat, A, Ganjugunte, SK, Hay, D, Sankararaman, S, and Zussman, G. "Network vulnerability to single, multiple, and probabilistic physical attacks." Proceedings  IEEE Military Communications Conference MILCOM (2010): 18241829. Full Text
 Agarwal, PK, Efrat, A, Sharathkumar, R, and Yu, H. "On approximate geodesicdistance queries amid deforming point clouds." Springer Tracts in Advanced Robotics 57 (2010): 351365. Full Text
 Agarwal, PK, Gao, J, Guibas, LJ, Kaplan, H, Koltun, V, Rubin, N, and Sharir, M. "Kinetic stable Delaunay graphs." Proceedings of the Annual Symposium on Computational Geometry (2010): 127136. Full Text
 Agarwal, PK, HarPeled, S, Sharir, M, and Wang, Y. "Hausdorff distance under translation for points and balls." ACM Transactions on Algorithms 6, no. 4 (2010). Full Text
 Agarwal, PK, Phillips, JM, and Sadri, B. "Lipschitz unimodal and isotonic regression on paths and trees." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6034 LNCS (2010): 384396. Full Text
 Agarwal, PK, Phillips, JM, and Yu, H. "Stability of εkernels." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6346 LNCS, no. PART 1 (2010): 487499. Full Text
 Agarwal, PK, and Sharathkumar, R. "Streaming algorithms for extent problems in high dimensions." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (2010): 14811489.
 Agarwal, PK. "An improved algorithm for computing the volume of the union of cubes." Proceedings of the Annual Symposium on Computational Geometry (2010): 230239. Full Text
 Beutel, A, Mølhave, T, and Agarwal, PK. "Natural neighbor interpolation based grid DEM construction using a GPU." GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems (2010): 172181. Full Text
 Mølhave, T, Agarwal, PK, Arge, L, and Revsbæk, M. "Scalable algorithms for large highresolution terrain data." ACM International Conference Proceeding Series (2010). Full Text
 Sankararaman, S, Efrat, A, Ramasubramanian, S, and Agarwal, PK. "On channeldiscontinuityconstraint routing in wireless networks." Proceedings  IEEE INFOCOM (2010). Full Text
 Agarwal, PK, Cheng, SW, Tao, Y, and Yi, K. "Indexing uncertain data." Proceedings of the ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems (2009): 137146. Full Text
 Agarwal, PK, Ezra, E, and Ganjugunte, SK. "Efficient sensor placement for surveillance problems." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5516 LNCS (2009): 301314. Full Text
 Agarwal, PK, Ezra, E, and Sharir, M. "Nearlinear approximation algorithms for geometric hitting sets." Proceedings of the Annual Symposium on Computational Geometry (2009): 2332. Full Text
 Agarwal, PK, Sharathkumar, R, and Yu, H. "Approximate Euclidean shortest paths amid convex obstacles." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (2009): 283292.
 Agarwal, PK, Xie, J, Yang, J, and Yu, H. "Inputsensitive scalable continuous join query processing." ACM Transactions on Database Systems 34, no. 3 (2009). Full Text
 Agarwal, PK, Arge, L, Moølhave, T, and Sadri, B. "I/Oefflcient algorithms for computing contours on a terrain." Proceedings of the Annual Symposium on Computational Geometry (2008): 129138. Full Text
 Agarwal, PK, Chen, DZ, Ganjugunte, SK, Misiołek, E, Sharir, M, and Tang, K. "Stabbing convex polygons with a segment or a polygon." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5193 LNCS (2008): 5263. Full Text
 Agarwal, PK, HarPeled, S, and Yu, H. "Robust shape fitting via peeling and grating coresets." Discrete and Computational Geometry 39, no. 13 (2008): 3858. Full Text
 Agarwal, PK, Hurtado, F, Toussaint, GT, and Trias, J. "On polyhedra induced by point sets in space." Discrete Applied Mathematics 156, no. 1 (2008): 4254. Full Text
 Agarwal, PK, Kaplan, H, and Sharir, M. "Kinetic and dynamic data structures for closest pair and all nearest neighbors." ACM Transactions on Algorithms 5, no. 1 (2008). Full Text
 Agarwal, PK, Klein, R, Knauer, C, Langerman, S, Morin, P, Sharir, M, and Soss, M. "Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D." Discrete and Computational Geometry 39, no. 13 (2008): 1737. Full Text
 Agarwal, PK, Sadri, B, and Yu, H. "Untangling triangulations through local explorations." Proceedings of the Annual Symposium on Computational Geometry (2008): 288297. Full Text
 Agarwal, PK, Sharir, M, and Welzl, E. "Algorithms for center and Tverberg points." ACM Transactions on Algorithms 5, no. 1 (2008). Full Text
 Agarwal, PK, and Phillips, JM. "An efficient algorithm for 2D Euclidean 2center with outliers." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5193 LNCS (2008): 6475. Full Text
 Chandramouli, B, Yang, J, Agarwal, PK, Yu, A, and Zheng, Y. "ProSem: Scalable widearea publish/subscribe." Proceedings of the ACM SIGMOD International Conference on Management of Data (2008): 13151317. Full Text
 Yu, H, Agarwal, PK, Poreddy, R, and Varadarajan, KR. "Practical methods for shape fitting and kinetic data structures using coresets." Algorithmica (New York) 52, no. 3 (2008): 378402. Full Text
 Clark, JS, Dietze, M, Chakraborty, S, Agarwal, PK, Ibanez, I, LaDeau, S, and Wolosin, M. "Resolving the biodiversity paradox." Ecol Lett 10, no. 8 (August 2007): 647659. Full Text Link to Item
 Agarwal, PK, Mustafa, NH, and Wang, Y. "Fast molecular shape matching using contact maps." J Comput Biol 14, no. 2 (March 2007): 131143. Full Text Link to Item
 Agarwal, PK, Apfelbaum, R, Purdy, G, and Sharir, M. "Similar simplices in a ddimensional point set." Proceedings of the Annual Symposium on Computational Geometry (2007): 232238. Full Text
 Agarwal, PK, HarPeled, S, and Yu, H. "Embeddings of surfaces, curves, and moving points in euclidean space." Proceedings of the Annual Symposium on Computational Geometry (2007): 381389. Full Text
 Agarwal, PK, Kaplan, H, and Sharir, M. "Computing the volume of the union of cubes." Proceedings of the Annual Symposium on Computational Geometry (2007): 294301. Full Text
 Agarwal, PK, and Yu, H. "A spaceoptimal datastream algorithm for coresets in the plane." Proceedings of the Annual Symposium on Computational Geometry (2007): 110. Full Text
 Agarwal, PK. "Modeling and analyzing massive terrain data sets." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4835 LNCS (2007): 1.
 Clark, JS, and Agarwal, PK. "Rejoinder to Clark et al. (2007): Response to Chesson and Rees." Ecology Letters 10, no. 8 (2007): 661662. Full Text
 Danner, A, Mølhave, T, Yi, K, Agarwal, PK, Arge, L, and Mitasova, H. "TerraStream: From elevation data to watershed hierarchies." GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems (2007): 212219. Full Text
 Flikkema, PG, Agarwal, PK, Clark, JS, Ellis, C, Gelfand, A, Munagala, K, and Yang, J. "From data reverence to data relevance: Modelmediated wireless sensing of the physical environment." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4487 LNCS (2007): 988994.
 Govindarajan, S, Dietze, MC, Agarwal, PK, and Clark, JS. "A scalable algorithm for dispersing population." Journal of Intelligent Information Systems 29, no. 1 (2007): 3961. Full Text
 Zheng, Y, Brady, DJ, and Agarwal, PK. "Localization using boundary sensors: An analysis based on graph theory." ACM Transactions on Sensor Networks 3, no. 4 (2007). Full Text
 Agarwal, PK, Arge, L, and Danner, A. "From point cloud to grid DEM: A scalable approach." Progress in Spatial Data Handling  12th International Symposium on Spatial Data Handling, SDH 2006 (December 1, 2006): 771788. Full Text
 Bilu, Y, Agarwal, PK, and Kolodny, R. "Faster algorithms for optimal multiple sequence alignment based on pairwise comparisons." IEEE/ACM Trans Comput Biol Bioinform 3, no. 4 (October 2006): 408422. Full Text Link to Item
 Abam, MA, Agarwal, PK, Berg, MD, and Yu, H. "Outoforder event processing in kinetic data structures." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4168 LNCS (2006): 624635.
 Agarwal, PK, Arge, L, and Yi, K. "I/Oefficient batched unionfind and its applications to terrain analysis." Proceedings of the Annual Symposium on Computational Geometry 2006 (2006): 167176.
 Agarwal, PK, Aronov, B, and Koltun, V. "Efficient algorithms for bichromatic separability." ACM Transactions on Algorithms 2, no. 2 (2006): 209227. Full Text
 Agarwal, PK, Brady, D, and Matoušek, J. "Segmenting object space by geometric reference structures." ACM Transactions on Sensor Networks 2, no. 4 (2006): 455465. Full Text
 Agarwal, PK, Edelsbrunner, H, Harer, J, and Wang, Y. "Extreme elevation on a 2manifold." Discrete and Computational Geometry 36, no. 4 (2006): 553572. Full Text
 Agarwal, PK, HarPeled, S, and Yu, H. "Robust shape fitting via peeling and grating coresets." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (2006): 182191. Full Text
 Agarwal, PK, Overmars, M, and Sharir, M. "Computing maximally separated sets in the plane." SIAM Journal on Computing 36, no. 3 (2006): 815834. Full Text
 Agarwal, PK, Wang, Y, and Yu, H. "A twodimensional kinetic triangulation with nearquadratic topological changes." Discrete and Computational Geometry 36, no. 4 (2006): 573592. Full Text
 Agarwal, PK, and Mustafa, NH. "Independent set of intersection graphs of convex objects in 2D." Computational Geometry: Theory and Applications 34, no. 2 (2006): 8395. Full Text
 Flikkema, PG, Agarwal, PK, Clark, JS, Ellis, C, Gelfand, A, Munagala, K, and Yang, J. "Modeldriven dynamic control of embedded wireless sensor networks." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3993 LNCS  III (2006): 409416. Full Text
 Phillips, JM, Rudolph, J, and Agarwal, PK. "Segmenting motifs in proteinprotein interface surfaces." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4175 LNBI (2006): 207218.
 Agarwal, PK, Arge, L, and Yi, K. "I/Oefficient construction of constrained delaunay triangulations." Lecture Notes in Computer Science 3669 (2005): 355366.
 Agarwal, PK, Arge, L, and Yi, K. "An optimal dynamic interval stabbingmax data structure?." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (2005): 803812.
 Agarwal, PK, Aronov, B, Koltun, V, and Sharir, M. "Lines avoiding unit balls in three dimensions." Discrete and Computanional Geometry 34, no. 2 (2005): 231250. Full Text
 Agarwal, PK, Bereg, S, Daescu, O, Kaplan, H, Ntafos, S, and Zhu, B. "Guarding a terrain by two watchtowers." Proceedings of the Annual Symposium on Computational Geometry (2005): 346355. Full Text
 Agarwal, PK, Berretty, RP, and Collins, AD. "A nearquadratic algorithm for fence design." Discrete and Computanional Geometry 33, no. 3 (2005): 463481. Full Text
 Agarwal, PK, Bilu, Y, and Kolodny, R. "Faster algorithms for optimal Multiple Sequence Alignment based on pairwise comparisons." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3692 LNBI (2005): 315327. Full Text
 Agarwal, PK, HarPeled, S, Mustafa, NH, and Wang, Y. "Nearlinear time approximation algorithms for curve simplification." Algorithmica (New York) 42, no. 34 (2005): 203219. Full Text
 Agarwal, PK, Procopiuc, CM, and Varadarajan, KR. "Approximation algorithms for a kline center." Algorithmica (New York) 42, no. 34 (2005): 221230. Full Text
 Agarwal, PK, Wang, Y, and Yin, P. "Lower bound for sparse Euclidean spanners." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (2005): 670671.
 Agarwal, PK, Xie, J, Yang, J, and Yu, H. "Monitoring continuous bandjoin queries over dynamic data." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3827 LNCS (2005): 349359. Full Text
 Agarwal, PK, and Sharir, M. "Pseudoline arrangements: Duality, algorithms, and applications." SIAM Journal on Computing 34, no. 3 (2005): 526552. Full Text
 Wang, Y, Agarwal, PK, Brown, P, Edelsbrunner, H, and Rudolph, J. "Coarse and reliable geometric alignment for protein docking." Pac Symp Biocomput (2005): 6475. Link to Item
 Agarwal, P, Guibas, L, Nguyen, A, Russel, D, and Zhang, L. "Collision detection for deforming necklaces." Computational Geometry: Theory and Applications 28, no. 23 SPEC. ISS. (2004): 137163. Full Text
 Agarwal, PK, Arge, L, Erickson, J, and Yu, H. "Efficient tradeoff schemes in data structures for querying moving objects." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3221 (2004): 415.
 Agarwal, PK, Aronov, B, Koltun, V, and Sharir, M. "On lines avoiding unit balls in three dimensions." Proceedings of the Annual Symposium on Computational Geometry (2004): 3645.
 Agarwal, PK, Aronov, B, and Koltun, V. "Efficient Algorithms for Bichromatic Separability." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms 15 (2004): 675683.
 Agarwal, PK, Berretty, RP, and Collins, AD. "A nearquadratic algorithm for fence design." Springer Tracts in Advanced Robotics 7 STAR (2004): 347362. Full Text
 Agarwal, PK, Edelsbrunner, H, Harer, J, and Wang, Y. "Extreme elevation on a 2manifold." Proceedings of the Annual Symposium on Computational Geometry (2004): 357365.
 Agarwal, PK, Edelsbrunner, H, and Wang, Y. "Computing the writhing number of a polygonal knot." Discrete and Computanional Geometry 32, no. 1 (2004): 3753. Full Text
 Agarwal, PK, HarPeled, S, and Varadarajan, KR. "Approximating extent measures of points." Journal of the ACM 51, no. 4 (2004): 606635. Full Text
 Agarwal, PK, Nevo, E, Pach, J, Pinchasi, R, Sharir, M, and Smorodinsky, S. "Lenses in arrangements of pseudocircles and their applications." Journal of the ACM 51, no. 2 (2004): 139186. Full Text
 Agarwal, PK, Overmars, M, and Sharir, M. "Computing Maximally Separated Sets in the Plane and Independent Sets in the Intersection Graph of Unit Disks." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms 15 (2004): 509518.
 Agarwal, PK, Sharir, M, and Welzl, E. "Algorithms for center and tverberg points." Proceedings of the Annual Symposium on Computational Geometry (2004): 6167.
 Agarwal, PK, Wang, Y, and Yu, H. "A 2D kinetic triangulation with nearquadratic topological changes." Proceedings of the Annual Symposium on Computational Geometry (2004): 180189.
 Agarwal, PK, and Mustafa, NH. "Independent set of intersection graphs of convex objects in 2D." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3111 (2004): 127137.
 Agarwal, PK, and Mustafa, NH. "Kmeans projective clustering." Proceedings of the ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems 23 (2004): 155165.
 Agarwal, PK, and Varadarajan, KR. "A nearlinear constantfactor approximation for euclidean bipartite matching?." Proceedings of the Annual Symposium on Computational Geometry (2004): 247252.
 Choi, V, Agarwal, PK, Edelsbrunner, H, and Rudolph, J. "Local search heuristic for rigid protein docking." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3240 (2004): 218229.
 Govindarajan, S, Dietze, M, Agarwal, PK, and Clark, JS. "A scalable simulator for forest dynamics." Proceedings of the Annual Symposium on Computational Geometry (2004): 106115.
 Yu, H, Agarwal, PK, Poreddy, R, and Varadarajan, KR. "Practical methods for shape fitting and kinetic data structures using core sets." Proceedings of the Annual Symposium on Computational Geometry (2004): 263272.
 Agarwal, PK, Procopiuc, CM, and Varadarajan, KR. "A (1+ε)approximation algorithm for 2linecenter." Computational Geometry: Theory and Applications 26, no. 2 (October 1, 2003): 119128. Full Text
 Agarwal, PK, Arge, L, Danner, A, and HollandMinkley, B. "Cacheoblivious data structures for orthogonal range searching." Proceedings of the Annual Symposium on Computational Geometry (2003): 237245.
 Agarwal, PK, Arge, L, Yang, J, and Yi, K. "I/Oefficient structures for orthogonal rangemax and stabbingmax queries." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2832 (2003): 718.
 Agarwal, PK, Arge, L, and Erickson, J. "Indexing moving points." Journal of Computer and System Sciences 66, no. 1 (2003): 207243. Full Text
 Agarwal, PK, HarPeled, S, Sharir, M, and Wang, Y. "Hausdorff distance under translation for points and balls." Proceedings of the Annual Symposium on Computational Geometry (2003): 282291.
 Agarwal, PK, Krishnan, S, Mustafa, NH, and Venkatasubramanian, S. "Streaming geometric optimization using graphics hardware." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2832 (2003): 544555.
 Agarwal, PK, Procopiuc, CM, and Varadarajan, KR. "A (1+ε)approximation algorithm for 2linecenter." Computational Geometry: Theory and Applications 26, no. 2 (2003): 119128. Full Text
 Agarwal, PK, and Arge, L. "Editorial." Computational Geometry: Theory and Applications 24, no. 2 (2003): 49. Full Text
 Agarwal, PK, and Procopiuc, CM. "Approximation algorithms for projective clustering." Journal of Algorithms 46, no. 2 (2003): 115139. Full Text
 Collins, AD, Agarwal, PK, and Harer, JL. "HPRM: A hierarchical PRM." Proceedings  IEEE International Conference on Robotics and Automation 3 (2003): 44334438.
 Govindarajan, S, Agarwal, PK, and Arge, L. "CRBtree: An efficient indexing scheme for rangeaggregate queries." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2572 (2003): 143157.
 Procopiuc, O, Agarwal, PK, Arge, L, and Vitter, JS. "Bkdtree: A dynamic scalable kdtree." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2750 (2003): 4665.
 Agarwal, P, Nevo, E, Pach, J, Pinchasi, R, Pinchasi, R, and Smorodinsky, S. "Lenses in arrangements of pseudocircles and their applications." Proceedings of the Annual Symposium on Computational Geometry (January 1, 2002): 123132.
 Agarwal, PK, Basch, J, Guibas, LJ, Hershberger, J, and Zhang, L. "Deformable freespace tilings for kinetic collision detection." International Journal of Robotics Research 21, no. 3 (2002): 179197. Full Text
 Agarwal, PK, Berg, MD, Gudmundsson, J, Hammar, M, and Haverkort, HJ. "Boxtrees and Rtrees with nearoptimal query time." Discrete and Computational Geometry 28, no. 3 (2002): 291312. Full Text
 Agarwal, PK, Berg, MD, HarPeled, S, Overmars, MH, Sharir, M, and Vahrenhold, J. "Reporting intersecting pairs of convex polytopes in two and three dimensions." Computational Geometry: Theory and Applications 23, no. 2 (2002): 195207.
 Agarwal, PK, Bhattacharya, BK, and Sen, S. "Improved algorithms for uniform partitions of points." Algorithmica (New York) 32, no. 4 (2002): 521539.
 Agarwal, PK, Biedl, T, Lazard, S, Robbins, S, Suri, S, and Whitesides, S. "Curvatureconstrained shortest paths in a convex polygon." SIAM Journal on Computing 31, no. 6 (2002): 18141851. Full Text
 Agarwal, PK, Flato, E, and Halperin, D. "Polygon decomposition for efficient construction of Minkowski sums." Computational Geometry: Theory and Applications 21, no. 12 (2002): 3961.
 Agarwal, PK, Guibas, LJ, Edelsbrunner, H, Erickson, J, Isard, M, HarPeled, S, Hershberger, J, Jensen, C, Kavraki, L, Koehl, P, Lin, M, Manocha, D, Metaxas, D, Mirtich, B, Mount, D, Muthukrishnan, S, Pai, D, Sacks, E, Snoeyink, J, Suri, S, and Wolefson, O. "Algorithmic issues in modeling motion." ACM Computing Surveys 34, no. 4 (2002): 550572. Full Text
 Agarwal, PK, HarPeled, S, and Karia, M. "Computing approximate shortest paths on convex polytopes." Algorithmica (New York) 33, no. 2 (2002): 227242.
 Agarwal, PK, and Procopiuc, CM. "Exact and approximation algorithms for clustering." Algorithmica (New York) 33, no. 2 (2002): 201226.
 Agarwal, PK, and Sharir, M. "The number of congruent simplices in a point set." Discrete and Computational Geometry 28, no. 2 (2002): 123150. Full Text
 Procopiuc, CM, Jones, M, Agarwal, PK, and Murali, TM. "A Monte Carlo algorithm for fast projective clustering." Proceedings of the ACM SIGMOD International Conference on Management of Data (2002): 418427.
 Agarwal, PK, Aronov, B, and Sharir, M. "On the complexity of many faces in arrangements of circles." Annual Symposium on Foundations of Computer Science  Proceedings (2001): 7483.
 Agarwal, PK, Aronov, B, and Sharir, M. "Exact and approximation algorithms for minimumwidth cylindrical shells." Discrete and Computanional Geometry 26, no. 3 (2001): 307320.
 Agarwal, PK, Berg, MD, Gudmundsson, J, Hammar, M, and Haverkort, HJ. "Boxtrees and Rtrees with nearoptimal query time." Proceedings of the Annual Symposium on Computational Geometry (2001): 124133.
 Agarwal, PK, Collins, AD, and Harer, JL. "Minimal trap design." Proceedings  IEEE International Conference on Robotics and Automation 3 (2001): 22432248.
 Agarwal, PK, Guibas, LJ, Hershberger, J, and Veach, E. "Maintaining the extent of a moving point set." Discrete and Computanional Geometry 26, no. 3 (2001): 353374.
 Agarwal, PK, and HalPeled, S. "Maintaining approximate extent measures of moving points." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (2001): 148157.
 Agarwal, PK, and Sharir, M. "On the number of congruent simplices in a point set." Proceedings of the Annual Symposium on Computational Geometry (2001): 19.
 Agarwal, PK, Arge, L, Erickson, J, Franciosa, PG, and Vitter, JS. "Efficient searching with linear constraints." Journal of Computer and System Sciences 61, no. 2 (2000): 194216. Full Text
 Agarwal, PK, Arge, L, and Erickson, J. "Indexing moving points." Proceedings of the ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems (2000): 175186.
 Agarwal, PK, Aronov, B, HarPeled, S, and Sharir, M. "Approximation Algorithms for MinimumWidth Annuli and Shells." Discrete and Computanional Geometry 24, no. 4 (2000): 687705.
 Agarwal, PK, Aronov, B, and Sharir, M. "Exact and approximation algorithms for minimumwidth cylindrical shells." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (2000): 510517.
 Agarwal, PK, Basch, J, Berg, MD, Guibas, LJ, and Hershberger, J. "Lower Bounds for Kinetic Planar Subdivisions." Discrete & Computational Geometry 24 (2000): 721733. Full Text
 Agarwal, PK, Grove, EF, Murali, TM, and Vitter, JS. "Binary space partitions for fat rectangles." SIAM Journal on Computing 29, no. 5 (2000): 14221448. Full Text
 Agarwal, PK, Guibas, LJ, Murali, TM, and Vitter, JS. "Cylindrical static and kinetic binary space partitions." Computational Geometry: Theory and Applications 16, no. 2 (2000): 103127.
 Agarwal, PK, HarPeled, S, and Karia, M. "Computing approximate shortest paths on convex polytopes." Proceedings of the Annual Symposium on Computational Geometry (2000): 270279.
 Agarwal, PK, and Desikan, PK. "Approximation algorithms for layered manufacturing." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (2000): 528537.
 Agarwal, PK, and Procopiuc, CM. "Approximation algorithms for projective clustering." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (2000): 538547.
 Agarwal, PK, and Sharir, M. "Pipes, Cigars, and Kreplach: The Union of Minkowski Sums in Three Dimensions." Discrete and Computanional Geometry 24, no. 4 (2000): 645685.
 Agarwal, PK, and Varadarajan, KR. "Efficient algorithms for approximating polygonal chains." Discrete and Computanional Geometry 23, no. 2 (2000): 273291.
 Agarwal, PK, and Wanq, H. "Approximation algorithms for curvatureconstrained shortest paths." SIAM Journal on Computing 30, no. 6 (2000): 17391772.
 Varadarajan, KR, and Agarwal, PK. "Approximating shortest paths on a nonconvex polyhedron." SIAM Journal on Computing 30, no. 4 (2000): 13211340.
 Agarwal, PK, Arge, L, Brodal, GS, and Vitter, JS. "I/Oefficient dynamic point location in monotone planar subdivisions." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (1999): 1120.
 Agarwal, PK, Aronov, B, HarPeled, S, and Sharir, M. "Approximation and exact algorithms for minimumwidth annuli and shells." Proceedings of the Annual Symposium on Computational Geometry (1999): 380389.
 Agarwal, PK, Aronov, B, and Sharir, M. "Motion planning for a convex polygon in a polygonal environment." Discrete and Computational Geometry 22, no. 2 (1999): 201221.
 Agarwal, PK, Aronov, B, and Sharir, M. "Line transversals of balls and smallest enclosing cylinders in three dimensions." Discrete and Computational Geometry 21, no. 3 (1999): 373388.
 Agarwal, PK, Basch, J, Berg, MD, Guibas, LJ, and Hershberger, J. "Lower bounds for kinetic planar subdivisions." Proceedings of the Annual Symposium on Computational Geometry (1999): 247254.
 Agarwal, PK, Efrat, A, and Sharir, M. "Vertical decomposition of shallow levels in 3dimensional arrangements and its applications." SIAM Journal on Computing 29, no. 3 (1999): 912953.
 Agarwal, PK, and O'Rourke, J. "Open Problems Presented at SCG'98." Journal of Algorithms 30, no. 2 (1999): 449453.
 Agarwal, PK, and Sharir, M. "Motion planning of a ball amid segments in three dimensions." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (1999): 2130.
 Agarwal, PK, and Sharir, M. "Pipes, cigars, and kreplach: The union of Minkowski sums in three dimensions." Proceedings of the Annual Symposium on Computational Geometry (1999): 143153.
 Varadarajan, KR, and Agarwal, PK. "Approximation algorithms for bipartite and nonbipartite matching in the plane." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (1999): 805814.
 Agarwal, PK, Amenta, N, and Sharir, M. "Largest placement of one convex polygon inside another." Discrete and Computational Geometry 19, no. 1 (1998): 95104.
 Agarwal, PK, Arge, L, Erickson, J, Franciosa, PG, and Vitter, JS. "Efficient searching with linear constraints." Proceedings of the ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems (1998): 169178.
 Agarwal, PK, Arge, L, Murali, TM, Varadarajan, KR, and Vitter, JS. "I/Oefficient algorithms for contourline extraction and planar graph blocking." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (1998): 117126.
 Agarwal, PK, Aronov, B, Chan, TM, and Sharir, M. "On levels in arrangements of lines, segments, planes, and triangles." Discrete and Computational Geometry 19, no. 3 (1998): 315331.
 Agarwal, PK, Berg, MD, Matoušek, J, and Schwarzkopf, O. "Constructing Levels in Arrangements and Higher Order Voronoi Diagrams." SIAM Journal on Computing 27, no. 3 (1998): 654667.
 Agarwal, PK, Biedl, T, Lazard, S, Robbins, S, Suri, S, and Whitesides, S. "Curvatureconstrained shortest paths in a convex polygon." Proceedings of the Annual Symposium on Computational Geometry (1998): 392401.
 Agarwal, PK, Eppstein, D, Guibas, LJ, and Henzinger, MR. "Parametric and kinetic minimum spanning trees." Annual Symposium on Foundations of Computer Science  Proceedings (1998): 596605.
 Agarwal, PK, Erickson, J, and Guibas, LJ. "Kinetic binary space partitions for intersecting segments and disjoint triangles." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (1998): 107116.
 Agarwal, PK, Kreveld, MV, and Suri, S. "Label placement by maximum independent set in rectangles." Computational Geometry: Theory and Applications 11, no. 34 (1998): 209218.
 Agarwal, PK, Matoušek, J, and Schwarzkopf, O. "Computing many faces in arrangements of lines and segments." SIAM Journal on Computing 27, no. 2 (1998): 491505.
 Agarwal, PK, Sharir, M, and Welzl, E. "The discrete 2center problem." Discrete and Computational Geometry 20, no. 3 (1998): 287305.
 Agarwal, PK, and O'Rourke, J. "Computational geometry column 34." International Journal of Computational Geometry and Applications 8, no. 56 (1998): 637642.
 Agarwal, PK, and Procopiuc, CM. "Exact and approximation algorithms for clustering." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (1998): 658667.
 Agarwal, PK, and Sharir, M. "Efficient algorithms for geometric optimization." ACM Computing Surveys 30, no. 4 (1998): 448458.
 Agarwal, PK. "Surface approximation and geometric partitions." SIAM Journal on Computing 27, no. 4 (1998): 10161035.
 Agarwal, PK, Aronov, B, O'Rourke, J, and Schevon, CA. "Star unfolding of a polytope with applications." SIAM Journal on Computing 26, no. 6 (1997): 16891713.
 Agarwal, PK, Aronov, B, Pach, J, Pollack, R, and Sharir, M. "Quasiplanar graphs have a linear number of edges." Combinatorica 17, no. 1 (1997): 19.
 Agarwal, PK, Aronov, B, and Sharir, M. "Computing envelopes in four dimensions with applications." SIAM Journal on Computing 26, no. 6 (1997): 17141732.
 Agarwal, PK, Aronov, B, and Sharir, M. "Line transversals of balls and smallest enclosing cylinders in three dimensions." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (1997): 483492.
 Agarwal, PK, Aronov, B, and Sharir, M. "On levels in arrangements of lines, segments, planes, and triangles." Proceedings of the Annual Symposium on Computational Geometry (1997): 3038.
 Agarwal, PK, Guibas, LJ, Murali, TM, and Vitter, JS. "Cylindrical static and kinetic binary space partitions." Proceedings of the Annual Symposium on Computational Geometry (1997): 3948.
 Agarwal, PK, HarPeled, S, Sharir, M, and Varadarajan, KR. "Approximating shortest paths on a convex polytope in three dimensions." Journal of the ACM 44, no. 4 (1997): 567584.
 Agarwal, PK, Latombe, JC, Motwani, R, and Raghavan, P. "Nonholonomic path planning for pushing a disk among obstacles." Proceedings  IEEE International Conference on Robotics and Automation 4 (1997): 31243129.
 Agarwal, PK, Murali, TM, and Vitter, JS. "Practical techniques for constructing Binary Space Partitions for orthogonal rectangles." Proceedings of the Annual Symposium on Computational Geometry (1997): 382384.
 Agarwal, PK, Sharir, M, and Welzl, E. "Discrete 2center problem." Proceedings of the Annual Symposium on Computational Geometry (1997): 147155.
 Agarwal, PK, and Desikan, PK. "Efficient algorithm for terrain simplification." Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms (1997): 139147.
 Varadarajan, KR, and Agarwal, PK. "Linear approximation of simple objects." Information Processing Letters 62, no. 2 (1997): 8994.
 Varadarajan, KR, and Agarwal, PK. "Approximating shortest paths on a nonconvex polyhedron." Annual Symposium on Foundations of Computer Science  Proceedings (1997): 182191.
 Agarwal, PK, Grove, EF, Murali, TM, and Vitter, JS. "Binary space partitions for fat rectangles." Annual Symposium on Foundations of Computer Science  Proceedings (1996): 482491.
 Agarwal, PK, Schwarzkopf, O, and Sharir, M. "The overlay of lower envelopes and its applications." Discrete and Computational Geometry 15, no. 1 (1996): 113.
 Agarwal, PK, and Kreveld, MV. "Connected Component and Simple Polygon Intersection Searching." Algorithmica (New York) 15, no. 6 (1996): 626660.
 Agarwal, PK, and Sen, S. "Selection in Monotone Matrices and Computing kth Nearest Neighbors." Journal of Algorithms 20, no. 3 (1996): 581601. Full Text
 Agarwal, PK, and Sharir, M. "Efficient randomized algorithms for some geometric optimization problems." Discrete and Computational Geometry 16, no. 4 (1996): 317337.
 Agarwal, PK, and Sharir, M. "Ray Shooting Amidst Convex Polygons in 2D." Journal of Algorithms 21, no. 3 (1996): 508519. Full Text
 Agarwal, PK, and Sharir, M. "Ray shooting amidst convex polyhedra and polyhedral terrains in three dimensions." SIAM Journal on Computing 25, no. 1 (1996): 100116.
 Cohen, J, Varshney, A, Manocha, D, Turk, G, Weber, H, Agarwal, P, Brooks, F, and Wright, W. "Simplification envelopes." Proceedings of the ACM SIGGRAPH Conference on Computer Graphics (1996): 119128.
 Frey, HC, and Agarwal, P. "Probabilistic modeling and optimization of clean coal technologies: case studies of the externallyfired combined cycle." Proceedings of the Air & Waste Management Association's Annual Meeting & Exhibition (1996): 16pp.
 Frey, HC, and Agarwal, P. "Probabilistic analysis and optimization of new power generation technologies: a case study for the externallyfired combined cycle." Proceedings of the American Power Conference 1 (1996): 5257.
 Tamassia, R, Agarwal, PK, Amato, N, Chen, DZ, Dobkin, D, Drysdale, S, Fortune, S, Goodrich, MT, Hershberger, J, O'Rourke, J, Preparata, FP, Sack, JR, Suri, S, Tollis, I, Vitter, JS, and Whitesides, S. "Strategic directions in computational geometry." ACM Computing Surveys 28, no. 4 (1996): 591606.
 Agarwal, P. "Cellular segregation and engulfment simulations using the cell programming language." Journal of Theoretical Biology 176, no. 1 (1995): 7989. Full Text
 Agarwal, PK, Katz, MJ, and Sharir, M. "Computing depth orders for fat objects and related problems." Computational Geometry: Theory and Applications 5, no. 4 (1995): 187206.
 Agarwal, PK, and Matoušek, J. "Dynamic halfspace range reporting and its applications." Algorithmica 13, no. 4 (1995): 325345. Full Text
 Agarwal, P, and Sharir, M. "Planar geometric location problems." Algorithmica (New York) 11, no. 2 (1994): 185195.
 Agarwal, P. "Simulation of aggregation in Dictyostelium using the cell programming language." Computer Applications in the Biosciences 10, no. 6 (1994): 647655.
 Agarwal, PK, Alon, N, Aronov, B, and Suri, S. "Can visibility graphs Be represented compactly?." Discrete & Computational Geometry 12, no. 1 (1994): 347365. Full Text
 Agarwal, PK, Aronov, B, and Sharir, M. "Computing envelopes in four dimensions with applications." Proceedings of the Annual Symposium on Computational Geometry (1994): 348358.
 Agarwal, PK, Berg, MD, Matousek, J, and Schwarzkopf, O. "Constructing levels in arrangements and higher order Voronoi diagrams." Proceedings of the Annual Symposium on Computational Geometry (1994): 6775.
 Agarwal, PK, Matousek, J, and Schwarzkopf, O. "Computing many faces in arrangements of lines and segments." Proceedings of the Annual Symposium on Computational Geometry (1994): 7684.
 Agarwal, PK, Sharir, M, and Toledo, S. "Applications of Parametric Searching in Geometric Optimization." Journal of Algorithms 17, no. 3 (1994): 292318. Full Text
 Agarwal, PK, and Matousek, J. "On range searching with semialgebraic sets." Discrete & Computational Geometry 11, no. 1 (1994): 393418. Full Text
 Agarwal, PK, and Sharir, M. "On the number of views of polyhedral terrains." Discrete & Computational Geometry 12, no. 1 (1994): 177182. Full Text
 Agarwal, PK, and Suri, S. "Surface approximation and geometric partitions." Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms (1994): 2433.
 Agarwal, PK. "On stabbling lines for convex polyhedra in 3D." Computational Geometry: Theory and Applications 4, no. 4 (1994): 177189.
 Agarwal, PK, Alon, N, Aronov, B, and Suri, S. "Can visibility graphs be represented compactly?." Proceedings of the 9th Annual Symposium on Computational Geometry (1993): 338347.
 Agarwal, PK, Aronov, B, Sharir, M, and Suri, S. "Selecting distances in the plane." Algorithmica 9, no. 5 (1993): 495514. Full Text
 Agarwal, PK, Efrat, A, Sharir, M, and Toledo, S. "Computing a Segment Center for a Planar Point Set." Journal of Algorithms 15, no. 2 (1993): 314323. Full Text
 Agarwal, PK, Pellegrini, M, and Sharir, M. "Counting circular arc intersections." SIAM Journal on Computing 22, no. 4 (1993): 778793.
 Agarwal, PK, Vankreveld, M, and Overmars, M. "Intersection Queries in Curved Objects." Journal of Algorithms 15, no. 2 (1993): 229266. Full Text
 Agarwal, PK, and Matousek, J. "Ray shooting and parametric search." SIAM Journal on Computing 22, no. 4 (1993): 794806.
 Agarwal, PK, and Sharir, M. "Applications of a new spacepartitioning technique." Discrete & Computational Geometry 9, no. 1 (1993): 1138. Full Text
 Agarwal, PK, and Sharir, M. "Ray shooting amidst convex polytopes in three dimensions." Proceedings of the Fourth Annual ACMSIAM Symposium on Discrete Algorithms (1993): 260270.
 Agarwal, PK, and Sharir, M. "Circle Shooting in a Simple Polygon." Journal of Algorithms 14, no. 1 (1993): 6987. Full Text
 Agarwal, PK, Matoušek, J, and Suri, S. "Farthest neighbors, maximum spanning trees and related problems in higher dimensions." Computational Geometry: Theory and Applications 1, no. 4 (1992): 189201.
 Agarwal, PK, and Aronov, B. "Counting facets and incidences." Discrete & Computational Geometry 7, no. 1 (1992): 359369. Full Text
 Agarwal, PK, and Matousek, J. "Ray shooting and parametric search." Conference Proceedings of the Annual ACM Symposium on Theory of Computing (1992): 517526.
 Agarwal, PK, and Matoušek, J. "Relative neighborhood graphs in three dimensions." Computational Geometry: Theory and Applications 2, no. 1 (1992): 114.
 Agarwal, PK, and Shing, MT. "Oriented aligned rectangle packing problem." European Journal of Operational Research 62, no. 2 (1992): 210220.
 Kreveld, MV, Overmars, M, and Agarwal, PK. "Intersection queries in sets of disks." BIT 32, no. 2 (1992): 268279. Full Text
 Agarwal, PK, Aggarwal, A, Aronov, B, Kosaraju, SR, Schieber, B, and Suri, S. "Computing external farthest neighbors for a simple polygon." Discrete Applied Mathematics 31, no. 2 (1991): 97111.
 Agarwal, PK, Edelsbrunner, H, Schwarzkopf, O, and Welzl, E. "Euclidean minimum spanning trees and bichromatic closest pairs." Discrete & Computational Geometry 6, no. 1 (1991): 407422. Full Text
 Agarwal, PK, and Sharir, M. "Offline dynamic maintenance of the width of a planar point set." Computational Geometry: Theory and Applications 1, no. 2 (1991): 6578.
 Agarwal, PK, Aronov, B, Sharir, M, and Suri, S. "Selecting distances in the plane." (1990): 321331.
 Agarwal, PK, Edelsbrunner, H, Schwarzkopf, O, and Welzl, E. "Euclidean minimum spanning trees and bichromatic closest pairs." (1990): 203210.
 Agarwal, PK, and Sharir, M. "Redblue intersection detection algorithms, with applications to motion planning and collision detection." SIAM Journal on Computing 19, no. 2 (1990): 297321.
 Agarwal, PK. "Partitioning arrangements of lines II: Applications." Discrete & Computational Geometry 5, no. 1 (1990): 533573. Full Text
 Agarwal, PK. "Partitioning arrangements of lines I: An efficient deterministic algorithm." Discrete & Computational Geometry 5, no. 1 (1990): 449483. Full Text
 Agarwal, PK, Sharir, M, and Shor, P. "Sharp upper and lower bounds on the length of general DavenportSchinzel sequences." Journal of Combinatorial Theory, Series A 52, no. 2 (1989): 228274.
 Agarwal, PK, Avraham, RB, Kaplan, H, and Sharir, M. "Computing the Discrete Fréchet Distance in Subquadratic Time." Link to Item
 Sankararaman, S, Efrat, A, Ramasubramanian, S, and Agarwal, PK. "On channeldiscontinuityconstraint routing in wireless networks." Ad Hoc Networks . Full Text
 Shaharabani, D, Salzman, O, Agarwal, PK, and Halperin, D. "Sparsification of MotionPlanning Roadmaps by Edge Contraction." Link to Item

 Teaching & Mentoring

Recent Courses
Some information on this profile has been compiled automatically from Duke databases and external sources. (Our About page explains how this works.) If you see a problem with the information, please write to Scholars@Duke and let us know. We will reply promptly.