Recent Papers

• P. K. Agarwal and P. K. Desikan. An approximation algorithm for terrain simplification. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 139-147, 1997. (PostScript)

• P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. In J. E. Goodman B. Chazelle and R. Pollack, editors, Advances in Discrete and Computational Geometry. AMS Press, Providence, RI, 1998.

• P. K. Agarwal and C. M. Procopiuc. Covering points by strips in the plane, 1998. Unpublished manuscript.

• P. K. Agarwal and C. M. Procopiuc. Exact and approximation algortihms for clustering. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 658-667, 1998. (PostScript)

• P. K. Agarwal and M. Sharir. Efficient randomized algorithms for some geometric optimization problems. Discrete Comput. Geom., 16:317-337, 1996.

• P. K. Agarwal and M. Sharir. Arrangements and their applications. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 1998. To appear. (PostScript)

• P. K. Agarwal and M. Sharir. Davenport-Schinzel sequences and their geometric applications. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 1998. To appear. (PostScript)

• P. K. Agarwal and M. Sharir. Efficient algorithms for geometric optimization. Tech. Report, Duke University, 1998. ACM Comput. Surveys, in press. (PostScript)

• P. K. Agarwal and M. Sharir. Motion planning of a ball amid segments in three dimensions. In Proc. ACM-SIAM Symp. on Discrete Algorithms, 1999. (PostScript)

• P. K. Agarwal and M. Sharir. Pipes, cigars, and kreplach: The union of minkowski sums in three dimensions. In Proc. ACM Symp. on Computational Geometry, 1999. (PostScript)

• P. K. Agarwal and S. Suri. Surface approximation and geometric partitions. SIAM Journal of Computing, 27, 1998. (PostScript)

• P. K. Agarwal, A. Efrat, and M. Sharir. Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. To appear in SIAM Journal of Computing. (PostScript)

• P. K. Agarwal, P. Raghavan, and H. Tamaki. Motion planning for a steering-constrained robot through moderate obstacles. In Proc. ACM Symp. on Theory of Computation, 1995. (PostScript)

• P. K. Agarwal, M. de Berg, D. Halperin, and M. Sharir. Efficient generation of k-directional assembly sequences. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 122-131, 1996. (PostScript)

• P. K. Agarwal, O. Schwarzkopf, and M. Sharir. The overlay of lower envelopes and its applications. Discrete Comput. Geom., 15:1-13, 1996.

• P. K. Agarwal, N. Amenta, B. Aronov, and M. Sharir. Largest placements and motion planning of a convex polygon. In Jean-Paul Laumond and Mark Overmars, editors, Algorithms for Robotic Motion and Manipulation, pages 143-154, Wellesley, MA, 1997. A. K. Peters. Proc. 1996 Workshop on the Algorithmic Foundations of Robotics. (PostScript)

• P. K. Agarwal, B. Aronov, J. O'Rourke, and C. A. Schevon. Star unfolding of a polytope with applications. SIAM Journal of Computing, 26:1689-1713, 1997.

• P. K. Agarwal, B. Aronov, J. Pach, R. Pollack, and M. Sharir. Quasi-planar graphs have a linear number of edges. Combinatorica, 17:1-9, 1997.~ (PostScript)

• P. K. Agarwal, B. Aronov, and M. Sharir. Computing envelopes in four dimensions with applications. SIAM Journal of Computing, 26:1714-1732, 1997.

• P. K. Agarwal, B. Aronov, and M. Sharir. Line traversals of balls and smallest enclosing cylinders in three dimensions. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 483-492, 1997.

• P. K. Agarwal, B. Aronov, and M. Sharir. Motion planning for a convex polygon in a polygonal environment. Technical Report CS-1997-17, Dept. Computer Science, Duke University, 1997. To appear in Discrete Comput. Geom. (PostScript)

• P. K. Agarwal, B. Aronov, and M. Sharir. On levels in arrangements of lines, segments, planes and triangles. In Proc. ACM Symp. on Computational Geometry, pages 30-38, 1997. (PostScript)

• P. K. Agarwal, E. F. Grove, T. M. Murali, and J. S. Vitter. Binary space partitions for fat rectangles. Technical Report TR-CS-97-09, Dept. Comput. Sci., Duke Univ., march 1997. A preliminary version appeared in Proc. IEEE Symp. on Foundations of Comp. Sci. 1996. (PostScript)

• P. K. Agarwal, L. J. Guibas, J. Hershberger, and E. Veach. Maintaining the extent of a moving point set. In Proc. Workshop on Algorithms and Data Structures, volume 1272 of Lecture Notes in Computer Science, pages 31-44. Springer-Verlag, 1997. (PostScript)

• P. K. Agarwal, L. J. Guibas, T. M. Murali, and J. S. Vitter. Cylindrical static and kinetic binary space partitions. In Proc. ACM Symp. on Computational Geometry, pages 39-48, 1997. (PostScript)

• P. K. Agarwal, S. Har-Peled, M. Sharir, and K. R. Varadarajan. Approximate shortest paths on a convex polytope in three dimensions. J. ACM, 44:567-584, 1997. (PostScript)

• P. K. Agarwal, J.-C. Latombe, R. Motwani, and P. Raghavan. Nonholonomic path planning for pushing a disk among obstacles. In em Intl. Conf. Robotics and Auto., 1997. (PostScript)

• P. K. Agarwal, T. M. Murali, and J. S. Vitter. Practical techniques for constructing binary space partitions for orthogonal objects. In Proc. ACM Symp. on Computational Geometry (communication), pages 382-384, 1997. (PostScript)

• P. K. Agarwal, M. Sharir, and E. Welzl. The discrete 2-center problem. In Proc. ACM Symp. on Computational Geometry, pages 147-155, 1997. (PostScript)

• P. K. Agarwal, M. van Kreveld, and S. Suri. Label placement by maximum independent set in rectangles. In Proc. 9th Canad. Conf. Comput. Geom., pages 233-238, 1997.

• P. K. Agarwal, N. Amenta, and M. Sharir. Placement of one convex polygon inside another. Discrete Comput. Geom., 19:95-104, 1998.

• P. K. Agarwal, L. Arge, J. Erickson, P. G. Franciosa, and J. S. Vitter. Efficient searching with linear constraints. In Proc. ACM Symp. Principles of Database Systems, 1998. (PostScript)

• P. K. Agarwal, L. Arge, T.M. Murali, K. Varadarajan, and J.S. Vitter. I/O-efficient algorithms for contour line extraction and planar graph blocking. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 117-126, 1998. (PostScript)

• P. K. Agarwal, B. Aronov, T. Chan, and M. Sharir. On levels in arrangements of lines, segments, planes, and triangles. Discrete Comput. Geom., 19:315-331, 1998.

• P. K. Agarwal, T. Biedl, S. Lazard, S. Robbins, S. Suri, and S. Whitesides. Curvature-constrained shortest paths in a convex polygon. In Proc. ACM Symp. on Computational Geometry, 1998. (PostScript)

• P. K. Agarwal, M. de Berg, J. Matousek, and O. Schwarzkopf. Constructing levels in arrangements and higher order Voronoi diagrams. SIAM Journal of Computing, 27:654-667, 1998. (PostScript)

• P. K. Agarwal, D. Eppstein, L. J. Guibas, and M. Henzinger. Parametric and kinetic minimum spanning trees. In Proc. IEEE Symp. on Foundations of Comp. Sci., 1998. (PostScript)

• P. K. Agarwal, J. Erickson, and L. J. Guibas. Kinetic binary space partitions for intersecting segments and disjoint triangles. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 107-116, 1998. (PostScript)

• P. K. Agarwal, L. E. Kavraki, and M. T. Mason, editors. Robotics: The Algorithmic Perspective. A. K. Peters, Wellesley, 1998.

• P. K. Agarwal, J. Matousek, and O. Schwarzkopf. Computing many faces in arrangements of lines and segments. SIAM Journal of Computing, 27(2):491-505, 1998.

• P. K. Agarwal, T. Murali, and J. Vitter. A new algorithm for constructing binary space partitions for orthogonal rectangles. In Proc. European Sympos. Algortihms, 1998. (PostScript)

• P. K. Agarwal, M. van Kreveld, and S. Suri. Label placement by maximum independent set in rectangles. 11:209-218, 1998.

• P. K. Agarwal, L. Arge, G. Brodal, and J. S. Vitter. I/O-efficient dynamic point location in monotone planar subdivisions. In Proc. ACM-SIAM Symp. on Discrete Algorithms, 1999. (PostScript)

• P. K. Agarwal, B. Aronov, S. Har-Peled, and M. Sharir. Exact and approximation algorithms for minimum width annuli and shells, 1999. (PostScript)

• P. K. Agarwal, B. Aronov, and M. Sharir. Line transversals of balls and smallest enclosing cylinders in three dimensions. Discrete and Comput. Geom., 21:373-388, 1999. (PostScript)

• P. K. Agarwal, J. Basch, M. de Berg, L. J. Guibas, and J. Hershberger. Lower bounds for kinetic planar subdivisions. In Proc. ACM Symp. on Computational Geometry, 1999. (PostScript)

• P. K. Agarwal. Range searching. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 31, pages 575-598. CRC Press LLC, 1997. (PostScript)

• C. C. Aggarwal, C. M. Procopiuc, J. L. Wolf, P. S. Yu, and J. S. Park. A framework for finding projected clusters in high dimensional spaces. submitted to Proc. of the 15th Intl. Conf. on Data Eng., 1999.

• L. Arge and P. B. Miltersen. On showing lower bounds for external-memory computational geometry. In J. Abello and J. S. Vitter, editors, External Memory Algorithms and Visualization, DIMACS series. American Mathematical Scoiety, 1998. (To appear). (PostScript)

• L. Arge and J. S. Vitter. Optimal dynamic interval management in external memory. In Proc. IEEE Symp. on Foundations of Comp. Sci., pages 560-569, 1996. (PostScript)

• L. Arge, D. E. Vengroff, and J. S. Vitter. External-memory algorithms for processing line segments in geographic information systems. In Proc. Annual European Symposium on Algorithms, LNCS 979, pages 295-310, 1995. To appear in special issue of Algorithmica. (PostScript)

• L. Arge, P. Ferragina, R. Grossi, and J. Vitter. On sorting strings in external memory. In Proc. ACM Symp. on Theory of Computation, 1997. (PostScript)

• L. Arge, K. H. Hinrichs, J. Vahrenhold, and J. S. Vitter. Efficient batched construction of R-trees. Submitted for publication, 1998.

• L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, and J. S. Vitter. Scalable sweeping-based spatial join. In Proc. IEEE International Conf. on Very Large Databases, 1998. (PostScript)

• L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, and J. S. Vitter. Theory and practice of I/O-efficient algorithms for multidimensional batched searching problems. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 685-694, 1998. (PostScript)

• L. Arge. External-memory algorithms with applications in geographic information systems. In Algorithmic Foundations of GIS, volume 1340. Springer Verlag, 1996. (PostScript)

• B. Aronov, M. van Kreveld, R. van Oostrum, and K. Varadarajan. Facility location on terrains. In Proc. 9th Annu. Intl. Symp. on Algorithms and Computation, 1998.

• R. D. Barve and J. S. Vitter. A simple and efficient parallel disk mergesort. Submitted for publication.

• R. D. Barve and J. S. Vitter. A theory of memory-adaptive algorithms. Submitted for publication.

• R. D. Barve, E. F. Grove, and J. S. Vitter. Simple randomized mergesort on parallel disks. In Proc. ACM Symp. on Parallel Algorithms and Architectures, pages 109-118, 1996. To appear in special issue on parallel I/O in ``Parallel Computing''. (PostScript)

• R. Barve, E. F. Grove, and J. S. Vitter. Practical parallel external mergesort using limited randomization. In Proc. DIMACS Workshop on Randomization Methods in Algorithm Design, DIMACS series. American Mathematical Scoiety, 1997.

• R. Barve, M. Kallahalla, P. Varman, and J. S. Vitter. Competitive analysis of buffer management algorithms for parallel I/O systems. In Proc. ACM-IEEE Workshop on I/O in Parallel And Distributed Systems, 1997.

• R. Barve, M. Kallahalla, P. J. Varman, and J. Scott Vitter. Competitive parallel disk prefetching and buffer management. In Proceedings of the Fifth Workshop on Input/Output in Parallel and Distributed Systems, pages 47-56, San Jose, CA, November 1997. ACM Press.

• R. D. Barve, E. F. Grove, and J. S. Vitter. Simple randomized mergesort on parallel disks. Parallel Computing, 23(4):601-631, 1997.

• R. Barve, E. A. M. Shriver, P. B. Gibbons, B. K. Hillyer, and Y. Matias. Modeling and imizing I/O throughput of multiple disks on a bus. In Proc. Joint International Conference on Measurement and Modeling of Computer Systems, 1998.

• R. Barve, E. F. Grove, and J. S. Vitter. A competitive application-controlled paging algorithm for a shared cache. SIAM Journal of Computing, to appear.

• J. Basch, J. Erickson, L. J. Guibas, J. Hershberger, and L. Zhang. Kinetic collision detection between two simple polygons. In Proc. ACM-SIAM Symp. on Discrete Algorithms, 1999.

• J. Cohen, A. Varshney, D. Manocha, G. Turk, H. Weber, P. K. Agarwal, F. P. Brooks, Jr., and W. Wright. Simplification envelopes. In Proc. SIGGRAPH'96, pages 118-128, 1996.

• J. Erickson and D. Eppstein. Raising roofs, crashing cycles, and playing pool: Applications of a data structure for maintaining closest pairs. In Proc. ACM Symp. on Computational Geometry, 1998. (PostScript)

• J. Erickson, L. J. Guibas, J. Stolfi, and L. Zhang. Separation-sensitive collision detection for convex objects. In Proc. ACM-SIAM Symp. on Discrete Algorithms, 1999.

• J. Erickson. Space-time tradeoffs for emptiness queries. In Proc. ACM Symp. on Computational Geometry, pages 304-313, 1997. (PostScript)

• G. Gibson, J. S. Vitter, and J. Wilkes (Editors). Strategic directions in storage I/O for large-scale computing. ACM Computing Surveys, 28(4):779-793, 1996. (PostScript)

• E. F. Grove, T. M. Murali, and J. S. Vitter. The object complexity model for hidden-surface elimination. International Journal of Computational Geometry & Applications, to appear. (PostScript)

• D. T. Hoang and J. S. Vitter. Multiplexing vbr video sequences onto a cbr channel with lexicographic imization. In Proc. IEEE International Conference on Image Processing, 1997.

• D. T. Hoang, P. M. Long, and J. S. Vitter. Dictionary by partial matching. Submitted for publication.

• D. T. Hoang, E. Linzer, and J. S. Vitter. Lexicographic bit allocation for mpeg video. Journal of Visual Communication and Image Representation (Special issue on high-fidelity media processing), 8(4):384-404, 1997.

• D. T. Hoang, P. M. Long, and J. S. Vitter. Rate-distortion imizations for motion estimation in low-bitrate video coding. IEEE Transactions on Circuits and Systems for Video Technology, 8(4):488-500, 1998.

• S. B. Kang and P. K. Desikan. Virtual navigation of complex scenes using clusters of cylindrical panoramic images. In Proc. Graphics Interface, 1998.

• P. Krishnan, J. S. Vitter, and B. R. Iyer. Estimating alphanumeric selectivity in the presence of wildcard. In Proc. ACM-SIGMOD Intl. Conf. on Management of Data, pages 282-293, 1996.

• P. M. Long, A. I. Natsev, and J. S. Vitter. Text compression via alphabet re-representation. In Proc. IEEE Data Compression Conference, 1997.

• Y. Matias, J. S. Vitter, and W.-C. Ni. Dynamic generation of discrete random variates. Submitted for publication.

• Y. Matias, J. S. Vitter, and M. Wang. Wavelet-based histograms for selectivity estimation. In Proc. ACM-SIGMOD Intl. Conf. on Management of Data, 1998. (PostScript)

• T. M. Murali and T. A. Funkhouser. Consistent solid and boundary representations from arbitrary polygonal data. In Proceedings of the 1997 Symposium on Interactive 3D Graphics, pages 155-162, 1997. (PostScript)

• M. H. Nodine and J. S. Vitter. imal deterministic sorting on parallel disks. Submitted for publication.

• M. H. Nodine and J. S. Vitter. imal deterministic sorting on parallel processors and parallel memory hierarchies. Submitted for publication.

• R. Tamassia, I. G. Tollis, and J. S. Vitter. A parallel algorithm for planar orthogonal grid drawings. Submitted for publication.

• K. Varadarajan and P. K. Agarwal. Approximating shortest paths on a nonconvex polyhedron. In Proc. IEEE Symp. on Foundations of Comp. Sci., 1997. (PostScript)

• K. R. Varadarajan and P. K. Agarwal. Linear approximation of simple objects. Information Processing Letters, 62:89-94, 1997.

• K. R. Varadarajan and P. K. Agarwal. Approximating polygonal curves. Technical Report CS-1998-15, Dept. Computer Science, Duke University, 1998. Submitted to Discrete Comput. Geom.

• K. R. Varadarajan and P. K. Agarwal. Approximation algorithms for bipartite and non-bipartite matching in the plane. In Proc. ACM-SIAM Symp. on Discrete Algorithms, 1999.

• K. R. Varadarajan. Approximating monotone polygonal curves using the uniform metric. In Proc. ACM Symp. on Computational Geometry, pages 311-318, 1996.

• K. R. Varadarajan. A divide-and-conquer algorithm for min-cost perfect matching in the plane. In Proc. IEEE Symp. on Foundations of Comp. Sci., 1998.

• D. E. Vengroff and J. S. Vitter. I/O-efficient scientific computation using tpie. In Proceedings of the Goddard Conference on Mass Storage Systems and Technologies, published in NASA Conference Publication 3340, Volume II, pages 553-570, 1996. (PostScript)

• D. E. Vengroff and J. S. Vitter. Three-dimensional range searching in external memory. In Proc. ACM Symp. on Theory of Computation, 1996. (PostScript)

• J. S. Vitter, M. Wang, and B. Iyer. Data cube approximation and histograms via wavelets. In Proc. International Conference on Information and Knowledge Management, 1998.

• J. S. Vitter. Communication issues in large-scale geometric computation. ACM Computing Surveys, 28(4es), 1996. article 20.

• J. S. Vitter. External memory algorithms. In Proc. ACM Symp. Principles of Database Systems, pages 119-128, 1998. Invited tutorial.

• J. S. Vitter. External memory algorithms (invited paper). In Proc. Annual European Symposium on Algorithms, 1998.

• H. Wang and P. K. Agarwal. Approximation algorithms for curvature-constrained shortest paths. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 409-418, 1996. (PostScript)

• M. Wang, J. S. Vitter, and B. Iyer. Selectivity estimation in the presence of alphanumeric correlations. In Proc. 13th Annual IEEE Conference on Data Engineering (ICDE '97), pages 169-180, 1997.

• M. Wang, B. Iyer, and J. S. Vitter. Scalable mining for classification rules in relational databases. In Proc. International Database Engineering & Application Symposium, pages 58-67, 1998.