Geographic Information Systems

Geographic information systems (GIS) is an important application domain for our research. We have been collaborating with the School of Environment at Duke on many geometric problems that arise in GIS.

We have developed efficient external-memory algorithms for large-scale problems involving collections of line segments, including triangulation and red-blue segment-intersection problems (the latter problem is an abstraction of map overlaying). Since the performance is inversely proportional to the external memory block size, our algorithms could be of great practical significance.

We developed a powerful theoretical framework for designing efficient algorithms for large-scale batched dynamic problems. One example of a batched dynamic problem is the extremely important spatial database and GIS problem called spatial join (a subproblem of map overlaying).

Selected bibliography

• 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, 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, 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)

• 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, 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)

• 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)

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

• M. Wang, J. S. Vitter, L. Lim, and S. Padmanabhan. Wavelet-based cost estimation for spatial queries, July 2001.