Scholars@Duke

• 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

  • 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

  • Fellow of National Academy of Public Administration. National Academy of Public Administration. 2007
  • Fellow. Association for Computing Machinery. 2002
  • Sloan Research Fellowship-Computer Science. Alfred P. Sloan Foundation. 1996
• Publications & Artistic Works
• 

  Selected Publications

  • Books

    • Agarwal, PK, Akutsu, T, Amihood, A, Apostolico, A, Benham, C, Benson, G, Blanchette, M, El-Mabrouk, 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.

  • Book Sections

    • Agarwal, PK. "Simplex range searching and its variants: A review." In A Journey through Discrete Mathematics: A Tribute to Jiri Matousek, 1-30. January 1, 2017.  Full Text

  • Conference Papers

    • Agarwal, PK, Fox, K, and Nath, A. "Maintaining reeb graphs of triangulated 2-manifolds." January 1, 2018.  Full Text
    • Rav, M, Lowe, A, and Agarwal, PK. "Flood Risk Analysis on Terrains." November 7, 2017.  Full Text
    • Agarwal, PK, Rubin, N, and Sharir, M. "Approximate nearest neighbor search amid higher-dimensional flats." September 1, 2017.  Full Text
    • Agarwal, PK, Kumar, N, Sintos, S, and Suri, S. "Efficient algorithms for k-regret minimizing sets." August 1, 2017.  Full Text
    • Agarwal, PK, Fox, K, Panigrahi, D, Varadarajan, KR, and Xiao, A. "Faster algorithms for the geometric transportation problem." June 1, 2017.  Full Text
    • Garg, N, Sadiq, M, and Agarwal, P. "GOASREP: Goal oriented approach for software requirements elicitation and prioritization using analytic hierarchy process." January 1, 2017.  Full Text
    • Wu, Y, Gao, J, Agarwal, PK, and Yang, J. "Finding diverse, high-value representatives on a surface of answers." January 1, 2017.
    • 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 nearest-neighbor searching data structures." June 15, 2016.  Full Text
    • Agarwal, PK, Kumar, N, Sintos, S, and Suri, S. "Range-max queries on uncertain data." June 15, 2016.  Full Text
    • Agarwal, PK, Fox, K, and Salzman, O. "An efficient algorithm for computing high-quality paths amid polygonal obstacles." January 1, 2016.
    • Pan, J, Rao, V, Agarwal, PK, and Gelfand, AE. "Markov-modulated marked poisson processes for check-in data." January 1, 2016.
    • Zhang, W, Agarwal, PK, and Mukherjee, S. "Contour trees of uncertain terrains." November 3, 2015.  Full Text
    • Agarwal, P. "Message from program chair." January 1, 2015.  Full Text
    • Garg, N, Agarwal, P, and Khan, S. "Recent advancements in requirement elicitation and prioritization techniques." January 1, 2015.  Full Text
    • Gupta, P, and Agarwal, P. "Experimental study & analysis of genetic operators for alignment of multiple biological sequences." January 1, 2015.  Full Text
    • Sekhon, A, and Agarwal, P. "Face recognition using back propagation neural network technique." January 1, 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, Har-Peled, S, Suri, S, YIldIz, H, and Zhang, W. "Convex hulls under uncertainty." January 1, 2014.  Full Text
    • Agarwal, P, Gupta, R, Maheswari, T, Agarwal, P, Yadav, S, and Bali, V. "A genetic algorithm for alignment of multiple DNA sequences." December 1, 2012.  Full Text
    • Agarwal, P, and Rizvi, SAM. "A technique based on neural network for predicting the secondary structure of proteins." March 31, 2008.  Full Text
    • Rizvi, SAM, and Agarwal, P. "A time efficient algorithm for finding longest common subsequence from two molecular sequences." December 1, 2007.  Full Text
    • Agarwal, PK, Xie, J, Yang, J, and Yu, H. "Scalable continuous query processing by tracking hotspots." December 1, 2006.
    • Rizvi, SAM, and Agarwal, P. "A new bucket-based algorithm for finding LCS from two given molecular sequences." November 14, 2006.  Full Text
    • Agarwal, PK, Cabello, S, Sellarès, JA, and Sharir, M. "Computing a Center-Transversal 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 kd-Trees." 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, Har-Peled, S, Mustafa, NH, and Wang, Y. "Near-Linear Time Approximation Algorithms for Curve Simplification." Springer, 2002.  Full Text
    • Agarwal, PK, Procopiuc, CM, and Varadarajan, KR. "Approximation Algorithms for k-Line Center." Springer, 2002.  Full Text
    • Agarwal, PK, and Sharir, M. "Pseudo-line arrangements: duality, algorithms, and applications." ACM/SIAM, 2002.
    • Procopiuc, CM, Agarwal, PK, and Har-Peled, S. "STAR-Tree: An Efficient Self-Adjusting 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, Har-Peled, 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, Har-Peled, 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. "Output-Sensitive 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, Berg, MD, Halperin, D, and Sharir, M. "Efficient Generation of k-Directional Assembly Sequences." ACM/SIAM, 1996.
    • Wang, H, and Agarwal, PK. "Approximation Algorithms for Curvature-Constrained Shortest Paths." ACM/SIAM, 1996.
    • Agarwal, PK, Aronov, B, Pach, J, Pollack, R, and Sharir, M. "Quasi-Planar Graphs Have a Linear Number of Edges." Springer, 1995.  Full Text
    • Agarwal, PK, Aronov, B, and Suri, S. "Stabbing Triangulations by Lines in 3D." ACM, 1995.  Full Text
    • Agarwal, PK, Efrat, A, and Sharir, M. "Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications." ACM, 1995.  Full Text
    • Agarwal, PK, Schwarzkopf, O, and Sharir, M. "The Overlay of Lower Envelopes in Three Dimensions and Its Applications." ACM, 1995.  Full Text
    • Agarwal, PK, and Sharir, M. "Efficient Randomized Algorithms for Some Geometric Optimization Problems." ACM, 1995.  Full Text
    • Agarwal, PK, Katz, MJ, and Sharir, M. "Computing Depth Orders and Related Problems." Springer, 1994.  Full Text
    • Agarwal, PK, and Sen, S. "Selection in Monotone Matrices and Computing kth Nearest Neighbors." Springer, 1994.  Full Text
    • Agarwal, PK, and Van Kreveld, M. "Connected component and simple polygon intersection searching." January 1, 1993.
    • Agarwal, PK, Sharir, M, and Toledo, S. "Applications of Parametric Searching in Geometric Optimization." ACM/SIAM, 1992.
    • Agarwal, PK, and Matousek, J. "On Range Searching with Semialgebraic Sets." Springer, 1992.  Full Text
    • Agarwal, PK, and Matousek, J. "Relative Neighborhood Graphs in Three Dimensions." ACM/SIAM, 1992.
    • Agarwal, PK, and van Kreveld, M. "Implicit point location of line segments, with an arrangements an application to motion planning." January 1, 1992.
    • Agarwal, PK, Aronov, B, O'Rourke, J, and Schevon, CA. "Star Unfolding of a Polytope with Applications (Extended Abstract)." Springer, 1990.  Full Text
    • Kreveld, MJV, Overmars, MH, and Agarwal, PK. "Intersection Queries in Sets of Disks." Springer, 1990.  Full Text

  • Journal Articles

    • Agarwal, PK, Efrat, A, Sankararaman, S, and Zhang, W. "Nearest-Neighbor Searching Under Uncertainty I." Discrete & Computational Geometry 58, no. 3 (October 2017): 705-745.  Full Text
    • Agarwal, PK, Har-Peled, S, Suri, S, Yıldız, H, and Zhang, W. "Convex Hulls Under Uncertainty." Algorithmica 79, no. 2 (October 2017): 340-367.  Full Text
    • Wu, Y, Agarwal, PK, Li, C, Yang, J, and Yu, C. "Computational Fact Checking through Query Perturbations." ACM Transactions on Database Systems 42, no. 1 (January 9, 2017): 1-41.  Full Text
    • Agarwal, PK, Kumar, N, Sintos, S, and Suri, S. "Range-max queries on uncertain data (Accepted)." Journal of Computer and System Sciences (January 1, 2017).  Full Text
    • Agarwal, PK, Aronov, B, Har-Peled, S, Phillips, JM, Yi, K, and Zhang, W. "Nearest-Neighbor Searching Under Uncertainty II." ACM Transactions on Algorithms 13, no. 1 (October 10, 2016): 1-25.  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.1-6.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): 311-325.  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): 905-929.  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): 871-904.  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): 796-811.  Full Text
    • Agarwal, PK, Fox, K, Nath, A, Sidiropoulos, A, and Wang, Y. "Computing the Gromov-Hausdorff 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): 529-540.  Full Text
    • Agarwal, PK, and Sharathkumar, R. "Streaming Algorithms for Extent Problems in High Dimensions." Algorithmica 72, no. 1 (2015): 83-98.  Full Text
    • Salzman, O, Shaharabani, D, Agarwal, PK, and Halperin, D. "Sparsification of motion-planning roadmaps by edge contraction." The International Journal of Robotics Research 33, no. 14 (December 2014): 1711-1725.  Full Text
    • Agarwal, PK, Har-Peled, S, Kaplan, H, and Sharir, M. "Union of Random Minkowski Sums and Network Vulnerability Analysis." Discrete & Computational Geometry 52, no. 3 (October 2014): 551-582.  Full Text
    • Wu, Y, Agarwal, PK, Li, C, Yang, J, and Yu, C. "Toward computational fact-checking." Proceedings of the VLDB Endowment 7, no. 7 (March 1, 2014): 589-600.  Full Text
    • Sankararaman, S, Efrat, A, Ramasubramanian, S, and Agarwal, PK. "On channel-discontinuity-constraint routing in wireless networks." Ad Hoc Networks 13, no. PART A (February 1, 2014): 153-169.  Full Text
    • Agarwal, PK, Har-Peled, 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): 37-48.  Full Text
    • Agarwal, PK, and Pan, J. "Near-linear algorithms for geometric hitting sets and set covers." Proceedings of the Annual Symposium on Computational Geometry (January 1, 2014): 271-279.  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): 555-564.  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): 1063-1066.  Full Text
    • Yu, A, Agarwal, PK, and Yang, J. "Top-k preferences in high dimensions." Proceedings - International Conference on Data Engineering (January 1, 2014): 748-759.  Full Text
    • Agarwal, PK, Aronov, B, Van Kreveld, M, Löffler, M, and Silveira, RI. "Computing correlation between piecewise-linear functions." SIAM Journal on Computing 42, no. 5 (December 26, 2013): 1867-1887.  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): 2039-2062.  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): 14-23.  Full Text
    • Sankararaman, S, Agarwal, PK, Mølhave, T, Pan, J, and Boedihardjo, AP. "Model-driven matching and segmentation of trajectories." GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems (December 1, 2013): 234-243.  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): 1525-1538.  Full Text
    • Afshani, P, Agarwal, PK, Arge, L, Larsen, KG, and Phillips, JM. "(Approximate) Uncertain Skylines." Theory of Computing Systems 52, no. 3 (2013): 342-366.  Full Text
    • Agarwal, PK, Arge, L, Govindarajan, S, Yang, J, and Yi, K. "Efficient external memory structures for range-aggregate queries." Computational Geometry: Theory and Applications 46, no. 3 (2013): 358-370.  Full Text
    • Agarwal, PK, Aronov, B, Har-Peled, S, Phillips, JM, Yi, K, and Zhang, W. "Nearest neighbor searching under uncertainty II." Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (2013): 115-126.  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, Har-Peled, S, and Yu, H. "EMBEDDINGS OF SURFACES, CURVES, AND MOVING POINTS IN EUCLIDEAN SPACE." SIAM JOURNAL ON COMPUTING 42, no. 2 (2013): 442-458.  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): 177-186.
    • 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): 1-16.  Full Text
    • Afshani, P, Agarwal, PK, Arge, L, Larsen, KG, and Phillips, JM. "(Approximate) Uncertain Skylines." Theory of Computing Systems (2012): 1-25.  Full Text
    • Agarwal, PK, Arge, L, Kaplan, H, Molad, E, Tarjan, RE, and Yi, K. "An optimal dynamic data structure for stabbing-semigroup queries." SIAM Journal on Computing 41, no. 1 (2012): 104-127.  Full Text
    • Agarwal, PK, Avraham, RB, and Sharir, M. "The 2-center problem in three dimensions." Computational Geometry: Theory and Applications (2012).  Full Text
    • Agarwal, PK, Cheng, S-W, 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 SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (2012): 23-34.  Full Text
    • Agarwal, PK, Efrat, A, Sankararaman, S, and Zhang, W. "Nearest-neighbor searching under uncertainty." Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (2012): 225-236.  Full Text
    • Agarwal, PK, Ezra, E, and Sharir, M. "Near-linear approximation algorithms for geometric hitting sets." Algorithmica 63, no. 1-2 (2012): 1-25.  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): 420-429.  Full Text
    • Sharathkumar, R, and Agarwal, PK. "A near-linear time ε-approximation algorithm for geometric bipartite matching." Proceedings of the Annual ACM Symposium on Theory of Computing (2012): 385-394.  Full Text
    • Sharathkumar, R, and Agarwal, PK. "Algorithms for the transportation problem in geometric settings." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2012): 306-317.
    • 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): 1487-1495.  Full Text
    • Yu, A, Agarwal, PK, and Yang, J. "Subscriber assignment for wide-area content-based publish/subscribe." IEEE Transactions on Knowledge and Data Engineering 24, no. 10 (2012): 1833-1847.  Full Text
    • Yu, A, Agarwal, PK, and Yang, J. "Processing and notifying range top-k subscriptions." Proceedings - International Conference on Data Engineering (2012): 810-821.  Full Text
    • Yu, A, Agarwal, PK, and Yang, J. "Processing a large number of continuous preference top-k queries." Proceedings of the ACM SIGMOD International Conference on Management of Data (2012): 397-408.  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): 1523-1536.  Link to Item
    • Abam, MA, Agarwal, PK, Berg, MD, and Yu, H. "Out-of-order event processing in kinetic data structures." Algorithmica (New York) 60, no. 2 (2011): 250-273.  Full Text
    • Afshani, P, Agarwal, PK, Arge, L, Larsen, KG, and Phillips, JM. "(Approximate) uncertain skylines." ACM International Conference Proceeding Series (2011): 186-196.  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): 1521-1529.  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): 77-86.  Full Text
    • Agarwal, PK, Mølhave, T, and Sadri, B. "I/O-efficieiit contour queries on terrains." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2011): 268-284.
    • 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): 64-73.  Full Text
    • Yu, A, Agarwal, PK, and Yang, J. "Subscriber assignment for wide-area content-based publish/subscribe." Proceedings - International Conference on Data Engineering (2011): 267-278.  Full Text
    • Agarwal, PK, Arge, L, and Yi, K. "I/O-efficient batched union-find 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 piecewise-linear functions." Proceedings of the Annual Symposium on Computational Geometry (2010): 375-383.  Full Text
    • Agarwal, PK, Ben-Avraham, R, and Sharir, M. "The 2-center problem in three dimensions." Proceedings of the Annual Symposium on Computational Geometry (2010): 87-96.  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): 352-390.  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): 1824-1829.  Full Text
    • Agarwal, PK, Efrat, A, Sharathkumar, R, and Yu, H. "On approximate geodesic-distance queries amid deforming point clouds." Springer Tracts in Advanced Robotics 57 (2010): 351-365.  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): 127-136.  Full Text
    • Agarwal, PK, Har-Peled, 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): 384-396.  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): 487-499.  Full Text
    • Agarwal, PK, and Sharathkumar, R. "Streaming algorithms for extent problems in high dimensions." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2010): 1481-1489.
    • Agarwal, PK. "An improved algorithm for computing the volume of the union of cubes." Proceedings of the Annual Symposium on Computational Geometry (2010): 230-239.  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): 172-181.  Full Text
    • Mølhave, T, Agarwal, PK, Arge, L, and Revsbæk, M. "Scalable algorithms for large high-resolution terrain data." ACM International Conference Proceeding Series (2010).  Full Text
    • Sankararaman, S, Efrat, A, Ramasubramanian, S, and Agarwal, PK. "On channel-discontinuity-constraint routing in wireless networks." Proceedings - IEEE INFOCOM (2010).  Full Text
    • Agarwal, PK, Cheng, S-W, Tao, Y, and Yi, K. "Indexing uncertain data." Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (2009): 137-146.  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): 301-314.  Full Text
    • Agarwal, PK, Ezra, E, and Sharir, M. "Near-linear approximation algorithms for geometric hitting sets." Proceedings of the Annual Symposium on Computational Geometry (2009): 23-32.  Full Text
    • Agarwal, PK, Sharathkumar, R, and Yu, H. "Approximate Euclidean shortest paths amid convex obstacles." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2009): 283-292.
    • Agarwal, PK, Xie, J, Yang, J, and Yu, H. "Input-sensitive 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/O-efflcient algorithms for computing contours on a terrain." Proceedings of the Annual Symposium on Computational Geometry (2008): 129-138.  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): 52-63.  Full Text
    • Agarwal, PK, Har-Peled, S, and Yu, H. "Robust shape fitting via peeling and grating coresets." Discrete and Computational Geometry 39, no. 1-3 (2008): 38-58.  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): 42-54.  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. 1-3 (2008): 17-37.  Full Text
    • Agarwal, PK, Sadri, B, and Yu, H. "Untangling triangulations through local explorations." Proceedings of the Annual Symposium on Computational Geometry (2008): 288-297.  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 2-center with outliers." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5193 LNCS (2008): 64-75.  Full Text
    • Chandramouli, B, Yang, J, Agarwal, PK, Yu, A, and Zheng, Y. "ProSem: Scalable wide-area publish/subscribe." Proceedings of the ACM SIGMOD International Conference on Management of Data (2008): 1315-1317.  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): 378-402.  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): 647-659.  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): 131-143.  Full Text  Link to Item
    • Agarwal, PK, Apfelbaum, R, Purdy, G, and Sharir, M. "Similar simplices in a d-dimensional point set." Proceedings of the Annual Symposium on Computational Geometry (2007): 232-238.  Full Text
    • Agarwal, PK, Har-Peled, S, and Yu, H. "Embeddings of surfaces, curves, and moving points in euclidean space." Proceedings of the Annual Symposium on Computational Geometry (2007): 381-389.  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): 294-301.  Full Text
    • Agarwal, PK, and Yu, H. "A space-optimal data-stream algorithm for coresets in the plane." Proceedings of the Annual Symposium on Computational Geometry (2007): 1-10.  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): 661-662.  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): 212-219.  Full Text
    • Flikkema, PG, Agarwal, PK, Clark, JS, Ellis, C, Gelfand, A, Munagala, K, and Yang, J. "From data reverence to data relevance: Model-mediated 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): 988-994.
    • Govindarajan, S, Dietze, MC, Agarwal, PK, and Clark, JS. "A scalable algorithm for dispersing population." Journal of Intelligent Information Systems 29, no. 1 (2007): 39-61.  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): 771-788.  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): 408-422.  Full Text  Link to Item
    • Abam, MA, Agarwal, PK, Berg, MD, and Yu, H. "Out-of-order 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): 624-635.
    • Agarwal, PK, Arge, L, and Yi, K. "I/O-efficient batched union-find and its applications to terrain analysis." Proceedings of the Annual Symposium on Computational Geometry 2006 (2006): 167-176.
    • Agarwal, PK, Aronov, B, and Koltun, V. "Efficient algorithms for bichromatic separability." ACM Transactions on Algorithms 2, no. 2 (2006): 209-227.  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): 455-465.  Full Text
    • Agarwal, PK, Edelsbrunner, H, Harer, J, and Wang, Y. "Extreme elevation on a 2-manifold." Discrete and Computational Geometry 36, no. 4 (2006): 553-572.  Full Text
    • Agarwal, PK, Har-Peled, S, and Yu, H. "Robust shape fitting via peeling and grating coresets." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2006): 182-191.  Full Text
    • Agarwal, PK, Overmars, M, and Sharir, M. "Computing maximally separated sets in the plane." SIAM Journal on Computing 36, no. 3 (2006): 815-834.  Full Text
    • Agarwal, PK, Wang, Y, and Yu, H. "A two-dimensional kinetic triangulation with near-quadratic topological changes." Discrete and Computational Geometry 36, no. 4 (2006): 573-592.  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): 83-95.  Full Text
    • Flikkema, PG, Agarwal, PK, Clark, JS, Ellis, C, Gelfand, A, Munagala, K, and Yang, J. "Model-driven 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): 409-416.  Full Text
    • Phillips, JM, Rudolph, J, and Agarwal, PK. "Segmenting motifs in protein-protein interface surfaces." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4175 LNBI (2006): 207-218.
    • Agarwal, PK, Akutsu, T, Amihood, A, Apostolico, A, Benham, C, Benson, G, Blanchette, M, El-Mabrouk, 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, M-F, 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." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3692 LNBI (2005): V-VI.
    • Agarwal, PK, Arge, L, and Yi, K. "I/O-efficient construction of constrained delaunay triangulations." Lecture Notes in Computer Science 3669 (2005): 355-366.
    • Agarwal, PK, Arge, L, and Yi, K. "An optimal dynamic interval stabbing-max data structure?." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2005): 803-812.
    • Agarwal, PK, Aronov, B, Koltun, V, and Sharir, M. "Lines avoiding unit balls in three dimensions." Discrete and Computanional Geometry 34, no. 2 (2005): 231-250.  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): 346-355.  Full Text
    • Agarwal, PK, Berretty, R-P, and Collins, AD. "A near-quadratic algorithm for fence design." Discrete and Computanional Geometry 33, no. 3 (2005): 463-481.  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): 315-327.  Full Text
    • Agarwal, PK, Har-Peled, S, Mustafa, NH, and Wang, Y. "Near-linear time approximation algorithms for curve simplification." Algorithmica (New York) 42, no. 3-4 (2005): 203-219.  Full Text
    • Agarwal, PK, Procopiuc, CM, and Varadarajan, KR. "Approximation algorithms for a k-line center." Algorithmica (New York) 42, no. 3-4 (2005): 221-230.  Full Text
    • Agarwal, PK, Wang, Y, and Yin, P. "Lower bound for sparse Euclidean spanners." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2005): 670-671.
    • Agarwal, PK, Xie, J, Yang, J, and Yu, H. "Monitoring continuous band-join queries over dynamic data." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3827 LNCS (2005): 349-359.  Full Text
    • Agarwal, PK, and Sharir, M. "Pseudo-line arrangements: Duality, algorithms, and applications." SIAM Journal on Computing 34, no. 3 (2005): 526-552.  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): 64-75.  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. 2-3 SPEC. ISS. (2004): 137-163.  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): 4-15.
    • 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): 36-45.
    • Agarwal, PK, Aronov, B, and Koltun, V. "Efficient Algorithms for Bichromatic Separability." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms 15 (2004): 675-683.
    • Agarwal, PK, Berretty, R-P, and Collins, AD. "A near-quadratic algorithm for fence design." Springer Tracts in Advanced Robotics 7 STAR (2004): 347-362.  Full Text
    • Agarwal, PK, Edelsbrunner, H, Harer, J, and Wang, Y. "Extreme elevation on a 2-manifold." Proceedings of the Annual Symposium on Computational Geometry (2004): 357-365.
    • Agarwal, PK, Edelsbrunner, H, and Wang, Y. "Computing the writhing number of a polygonal knot." Discrete and Computanional Geometry 32, no. 1 (2004): 37-53.  Full Text
    • Agarwal, PK, Har-Peled, S, and Varadarajan, KR. "Approximating extent measures of points." Journal of the ACM 51, no. 4 (2004): 606-635.  Full Text
    • Agarwal, PK, Nevo, E, Pach, J, Pinchasi, R, Sharir, M, and Smorodinsky, S. "Lenses in arrangements of pseudo-circles and their applications." Journal of the ACM 51, no. 2 (2004): 139-186.  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 ACM-SIAM Symposium on Discrete Algorithms 15 (2004): 509-518.
    • Agarwal, PK, Sharir, M, and Welzl, E. "Algorithms for center and tverberg points." Proceedings of the Annual Symposium on Computational Geometry (2004): 61-67.
    • Agarwal, PK, Wang, Y, and Yu, H. "A 2D kinetic triangulation with near-quadratic topological changes." Proceedings of the Annual Symposium on Computational Geometry (2004): 180-189.
    • 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): 127-137.
    • Agarwal, PK, and Mustafa, NH. "K-means projective clustering." Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems 23 (2004): 155-165.
    • Agarwal, PK, and Varadarajan, KR. "A near-linear constant-factor approximation for euclidean bipartite matching?." Proceedings of the Annual Symposium on Computational Geometry (2004): 247-252.
    • 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): 218-229.
    • Govindarajan, S, Dietze, M, Agarwal, PK, and Clark, JS. "A scalable simulator for forest dynamics." Proceedings of the Annual Symposium on Computational Geometry (2004): 106-115.
    • 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): 263-272.
    • Agarwal, PK, Procopiuc, CM, and Varadarajan, KR. "A (1+ε)-approximation algorithm for 2-line-center." Computational Geometry: Theory and Applications 26, no. 2 (October 1, 2003): 119-128.  Full Text
    • Agarwal, PK, Arge, L, Danner, A, and Holland-Minkley, B. "Cache-oblivious data structures for orthogonal range searching." Proceedings of the Annual Symposium on Computational Geometry (2003): 237-245.
    • Agarwal, PK, Arge, L, Yang, J, and Yi, K. "I/O-efficient structures for orthogonal range-max and stabbing-max queries." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2832 (2003): 7-18.
    • Agarwal, PK, Arge, L, and Erickson, J. "Indexing moving points." Journal of Computer and System Sciences 66, no. 1 (2003): 207-243.  Full Text
    • Agarwal, PK, Har-Peled, S, Sharir, M, and Wang, Y. "Hausdorff distance under translation for points and balls." Proceedings of the Annual Symposium on Computational Geometry (2003): 282-291.
    • 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): 544-555.
    • Agarwal, PK, Procopiuc, CM, and Varadarajan, KR. "A (1+ε)-approximation algorithm for 2-line-center." Computational Geometry: Theory and Applications 26, no. 2 (2003): 119-128.  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): 115-139.  Full Text
    • Collins, AD, Agarwal, PK, and Harer, JL. "HPRM: A hierarchical PRM." Proceedings - IEEE International Conference on Robotics and Automation 3 (2003): 4433-4438.
    • Govindarajan, S, Agarwal, PK, and Arge, L. "CRB-tree: An efficient indexing scheme for range-aggregate queries." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2572 (2003): 143-157.
    • Procopiuc, O, Agarwal, PK, Arge, L, and Vitter, JS. "Bkd-tree: A dynamic scalable kd-tree." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2750 (2003): 46-65.
    • Agarwal, P, Nevo, E, Pach, J, Pinchasi, R, Pinchasi, R, and Smorodinsky, S. "Lenses in arrangements of pseudo-circles and their applications." Proceedings of the Annual Symposium on Computational Geometry (January 1, 2002): 123-132.
    • Agarwal, PK, Basch, J, Guibas, LJ, Hershberger, J, and Zhang, L. "Deformable free-space tilings for kinetic collision detection." International Journal of Robotics Research 21, no. 3 (2002): 179-197.  Full Text
    • Agarwal, PK, Berg, MD, Gudmundsson, J, Hammar, M, and Haverkort, HJ. "Box-trees and R-trees with near-optimal query time." Discrete and Computational Geometry 28, no. 3 (2002): 291-312.  Full Text
    • Agarwal, PK, Berg, MD, Har-Peled, 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): 195-207.
    • Agarwal, PK, Bhattacharya, BK, and Sen, S. "Improved algorithms for uniform partitions of points." Algorithmica (New York) 32, no. 4 (2002): 521-539.
    • Agarwal, PK, Biedl, T, Lazard, S, Robbins, S, Suri, S, and Whitesides, S. "Curvature-constrained shortest paths in a convex polygon." SIAM Journal on Computing 31, no. 6 (2002): 1814-1851.  Full Text
    • Agarwal, PK, Flato, E, and Halperin, D. "Polygon decomposition for efficient construction of Minkowski sums." Computational Geometry: Theory and Applications 21, no. 1-2 (2002): 39-61.
    • Agarwal, PK, Guibas, LJ, Edelsbrunner, H, Erickson, J, Isard, M, Har-Peled, 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): 550-572.  Full Text
    • Agarwal, PK, Har-Peled, S, and Karia, M. "Computing approximate shortest paths on convex polytopes." Algorithmica (New York) 33, no. 2 (2002): 227-242.
    • Agarwal, PK, and Procopiuc, CM. "Exact and approximation algorithms for clustering." Algorithmica (New York) 33, no. 2 (2002): 201-226.
    • Agarwal, PK, and Sharir, M. "The number of congruent simplices in a point set." Discrete and Computational Geometry 28, no. 2 (2002): 123-150.  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): 418-427.
    • 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): 74-83.
    • Agarwal, PK, Aronov, B, and Sharir, M. "Exact and approximation algorithms for minimum-width cylindrical shells." Discrete and Computanional Geometry 26, no. 3 (2001): 307-320.
    • Agarwal, PK, Berg, MD, Gudmundsson, J, Hammar, M, and Haverkort, HJ. "Box-trees and R-trees with near-optimal query time." Proceedings of the Annual Symposium on Computational Geometry (2001): 124-133.
    • Agarwal, PK, Collins, AD, and Harer, JL. "Minimal trap design." Proceedings - IEEE International Conference on Robotics and Automation 3 (2001): 2243-2248.
    • 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): 353-374.
    • Agarwal, PK, and Hal-Peled, S. "Maintaining approximate extent measures of moving points." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2001): 148-157.
    • Agarwal, PK, and Sharir, M. "On the number of congruent simplices in a point set." Proceedings of the Annual Symposium on Computational Geometry (2001): 1-9.
    • 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): 194-216.  Full Text
    • Agarwal, PK, Arge, L, and Erickson, J. "Indexing moving points." Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (2000): 175-186.
    • Agarwal, PK, Aronov, B, Har-Peled, S, and Sharir, M. "Approximation Algorithms for Minimum-Width Annuli and Shells." Discrete and Computanional Geometry 24, no. 4 (2000): 687-705.
    • Agarwal, PK, Aronov, B, and Sharir, M. "Exact and approximation algorithms for minimum-width cylindrical shells." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2000): 510-517.
    • Agarwal, PK, Basch, J, Berg, MD, Guibas, LJ, and Hershberger, J. "Lower Bounds for Kinetic Planar Subdivisions." Discrete & Computational Geometry 24 (2000): 721-733.  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): 1422-1448.  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): 103-127.
    • Agarwal, PK, Har-Peled, S, and Karia, M. "Computing approximate shortest paths on convex polytopes." Proceedings of the Annual Symposium on Computational Geometry (2000): 270-279.
    • Agarwal, PK, and Desikan, PK. "Approximation algorithms for layered manufacturing." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2000): 528-537.
    • Agarwal, PK, and Procopiuc, CM. "Approximation algorithms for projective clustering." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2000): 538-547.
    • 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): 645-685.
    • Agarwal, PK, and Varadarajan, KR. "Efficient algorithms for approximating polygonal chains." Discrete and Computanional Geometry 23, no. 2 (2000): 273-291.
    • Agarwal, PK, and Wanq, H. "Approximation algorithms for curvature-constrained shortest paths." SIAM Journal on Computing 30, no. 6 (2000): 1739-1772.
    • Varadarajan, KR, and Agarwal, PK. "Approximating shortest paths on a nonconvex polyhedron." SIAM Journal on Computing 30, no. 4 (2000): 1321-1340.
    • Agarwal, PK, Arge, L, Brodal, GS, and Vitter, JS. "I/O-efficient dynamic point location in monotone planar subdivisions." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (1999): 11-20.
    • Agarwal, PK, Aronov, B, Har-Peled, S, and Sharir, M. "Approximation and exact algorithms for minimum-width annuli and shells." Proceedings of the Annual Symposium on Computational Geometry (1999): 380-389.
    • 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): 201-221.
    • 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): 373-388.
    • 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): 247-254.
    • Agarwal, PK, Efrat, A, and Sharir, M. "Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications." SIAM Journal on Computing 29, no. 3 (1999): 912-953.
    • Agarwal, PK, and O'Rourke, J. "Open Problems Presented at SCG'98." Journal of Algorithms 30, no. 2 (1999): 449-453.
    • Agarwal, PK, and Sharir, M. "Motion planning of a ball amid segments in three dimensions." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (1999): 21-30.
    • 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): 143-153.
    • Varadarajan, KR, and Agarwal, PK. "Approximation algorithms for bipartite and non-bipartite matching in the plane." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (1999): 805-814.
    • Agarwal, PK, Amenta, N, and Sharir, M. "Largest placement of one convex polygon inside another." Discrete and Computational Geometry 19, no. 1 (1998): 95-104.
    • Agarwal, PK, Arge, L, Erickson, J, Franciosa, PG, and Vitter, JS. "Efficient searching with linear constraints." Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (1998): 169-178.
    • Agarwal, PK, Arge, L, Murali, TM, Varadarajan, KR, and Vitter, JS. "I/O-efficient algorithms for contour-line extraction and planar graph blocking." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (1998): 117-126.
    • 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): 315-331.
    • 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): 654-667.
    • Agarwal, PK, Biedl, T, Lazard, S, Robbins, S, Suri, S, and Whitesides, S. "Curvature-constrained shortest paths in a convex polygon." Proceedings of the Annual Symposium on Computational Geometry (1998): 392-401.
    • Agarwal, PK, Eppstein, D, Guibas, LJ, and Henzinger, MR. "Parametric and kinetic minimum spanning trees." Annual Symposium on Foundations of Computer Science - Proceedings (1998): 596-605.
    • Agarwal, PK, Erickson, J, and Guibas, LJ. "Kinetic binary space partitions for intersecting segments and disjoint triangles." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (1998): 107-116.
    • Agarwal, PK, Kreveld, MV, and Suri, S. "Label placement by maximum independent set in rectangles." Computational Geometry: Theory and Applications 11, no. 3-4 (1998): 209-218.
    • 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): 491-505.
    • Agarwal, PK, Sharir, M, and Welzl, E. "The discrete 2-center problem." Discrete and Computational Geometry 20, no. 3 (1998): 287-305.
    • Agarwal, PK, and O'Rourke, J. "Computational geometry column 34." International Journal of Computational Geometry and Applications 8, no. 5-6 (1998): 637-642.
    • Agarwal, PK, and Procopiuc, CM. "Exact and approximation algorithms for clustering." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (1998): 658-667.
    • Agarwal, PK, and Sharir, M. "Efficient algorithms for geometric optimization." ACM Computing Surveys 30, no. 4 (1998): 448-458.
    • Agarwal, PK. "Surface approximation and geometric partitions." SIAM Journal on Computing 27, no. 4 (1998): 1016-1035.
    • 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): 1689-1713.
    • Agarwal, PK, Aronov, B, Pach, J, Pollack, R, and Sharir, M. "Quasi-planar graphs have a linear number of edges." Combinatorica 17, no. 1 (1997): 1-9.
    • Agarwal, PK, Aronov, B, and Sharir, M. "Computing envelopes in four dimensions with applications." SIAM Journal on Computing 26, no. 6 (1997): 1714-1732.
    • Agarwal, PK, Aronov, B, and Sharir, M. "Line transversals of balls and smallest enclosing cylinders in three dimensions." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (1997): 483-492.
    • 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): 30-38.
    • 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): 39-48.
    • Agarwal, PK, Har-Peled, S, Sharir, M, and Varadarajan, KR. "Approximating shortest paths on a convex polytope in three dimensions." Journal of the ACM 44, no. 4 (1997): 567-584.
    • Agarwal, PK, Latombe, J-C, Motwani, R, and Raghavan, P. "Nonholonomic path planning for pushing a disk among obstacles." Proceedings - IEEE International Conference on Robotics and Automation 4 (1997): 3124-3129.
    • 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): 382-384.
    • Agarwal, PK, Sharir, M, and Welzl, E. "Discrete 2-center problem." Proceedings of the Annual Symposium on Computational Geometry (1997): 147-155.
    • Agarwal, PK, and Desikan, PK. "Efficient algorithm for terrain simplification." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (1997): 139-147.
    • Varadarajan, KR, and Agarwal, PK. "Linear approximation of simple objects." Information Processing Letters 62, no. 2 (1997): 89-94.
    • Varadarajan, KR, and Agarwal, PK. "Approximating shortest paths on a nonconvex polyhedron." Annual Symposium on Foundations of Computer Science - Proceedings (1997): 182-191.
    • Agarwal, PK, Grove, EF, Murali, TM, and Vitter, JS. "Binary space partitions for fat rectangles." Annual Symposium on Foundations of Computer Science - Proceedings (1996): 482-491.
    • Agarwal, PK, Schwarzkopf, O, and Sharir, M. "The overlay of lower envelopes and its applications." Discrete and Computational Geometry 15, no. 1 (1996): 1-13.
    • Agarwal, PK, and Kreveld, MV. "Connected Component and Simple Polygon Intersection Searching." Algorithmica (New York) 15, no. 6 (1996): 626-660.
    • Agarwal, PK, and Sen, S. "Selection in Monotone Matrices and Computing kth Nearest Neighbors." Journal of Algorithms 20, no. 3 (1996): 581-601.  Full Text
    • Agarwal, PK, and Sharir, M. "Efficient randomized algorithms for some geometric optimization problems." Discrete and Computational Geometry 16, no. 4 (1996): 317-337.
    • Agarwal, PK, and Sharir, M. "Ray Shooting Amidst Convex Polygons in 2D." Journal of Algorithms 21, no. 3 (1996): 508-519.  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): 100-116.
    • 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): 119-128.
    • Frey, HC, and Agarwal, P. "Probabilistic modeling and optimization of clean coal technologies: case studies of the externally-fired 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 externally-fired combined cycle." Proceedings of the American Power Conference 1 (1996): 52-57.
    • Tamassia, R, Agarwal, PK, Amato, N, Chen, DZ, Dobkin, D, Drysdale, S, Fortune, S, Goodrich, MT, Hershberger, J, O'Rourke, J, Preparata, FP, Sack, J-R, Suri, S, Tollis, I, Vitter, JS, and Whitesides, S. "Strategic directions in computational geometry." ACM Computing Surveys 28, no. 4 (1996): 591-606.
    • Agarwal, P. "Cellular segregation and engulfment simulations using the cell programming language." Journal of Theoretical Biology 176, no. 1 (1995): 79-89.  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): 187-206.
    • Agarwal, PK, and Matoušek, J. "Dynamic half-space range reporting and its applications." Algorithmica 13, no. 4 (1995): 325-345.  Full Text
    • Agarwal, P, and Sharir, M. "Planar geometric location problems." Algorithmica (New York) 11, no. 2 (1994): 185-195.
    • Agarwal, P. "Simulation of aggregation in Dictyostelium using the cell programming language." Computer Applications in the Biosciences 10, no. 6 (1994): 647-655.
    • Agarwal, PK, Alon, N, Aronov, B, and Suri, S. "Can visibility graphs Be represented compactly?." Discrete & Computational Geometry 12, no. 1 (1994): 347-365.  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): 348-358.
    • 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): 67-75.
    • 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): 76-84.
    • Agarwal, PK, Sharir, M, and Toledo, S. "Applications of Parametric Searching in Geometric Optimization." Journal of Algorithms 17, no. 3 (1994): 292-318.  Full Text
    • Agarwal, PK, and Matousek, J. "On range searching with semialgebraic sets." Discrete & Computational Geometry 11, no. 1 (1994): 393-418.  Full Text
    • Agarwal, PK, and Sharir, M. "On the number of views of polyhedral terrains." Discrete & Computational Geometry 12, no. 1 (1994): 177-182.  Full Text
    • Agarwal, PK, and Suri, S. "Surface approximation and geometric partitions." Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms (1994): 24-33.
    • Agarwal, PK. "On stabbling lines for convex polyhedra in 3D." Computational Geometry: Theory and Applications 4, no. 4 (1994): 177-189.
    • 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): 338-347.
    • Agarwal, PK, Aronov, B, Sharir, M, and Suri, S. "Selecting distances in the plane." Algorithmica 9, no. 5 (1993): 495-514.  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): 314-323.  Full Text
    • Agarwal, PK, Pellegrini, M, and Sharir, M. "Counting circular arc intersections." SIAM Journal on Computing 22, no. 4 (1993): 778-793.
    • Agarwal, PK, Vankreveld, M, and Overmars, M. "Intersection Queries in Curved Objects." Journal of Algorithms 15, no. 2 (1993): 229-266.  Full Text
    • Agarwal, PK, and Matousek, J. "Ray shooting and parametric search." SIAM Journal on Computing 22, no. 4 (1993): 794-806.
    • Agarwal, PK, and Sharir, M. "Applications of a new space-partitioning technique." Discrete & Computational Geometry 9, no. 1 (1993): 11-38.  Full Text
    • Agarwal, PK, and Sharir, M. "Ray shooting amidst convex polytopes in three dimensions." Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (1993): 260-270.
    • Agarwal, PK, and Sharir, M. "Circle Shooting in a Simple Polygon." Journal of Algorithms 14, no. 1 (1993): 69-87.  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): 189-201.
    • Agarwal, PK, and Aronov, B. "Counting facets and incidences." Discrete & Computational Geometry 7, no. 1 (1992): 359-369.  Full Text
    • Agarwal, PK, and Matousek, J. "Ray shooting and parametric search." Conference Proceedings of the Annual ACM Symposium on Theory of Computing (1992): 517-526.
    • Agarwal, PK, and Matoušek, J. "Relative neighborhood graphs in three dimensions." Computational Geometry: Theory and Applications 2, no. 1 (1992): 1-14.
    • Agarwal, PK, and Shing, M-T. "Oriented aligned rectangle packing problem." European Journal of Operational Research 62, no. 2 (1992): 210-220.
    • Kreveld, MV, Overmars, M, and Agarwal, PK. "Intersection queries in sets of disks." BIT 32, no. 2 (1992): 268-279.  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): 97-111.
    • Agarwal, PK, Edelsbrunner, H, Schwarzkopf, O, and Welzl, E. "Euclidean minimum spanning trees and bichromatic closest pairs." Discrete & Computational Geometry 6, no. 1 (1991): 407-422.  Full Text
    • Agarwal, PK, and Sharir, M. "Off-line dynamic maintenance of the width of a planar point set." Computational Geometry: Theory and Applications 1, no. 2 (1991): 65-78.
    • Agarwal, PK, Aronov, B, Sharir, M, and Suri, S. "Selecting distances in the plane." (1990): 321-331.
    • Agarwal, PK, Edelsbrunner, H, Schwarzkopf, O, and Welzl, E. "Euclidean minimum spanning trees and bichromatic closest pairs." (1990): 203-210.
    • Agarwal, PK, and Sharir, M. "Red-blue intersection detection algorithms, with applications to motion planning and collision detection." SIAM Journal on Computing 19, no. 2 (1990): 297-321.
    • Agarwal, PK. "Partitioning arrangements of lines II: Applications." Discrete & Computational Geometry 5, no. 1 (1990): 533-573.  Full Text
    • Agarwal, PK. "Partitioning arrangements of lines I: An efficient deterministic algorithm." Discrete & Computational Geometry 5, no. 1 (1990): 449-483.  Full Text
    • Agarwal, PK, Sharir, M, and Shor, P. "Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences." Journal of Combinatorial Theory, Series A 52, no. 2 (1989): 228-274.
    • 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 channel-discontinuity-constraint routing in wireless networks." Ad Hoc Networks .  Full Text
    • Shaharabani, D, Salzman, O, Agarwal, PK, and Halperin, D. "Sparsification of Motion-Planning Roadmaps by Edge Contraction."  Link to Item
• Teaching & Mentoring
• 

  Recent Courses

  • CBB 634: Geometric Algorithms 2018
  • COMPSCI 634: Geometric Algorithms 2018
  • COMPSCI 394: Research Independent Study 2017
  • COMPSCI 532: Design and Analysis of Algorithms 2016

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.