Selected Publications - Michael T. Goodrich

Information Security Algorithms

  1. M.T. Goodrich and R. Tamassia, An Efficient Dynamic and Distributed Cryptographic Accumulator, provision patent filing, November 2000.
  2. M.T. Goodrich and R. Tamassia, Efficient Authenticated Dictionaries with Skip Lists and Commutative Hashing, provisional patent filing, November 2000.
  3. M.T. Goodrich, R. Tamassia, and A. Schwerin, Implementation of an Authenticated Dictionary with Skip Lists and Commutative Hashing, DISCEX II, 2001.
  4. M.T. Goodrich, Efficient and Secure Network Routing Algorithms, provisional patent filing, January 2001.
  5. G. Ateniese, B. de Medeiros, and M.T. Goodrich, TRICERT: A Distributed Certified E-mail Scheme, Network and Distributed Systems Security Symposium, February 2001.

Internet Algorithmics and Bulk-Synchronous Computing

  1. M.T. Goodrich, Communication-Efficient Parallel Sorting, SIAM Journal on Computing, 29(2), 1999, 416--432. Preliminary version appeared in 28th ACM Symp. on Theory of Computing (STOC), 1996.
  2. M.T. Goodrich, Randomized Fully-Scalable BSP Techniques for Multi-Searching and Convex Hull Construction,8th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1997.
  3. T.H. Cormen and M.T. Goodrich, A Bridging Model for Parallel Computation, Communication, and I/O,ACM Computing Surveys, 28A(4), December 1996.
  4. G. Barequet, S.S. Bridgeman, C.A. Duncan, M.T. Goodrich, and R. Tamassia, GeomNet: Geometric Computing Over the Internet, IEEE Internet Computing, March/April 1999, 2-10.
  5. A. Bagchi, A. Chaudhary, R. Carg, M.T. Goodrich, and V. Kumar, Seller-Focused Algorithms for Online Auctioning.

Algorithm Engineering and Education

  1. Michael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in JAVA, Wiley, 1998.
  2. M. T. Goodrich, M. Handy, B. Hudson, and R. Tamassia, Abstracting Positional Information in Data Structures: Locators and Positions in JDSL. Poster (Postscript[4.5M]) and technical note presented at OOPSLA '98.

    3. This is a large document meant to be printed on a very large page (8'x3'). Your PDF interpreter may have trouble handling it. It is also available as a tarred gzipped file (TGZ) containing a FrameMaker document and embedded image files.
  3. M. T. Goodrich and J. K. Kloss, Tiered Vector: an Efficient Dynamic Array for JDSL. Poster and technical note presented at OOPSLA '98.
  4. N.  Gelfand, M. T. Goodrich and Roberto Tamassia, Teaching Data Structure Design Patterns, presented at ACM SIGCSE '98.
  5. M.T. Goodrich and R. Tamassia, Teaching the Analysis of Algorithms with Visual Proofs, presented at ACM SIGCSE '98.
  6. M. T. Goodrich, M. Handy, B. Hudson, and R. Tamassia, Accessing the Internal Organization of Data Structures in the JDSL library, presented at ALENEX '99.
  7. R. Baker, M. Boilen, M. T. Goodrich, R. Tamassia, and B. A. Stibel, Testers and Visualizers for Teaching Data Structures, presented at ACM SIGCSE '99.
  8. M.T. Goodrich and R. Tamassia, Using Randomization in the Teaching of Data Structures and Algorithms, presented at ACM SIGCSE '99.
  9. M.T. Goodrich and R. Tamassia, Teaching Internet Algorithmics, ACM SIGCSE '01.

Graph Visualization

  1. M.T. Goodrich. Planar Separators and Parallel Polygon Triangulation. Journal of Computer & System Sciences, 51(3), 1995, 374-389.
  2. A. Garg, M.T. Goodrich, and R. Tamassia. Planar Upward Tree Drawings with Optimal Area. International Journal of Computational Geometry and Applications, 6(3), 1996, 333-356.
  3. M. Chrobak, M.T. Goodrich, and R. Tamassia, Convex Drawings of Graphs in Two and Three Dimensions, Preliminary version appeared in 12th ACM Symp. on Computational Geometry (SCG), 1996.
  4. T. Chan, M.T. Goodrich, S.R. Kosaraju, and R. Tamassia, Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings,Graph Drawing '96, 1996.
  5. C.A. Duncan, M.T. Goodrich, and S. Kobourov, Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (compressed), Proceedings of the Sixth Symposium on Graph Drawing, 1998.
  6. C.C. Cheng, C.A. Duncan, M.T. Goodrich, and S.G. Kobourov, Drawing Planar Graphs with Circular Arcs, Discrete and Computational Geometry, accepted for publication. (Preliminary version appeared in Graph Drawing '99.)
  7. C.A. Duncan, M.T. Goodrich, and S.G. Kobourov, Planarity-Preserving Clustering and Embedding for Large Planar Graphs, Proc. Graph Drawing (GD), Lecture Notes Comput. Sci., Springer-Verlag, Vol. 1731, 1999, 186--196.
  8. P. Gajer, M.T. Goodrich, and S.G. Kobourov, A Fast Multi- Dimensional Algorithm for Drawing Large Graphs, Graph Drawing 2000, 211--221.

Data Structures

  1. M.T. Goodrich and R. Tamassia. Dynamic Ray Shooting and Shortest Paths via Balanced Geodesic Triangulations. J. Algorithms, 23, 1997, 51-73.
  2. M.T. Goodrich, M. Orletsky, and K. Ramaiyer, Methods for Achieving Fast Query Times in Point Location Data Structures,8th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1997.
  3. M.T. Goodrich and R. Tamassia. Dynamic Trees and Dynamic Point Location.  SIAM J. Comput., 28(2), 1999, 612-636.
  4. C.A Duncan, M.T. Goodrich, and S. Kobourov, Balanced Aspect Ratio Trees: Combining the Advantages of k-d Trees and Octrees (compressed), 10th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1999.
  5. M.T. Goodrich and J.G. Kloss II, "Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences," 1999 Workshop on Algorithms and Data Structures (WADS), 1999, 205--216.

Geometric Algorithms

  1. M.T. Goodrich. A Polygonal Approach to Hidden-Line and Hidden-Surface Elimination. Computer Vision, Graphics, and Image Processing: Graphical Models and Image Processing, 54(1), 1992, 1--12.
  2. M.T. Goodrich, M.J. Atallah, and M. Overmars. Output-Sensitive Methods for Rectilinear Hidden Surface Removal. Information and Computation, 107(1), 1993, 1--24.
  3. L.P. Chew, M.T. Goodrich, D.P. Huttenlocher, K. Kedem, J.M. Kleinberg, and D. Kravets. Geometric Pattern Matching under Euclidean Motion. Preliminary version appeared in Proc. 5th Canadian Conference on Computational Geometry (CCCG), 1993, 151-156.
  4. H. Bronnimann and M.T. Goodrich. Almost Optimal Set Covers in Finite VC-Dimension. Preliminary version appeared in Proc. 10th ACM Symp. on Computational Geometry (SCG), 1994, 293-302.
  5. M.T. Goodrich. Efficient Piecewise-Linear Function Approximation Using the Uniform Metric. Preliminary version appeared in Proc. 10th ACM Symp. on Computational Geometry (SCG), 1994, 322-331.
  6. G. Das and M.T. Goodrich, On the Complexity of Optimization Problems for 3-Dimensional Convex Polyhedra and Decision Trees. Preliminary version appeared in 1995 Workshop on Algorithms and Data Structures (WADS).
  7. C.A. Duncan, M.T. Goodrich, and E.A. Ramos, Efficient Approximation and Optimization Algorithms for Computational Metrology,8th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1997.
  8. M.T. Goodrich, L.J. Guibas, J. Hershberger, P.J. Tanenbaum, Snap Rounding Line Segments Efficiently in Two and Three Dimensions, Proc. 13th ACM Symp. on Computational Geometry (SCG), 1997.
  9. M.T. Goodrich. An Improved Ray Shooting Method for Constructive Solid Geometry Models via Tree Contraction. International Journal of Computational Geometry and Applications, 8(1), 1998, 1-23.
  10. M.T. Goodrich, J.S.B. Mitchell, and M.W. Orletsky, "Methods for Approximate Geometric Pattern Matching under Rigid Motion," IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI), 21(4), 1999, 371-379.
  11. N.M. Amato, M.T. Goodrich, and E.A. Ramos, A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time. Final version in Discrete and Computational Geometry. (Preliminary version appeared in 16th ACM Symp. on Computational Geometry (SCG), 2000, 201-212.

Large-Scale (Parallel and External-Memory) Algorithms

  1. M.T. Goodrich, J.J. Tsay, D.E. Vengroff, J.S. Vitter, External-Memory Computational Geometry , 34th IEEE Symp. on Foundations of Computer Science (FOCS), 1993, 714-723.
  2. M.T. Goodrich, Y. Matias, and U. Vishkin, Optimal Parallel Approximation Algorithms for Prefix Sums and Integer Sorting, Proc. 5th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1994, 241--250.
  3. M.J. Atallah, M.T. Goodrich, and S.R. Kosaraju. Parallel Algorithms for Evaluating Sequences of Set-Manipulation Operations. Journal of the ACM, 41(6), 1994, 1049-1088.
  4. Y.J. Chiang, M.T. Goodrich, E.F. Grove, R. Tamassia, D.E. Vengroff, J.S. Vitter, External-Memory Graph Algorithms, 6th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1995.
  5. N.M. Amato, M.T. Goodrich, E.A. Ramos. Parallel Algorithms for Higher-Dimensional Convex Hulls, Proc. 35th IEEE Symp. on Foundations of Computer Science (FOCS), 1994, 683-694.
  6. N.M. Amato, M.T. Goodrich, E.A. Ramos. Computing Faces in Segment and Simplex Arrangements, Proc. 27th ACM Symp. on Theory of Computing (STOC), 1995, 672-682.
  7. M.T. Goodrich and S.R. Kosaraju. Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation. J. ACM, 43(2), 1996, 331-361.
  8. M. Ghouse and M.T. Goodrich. "Fast Randomized Parallel Methods for Planar Convex Hull Construction. Computational Geometry: Theory and Applications, 7, 1997, 219-235.
  9. M.T. Goodrich and E.A. Ramos, Bounded-Independence Derandomization of Geometric Partitioning with Applications to Parallel Fixed-Dimensional Linear Programming, Discrete and Computational Geometry, 18, 1997, 397-420.
JHU CS Home Page.

Goodrich's Home Page.