Some of these papers are in postscript format. To read postscript from Window's machines, download the free software GSview (along with Alladin Ghostscript).

Nearest Neighbor and Range Searching

G. D. da Fonseca and D. M. Mount, Approximate range searching: The absolute model, Comput. Geom. Theory Appl., 2009. (In press. doi: 10.1016/j.comgeo.2008.09.009). S. Arya, T. Malamatos, and D. M. Mount, The Effect of Corners on the Complexity of Approximate Range Searching, Discrete and Computational Geometry, 41 (2009), 398-443. (doi: 10.1007/s00454-009-9140-z). S. Arya, G. D. da Fonseca, D. M. Mount, Tradeoffs in Approximate Range Searching Made Simpler, Proc. 2008 XXI Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI'08), 2008, 237-244. (doi: 10.1109/SIBGRAPI.2008.24). S. Arya, D. M. Mount, A. Vigneron, and J. Xia, Space-Time Tradeoffs for Proximity Searching in Doubling Spaces, Proc. 16th Annu. European Sympos. Algorithms (ESA'08), 2008, 112-123. (doi: 10.1007/978-3-540-87744-8_10). S. Arya, T. Malamatos, and D. M. Mount, On the Importance of Idempotence, Proc. 38th ACM Symp. on Theory of Computing (STOC'06), 2006, 564-573. S. Arya, T. Malamatos, and D. M. Mount, Space-Time Tradeoffs for Approximate Spherical Range Counting, 16th Ann. ACM-SIAM Symposium on Discrete Algorithms, (SODA'05), 2005, 535-544. (Full version: Univ. of Maryland, Dept. of Computer Science Technical Report CS-TR-4842, Nov 2006.) S. Arya, T. Malamatos, and D. M. Mount, Space-Efficient Approximate Voronoi Diagrams, Proc. 34th ACM Symp. on Theory of Computing (STOC'02), 2002, 721-730. S. Maneewongvatana and D. M. Mount, Analysis of Approximate Nearest Neighbor Searching with Clustered Point Sets, Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges, eds. M. H. Goldwasser, D. S. Johnson, C. C. McGeoch, in the DIMACS Series in Discr. Math. and Theoret. Comp. Sci., Vol. 59, AMS, 2002, 105-123. S. Maneewongvatana and D. M. Mount, The Analysis of a Probabilistic Approach to Nearest Neighbor Searching, Proc. 7th Workshop on Algorithms and Data Structures (WADS'01), 2001, 276-286. S. Maneewongvatana and D. M. Mount, On the Efficiency of Nearest Neighbor Searching with Data Clustered in Lower Dimensions, International Conference on Computational Science (ICCS'01), Springer Lecture Notes LNCS 2073, 2001, 842-851. (Full version: Univ. of Maryland, Dept. of Computer Science Technical Report CS-TR-4209, 2001.) S. Maneewongvatana and D. M. Mount, An Empirical Study of a New Approach to Nearest Neighbor Searching, 3rd International Workshop on Algorithm Engineering and Experiments (ALENEX'01), 2001, Springer Lecture Notes LNCS 2153, 2001, 172-187. S. Arya and D. M. Mount, Approximate Range Searching, Computational Geometry: Theory and Applications, 17 (2000), 135-163. D. M. Mount, N. Netanyahu, R. Silverman, A. Y. Wu, Chromatic nearest neighbor searching: A query sensitive approach,, Computational Geometry: Theory and Applications, 17 (2000), 97-119. S. Maneewongvatana and D. M. Mount, It's Okay to be Skinny, If Your Friends are Fat, 4th Annual CGC Workshop on Comptutational Geometry, 1999. S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu, An Optimal Algorithm for Approximate Nearest Neighbor Searching, Journal of the ACM, 45 (1998), 891-923. S. Arya, D. M. Mount, and O. Narayan, Accounting for Boundary Effects in Nearest Neighbor Searching, Discrete and Computational Geometry, 16 (1996), 155-176. S. Arya and D. M. Mount, Algorithms for Fast Vector Quantization, Proc. of the Data Compression Conference (DCC'93), eds. J. A. Storer and M. Cohn, IEEE Press, 1993, 381-390. (Revised). S. Arya and D. M. Mount, Approximate Nearest Neighbor Searching, Proc. 4th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA'93), 1993, 271-280.

Geometric Data Structures and Point Location

S. Arya, T. Malamatos, D. M. Mount, and K.-C. Wong Optimal Expected-Case Planar Point Location, SIAM J. Comput. 37, 2007, 584-610 (doi: 10.1137/S0097539704446724). Note: This paper combines and improves the results of the following two papers. S. Arya, T. Malamatos, and D. M. Mount, Entropy-Preserving Cuttings and Space-Efficient Planar Point Location, Proc. 12th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA'01), 2001, 256-261. S. Arya, T. Malamatos, and D. M. Mount, Nearly Optimal Expected-Case Planar Point Location, Proc. 41st Annual Symp. on Foundations of Computer Science (FOCS'00), 2000, 208-218. S. Arya, T. Malamatos, and D. M. Mount, A Simple Entropy-Based Algorithm for Planar Point Location, ACM Trans. Algorithms, 3 (2007) (doi: 10.1145/1240233.1240240). F. B. Atalay and D. M. Mount, The Cost of Compatible Refinement of Simplex Decomposition Trees, Proc. International Meshing Roundtable (IMR'06), 2006, 57-69. F. B. Atalay and D. M. Mount, Pointerless Implementation of Hierarchical Simplicial Meshes and Efficient Neighbor Finding in Arbitrary Dimensions, Internat. J. Comput. Geom. Appl., 17 (2007), 595-631. (doi: 10.1142/S0218195907002495). F. B. Atalay and D. M. Mount, Interpolation over Light Fields with Applications in Computer Graphics, Proc. of the 5th Workshop on Algorithm Engineering and Experiments (ALENEX'03), R. Ladner, Editor, SIAM, 2003, 56-68. (See also Project Web Page.) D. M. Mount and F. T. Pu, Binary Space Parititions in Pluecker Space, Algorithm Engineering and Experimentation, (ALENEX'99), Springer Lecture Notes LNCS 1619, Springer, 1999, 94-113. (printer-friendly version). J. S. B. Mitchell, D. M. Mount, and S. Suri, Query-Sensitive Ray Shooting, Internat. J. Comput. Geom. Appl., 7 (1997), 317-347.

Computational Statistics and Pattern Matching

M. Cho and D. M. Mount, Embedding and Similarity Search for Point Sets under Translation, Proc. 24th ACM Symp. on Computational Geometry (SoCG'08), 2008, 320-327. (doi: 10.1145/1377676.1377731). D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, and A. Y. Wu On the Least Trimmed Squares Estimator, (Manuscript submitted for publication, 2007.) N. Memarsadeghi and D. M. Mount, Efficient Implementation of an Optimal Interpolator for Large Spatial Data Sets, Computational Science - ICCS 2007; International Conference on Computational Science, Part II, Springer Lecture Notes LNCS 4488, 503-510, 2007. (doi: 10.1007/978-3-540-72586-2_74). D. M. Mount, N. S. Netanyahu, K. Romanik, R. Silverman, and A. Y. Wu A Practical Approximation Algorithm for the LMS Line Estimator, Computational Statistics & Data Analysis, 51 (2007), 2461-2486. J. Erickson, S. Har-Peled, and D. M. Mount, On the Least Median Square Problem, Discrete and Computational Geometry, 36 (2006), 593-607. M. Cho and D. M. Mount, Improved Approximation Bounds for Planar Point Pattern Matching, Proc. Workshop on Algorithms and Data Structures (WADS'05), 2005, 432-443. D. M. Mount, N. Netanyahu, and E. Zuck, Analyzing the Number of Samples for an Approximate Monte-Carlo LMS Line Estimator, in Theory and Applications of Recent Robust Methods, eds. M. Hubert, G. Pison, A. Struyf, and S. Van Aelst, Series: Statistics for Industry and Technology, Birkhauser, Basel, 207-219, 2004. D. M. Mount, and N. Netanyahu, Efficient Randomized Algorithms for Robust Estimation of Circular Arcs and Aligned Ellipses, Computational Geometry: Theory and Applications, 19 (2001), 1-34. D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, and A. Y. Wu, Quantile Approximation for Robust Statistical Estimation and k-Enclosing Problems, Int'l. J. of Computational Geometry and Applications, 10 (2000), 593-608. D. M. Mount, N. S. Netanyahu, and J. LeMoigne, Efficient algorithms for robust feature matching, Pattern Recognition, 32 (1999) 17-38. J. Matoushek, D. M. Mount, and N. Netanyahu, Efficient Randomized Algorithms for the Repeated Median Line Estimator, Algorithmica, 20 (1998), 136-150.

Clustering

N. Memarsadeghi, D. M. Mount, N. S. Netanyahu, and J. Le Moigne, A Fast Implementation of the ISODATA Clustering Algorithm, Internat. J. Comput. Geom. Appl., 17 (2007) 71-103 (doi: 10.1142/S0218195907002252). T. Kanungo, D. M. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Y. Wu, A Local Search Approximation Algorithm for k-Means Clustering, Computational Geometry: Theory and Applications, 28 (2004), 89-112. T. Kanungo, D. M. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Y. Wu, An Efficient k-Means Clustering Algorithm: Analysis and Implementation, IEEE Trans. PAMI, 24 (2002), 881-892. M. Charikar, S. Khuller, D. M. Mount, and G. Narasimhan, Algorithms for Facility Location Problems with Outliers, 12th Ann. ACM-SIAM Symposium on Discrete Algorithms, 2001, 642-651. T. Kanungo, D. M. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Y. Wu, Computing Nearest Neighbors for Moving Points and Applications to Clustering, 10th Ann. ACM-SIAM Symposium on Discrete Algorithms, 1999, S931-S932.

Euclidean Spanners

S. Arya, D. M. Mount, and M. Smid, Dynamic Algorithms for Geometric Spanners of Small Diameter: Randomized Algorithms, Computational Geometry: Theory and Applications, 13 (1999), 91-107. S. Arya, G. Das, D. M. Mount, J. S. Salowe, and M. Smid, Euclidean Spanners: Short, Thin, and Lanky, Proc. 27th ACM Symp. on Theory of Computing (STOC'95), 1995, 489-498. S. Arya, D. M. Mount, and M. Smid, Randomized and Deterministic Algorithms for Geometric Spanners of Small Diameter, Proc. 35th Annual Symp. on Foundations of Computer Science, (FOCS'94), 1994, 703-712.

Other Topics

D. M. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Y. Wu, A Computational Framework for Incremental Motion, Proc. 20th Ann. ACM Symp. on Computational Geometry (SoCG'04), 2004, 200-209. F. B. Atalay and D. M. Mount, Ray Interpolants for Fast Ray-Tracing Relections and Refractions, Journal of WSCG (Proc. Intl. Conf. in Central Europe on Computer Graphics, Visualization, and Computer Vision), 10(3), 2002, 1-8. T. Kanungo, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu, Approximating Large Convolutions in Digital Images, IEEE Transactions on Image Processing 10, 2001, 1826-1835. S. Arya, S.-W. Cheng, and D. M. Mount, Approximation Algorithms for Multiple-Tool Milling, Int'l. J. of Computational Geometry and Applications, 11 (2001), 339-372. M. Murphy, D. M. Mount, C. W. Gable, A Point-Placement Strategy for Conforming Delaunay tetrahedralization, Int'l. J. of Computational Geometry and Applications, 11 (2001), 669-682. D. M. Mount and F.-T. Pu, Stabbing Orthogonal Objects in 3-Space, Proc. 1st CGC Workshop in Computational Geometry, 1996. D. M. Mount, R. Silverman, and A. Y. Wu, On the Area of Overlap of Translated Polygons, Computer Vision and Image Understanding, 64 (1996), 53-61. E. M. Arkin, D. M. Mount, M. T. Goodrich, J. S. B. Mitchell, C. D. Piatko, and S. S. Skiena, Point Probe Decision Trees for Geometric Concept Classes, Proc. 3rd Workshop on Algorithms and Data Structures (WADS'93), 1993, 95-106. J. S. B. Mitchell, D. M. Mount, C. H. Papadimitriou, The Discrete Geodesic Problem, (3.0Meg) SIAM J. Comput., 16, 1987, 647-668.

Surveys

D. M. Mount, Geometric Intersection, in The Handbook of Discrete and Computational Geometry, 2nd Edition, eds. J. E. Goodman and J. O'Rourke, Chapman & Hall/CRC, Boca Raton, 2004, 857-876. S. Arya and D. M. Mount, Computational Geometry: Proximity and Location, in The Handbook of Data Structures and Applications, eds. D. Mehta and S. Sahni, Chapman & Hall/CRC, Boca Raton, 2005, 63.1-63.22.

Books

M. T. Goodrich, R. Tamassia, and D. M. Mount, Data Structures and Algorithms in C++ John Wiley & Sons, New York, 2004.

Scanned Papers

The following older papers are not available electronically. Some were scanned from second generation copies, and hence are of rather marginal quality. (My thanks to Jür van den Berg and Arno Kamphuis for scanning some of them for me.)

D. M. Mount, On Finding Shortest Paths on Convex Polyhedra, (1.4Meg) Technical Report, No. 1495, Department of Computer Science, University of Maryland, 1985. D. M. Mount, Voronoi Diagrams on the Surface of a Polyhedron, (1Meg) Technical Report, No. 1496, Department of Computer Science, University of Maryland, 1985. D. M. Mount, The Densest Double-Lattice Packing of a Convex Polygon, (3.0Meg) In J. Goodman, R. Pollack, and W. Steiger, editors, Discrete and Computational Geometry: Papers from the DIMACS Special Year, Vol 6 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 245-262, Amer. Math. Soc., 1991. T. C. Kao and D. M. Mount, Incremental Construction and Dynamic Maintenance of Constrained Delaunay Triangulations", (0.7Meg), In Proc. Fourth Canad. Conf. Comput. Geom., 1992, pp. 170-175.

Back to Dave Mount's Home Page.

Last updated Jul 3, 2009.