Matthew Dickerson:
Research Page


Computational Geometry

Computer Science Education


Welcome to my research home page.

I am Associate Professor of Computer Science (officially an associate professor of Mathematics and Computer Science, but I teach entirely Computer Science) at Middlebury College.

My interests are in Computational Geometry, Algorithms, Graph Drawing, and Computer Science Education.

 

(NEW!) If you are interested in the Voronoi diagram or in some new 2-site Distance Functions, please visit my new 2-Site Distance Function Voronoi Diagram applet.

Visit also my:

EDUCATION:

 

INTRODUCTION:

For the past several years, my research has been in the area of computation geometry. I have been interested in proximity problems and the Voronoi diagram (including non-Euclidean notions of distance and proximity other than Euclidean), triangualations (especially the minimum weight triangulation and related triangulations) and in optimal polygon placement problems.

 

Prior to coming to Middlebury College, I was a graduate student at Cornell University (1985-1989). My graduate research was in the area of computational algebra under the brilliant advising of Prof. Dexter Kozen. My dissertation was on algorithms for polynomial decomposition. However I have done little additional work in this field since leaving Cornell.

 Look below for:

 A Complete List of Publications

 Selected Publications with Undergraduates

 Selected Publications with Available Abstracts or Postscript

Overview:

As mentioned, my main area of interest is the design and analysis of algorithms: specifically, algorithms for computational geometry. I have done recent work on enumerating interpoint distances in the plane or in higher dimensions, the greedy triangulation, optimal polygon placement with translation only, optimal polygon placement with translation and rotation, heuristics for approximating the minimum weight triangulation, triangulating a 3-dimensional polygon, and a new, extensive, practically computable skeleton of the minimum weight triangulation of a general point set.

Research with Undergraduates:

I have published several papers co-authored with Middlebury College undergraduates who have worked with me on original research problems in computational geometry.

 Publications in Computer Science

 I. Journal Articles (Computational Geometry & Algebra)

  1. M.Dickerson and D. Scharstein, "Optimal Placement of Convex Polygons to Maximize Point Containmen." Discrete and Computational Geometry 11 (1998) 1--16.
  2. G.Barequet, M.Dickerson, and D.Eppstein, "On Triangulating Three-Dimensional Polygons." Discrete and Computational Geometry 10 (1998) 155--170.
  3. M.Dickerson, M.Keil and M.Montague) "A Large Subgraph of the Minimum Weight Triangulation." Discrete and Computational Geometry 18 (1997) 289--304.
  4. G.Barequet,M.Dickerson, and P.Pau "Translating a Convex Polygon to Contain a Maximum Number of Points." Computational Geometry: Theory and Applications, 8:4 (1997) 167--179.
  5. M.Dickerson R.L.Drysdale, S.McElfresh, and E. Welzl, "Fast Greedy Triangulation Algorithms." Computational Geometry: Theory and Applications, 8 (1997) 67--86.
  6. M.Dickerson, and D. Eppstein, "Algorithms for Proximity Problems in Higher Dimensions." Computational Geometry: Theory and Applications, 5 (1996) 277--291.
  7. M.Dickerson, "General Polynomial Decomposition and the s-1-decomposition are NP-hard." International Journal of Foundations of Computer Science, 4:2 (1993) 147-156.
  8. M.Dickerson J. Shugart, "A Simple Algorithm for Enumerating Longest Distances in the Plane." Information Processing Letters, 45 (1993) 269274.
  9. M.Dickerson, "The Inverse of an Automorphism in Polynomial Time." Journal of Symbolic Computation, 13 (1992) 209-220.
  10. M.Dickerson, R.L.Drysdale & J-R. Sack, "Simple Algorithms for Enumerating Interpoint Distances and Finding k Nearest Neighbors." International Journal of Computational Geometry and Applications, 2:3 (1992) 221-239.
  11. M.Dickerson and R.L.Drysdale, "Fixed Radius Near Neighbors Search Problem for Points and Segments." Information Processing Letters, 35 (1990) 269273.

II. Conference Proceedings (Computational Geometry & Algebra)

  1. G.Barequet, M.Dickerson and M.Goodrich, "Voronoi Diagrams for Polygon-Offset Distance Functions." LNCS 1272 (WADS:Workshop on Algorithms and Data Structures), Springer (1997) 200--209.
  2. G.Barequet, A. Briggs, M.Dickerson, and M.Goodrich, "Offset-Polygon Annulus Placement Problems." LNCS 1272 (WADS:Workshop on Algorithms and Data Structures) Springer, (1997) 378--391.
  3. M.Dickerson, and M. Montague, "A (Usually?) Connected Subgraph of the Minimum Weight Triangulation." Proceedings of the 12th Annual Symposium on Computational Geometry (1996) 204--213.
  4. G. Barequet, M.Dickerson,and D. Eppstein, "On Triangulating Three-Dimensional Polygons" Proceedings of the 12th Annual Symposium on Computational Geometry (1996) 38--47.
  5. M.Dickerson and D. Scharstein, "Optimal Placement of Convex Polygons to Maximize Point Containment." Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithm, (1996) 114--121.
  6. Gill Barequet, M.Dickerson, and Petru Pau, "Translating a convex polygon to contain a maximum number of points." Proceedings of the 7th Canadian Conference on Computational Geometry, (1995) 61--66.
  7. M.Dickerson, S.McElfresh and M. Montague, "New Algorithms and Empirical Findings on Minimum Weight Triangulation Heuristics." Proceedings of the 11th Annual Symposium on Computational Geometry (1995) 238-247.
  8. M.Dickerson, R.L.Drysdale, S.McElfresh, and E. Welzl, "Fast Greedy Triangulation Algorithms." Proceedings of the 10th Annual Symposium on Computational Geometry (1994) 211-220.
  9. M.Dickerson "Rank of the Longest Edge in the Greedy Triangulation." Proceedings of the Fourth Canadian Conference on Computational Geometry, St. John's Newfoundland, (1992) 182-187.
  10. M.Dickerson and J. Shugart, "Enumerating k Longest Distances for n Points in the Plane." Proceedings of the Fourth Canadian Conference on Computational Geometry, St. John's Newfoundland, (1992) 137-142.
  11. M.Dickerson and R.L.Drysdale, "Enumerating k Distances in the Plane." Proceedings of the 7th Annual Symposium on Computational Geometry, (1991) 234-238.
  12. M.Dickerson, "The Inverse of an Automorphism in Polynomial Time." Proceedings of the IEEE 30th Annual Symposium on Foundations of Computer Science [FOCS], (1989) 82-87.

III. Books (Computational Geometry)

  1. Matthew Dickerson and Scot Drysdale, Voronoi Diagrams and Proximity Problems COMAP, Lexington Massachusetts, 1996. ISSN 1071-6874.
  2. Matthew Dickerson and Jack Snoeyink, Convex Hulls and Algorithms COMAP, Lexington Massachusetts, to appear.

 IV. Videos (Computational Geometry)

  1. G. Barequet, A.Briggs, M.Dickerson, C.Dima, and M.Goodrich, "Animating the offset-polygon distance function" The 6th Annual Video Review of Computational Geometry (1997) with abstract appearing in the Proceedings of the 13th Annual Symposium on Computational Geometry: Videos (1997) 479--480.
  2. M.Dickerson and D. Scharstein "The rotation diagram and optimal containing placements of a convex polygon" The 5th Annual Video Review of Computational Geometry (1996) with abstract appearing in the Proceedings of the 12th Annual Symposium on Computational Geometry: Videos (1996) V9--V10.

 V. Articles on Computer Science Education

  1. A.Briggs, and M. Dickerson, "Making a Non-Majors Course Fun (without sacrificing conent)" Journal of Computing in Small Colleges (JSCS) 14:4 1999) 154--162.
  2. M. Dickerson and R.L.Scot Drysdale "Recent Research in Computational Geometry and the Undergraduate Algorithms Course" Journal of Computing in Small Colleges (JSCS)13:5 (1998) 173--186.
  3. C. Dima, G. Parent, A.Briggs, and M. Dickerson, "Polygon Placement Problems: an undergraduate research project in computational geometry." Journal of Computing in Small Colleges (JSCS) 13:5 (1998) 13--24.
  4. M. Dickerson, "Music, MIDI, and the Computer Science Survey Course" Journal of Computing in Small Colleges (JSCS) 12:5 (1997) 57--70.
 









If you've seen enough here, feel free to return now to the regular,
general, not-research-specific, Matt
Dickerson home page .