Selected Publications  Michael T. Goodrich
Information Security Algorithms

M.T. Goodrich and R. Tamassia,
An Efficient Dynamic and Distributed Cryptographic Accumulator,
provision patent filing, November 2000.

M.T. Goodrich and R. Tamassia,
Efficient Authenticated Dictionaries
with Skip Lists and Commutative Hashing,
provisional patent filing, November 2000.

M.T. Goodrich, R. Tamassia, and A. Schwerin,
Implementation of an Authenticated Dictionary
with Skip Lists and Commutative Hashing,
DISCEX II, 2001.

M.T. Goodrich,
Efficient and Secure Network Routing Algorithms,
provisional patent filing, January 2001.

G. Ateniese, B. de Medeiros, and M.T. Goodrich,
TRICERT: A Distributed Certified Email
Scheme, Network and Distributed Systems Security Symposium, February 2001.
Internet Algorithmics and BulkSynchronous Computing

M.T. Goodrich, CommunicationEfficient
Parallel Sorting,
SIAM Journal on Computing, 29(2), 1999, 416432.
Preliminary version appeared in
28th ACM Symp.
on Theory of Computing (STOC), 1996.

M.T. Goodrich,
Randomized
FullyScalable BSP Techniques for MultiSearching and Convex Hull Construction,8th
ACMSIAM Symp. on Discrete Algorithms (SODA), 1997.

T.H. Cormen and M.T. Goodrich,
A
Bridging Model for Parallel Computation, Communication, and I/O,ACM
Computing Surveys, 28A(4), December 1996.

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, 210.

A. Bagchi, A. Chaudhary, R. Carg, M.T. Goodrich,
and V. Kumar,
SellerFocused Algorithms for Online
Auctioning.
Algorithm Engineering and Education

Michael T. Goodrich and Roberto Tamassia, Data
Structures and Algorithms in JAVA, Wiley, 1998.

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.
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.

M. T. Goodrich and J. K. Kloss, Tiered
Vector: an Efficient Dynamic Array for JDSL. Poster and technical
note presented at OOPSLA
'98.

N. Gelfand, M. T. Goodrich and Roberto Tamassia, Teaching
Data Structure Design Patterns, presented at ACM SIGCSE '98.

M.T. Goodrich and R. Tamassia, Teaching
the Analysis of Algorithms with Visual Proofs, presented at ACM
SIGCSE '98.

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.

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.

M.T. Goodrich and R. Tamassia, Using
Randomization in the Teaching of Data Structures and Algorithms, presented
at ACM SIGCSE '99.

M.T. Goodrich and R. Tamassia,
Teaching Internet Algorithmics,
ACM SIGCSE '01.
Graph Visualization

M.T. Goodrich. Planar
Separators and Parallel Polygon Triangulation. Journal of Computer
& System Sciences, 51(3), 1995, 374389.

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, 333356.

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.

T. Chan, M.T. Goodrich, S.R. Kosaraju, and R. Tamassia,
Optimizing
Area and Aspect Ratio in StraightLine Orthogonal Tree Drawings,Graph
Drawing '96, 1996.

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.

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

C.A. Duncan, M.T. Goodrich, and S.G. Kobourov,
PlanarityPreserving Clustering and Embedding for Large Planar Graphs,
Proc. Graph Drawing (GD),
Lecture Notes Comput. Sci., SpringerVerlag, Vol. 1731, 1999,
186196.

P. Gajer, M.T. Goodrich, and S.G. Kobourov,
A Fast Multi Dimensional Algorithm for Drawing Large Graphs,
Graph Drawing 2000, 211221.
Data Structures

M.T. Goodrich and R. Tamassia. Dynamic
Ray Shooting and Shortest Paths via Balanced Geodesic Triangulations.
J.
Algorithms, 23, 1997, 5173.

M.T. Goodrich, M. Orletsky, and K. Ramaiyer,
Methods
for Achieving Fast Query Times in Point Location Data Structures,8th
ACMSIAM Symp. on Discrete Algorithms (SODA), 1997.

M.T. Goodrich and R. Tamassia. Dynamic
Trees and Dynamic Point Location. SIAM J. Comput., 28(2),
1999, 612636.

C.A Duncan, M.T. Goodrich, and S. Kobourov, Balanced
Aspect Ratio Trees: Combining the Advantages of kd Trees and Octrees
(compressed),
10th
ACMSIAM Symposium on Discrete Algorithms (SODA), 1999.

M.T. Goodrich and J.G. Kloss II,
"Tiered Vectors: Efficient Dynamic Arrays for RankBased Sequences,"
1999 Workshop on Algorithms and Data Structures (WADS),
1999, 205216.
Geometric Algorithms

M.T. Goodrich. A
Polygonal Approach to HiddenLine and HiddenSurface Elimination.
Computer
Vision, Graphics, and Image Processing: Graphical Models and Image Processing,
54(1), 1992, 112.

M.T. Goodrich, M.J. Atallah, and M. Overmars. OutputSensitive
Methods for Rectilinear Hidden Surface Removal.
Information and
Computation, 107(1), 1993, 124.

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, 151156.

H. Bronnimann and M.T. Goodrich. Almost
Optimal Set Covers in Finite VCDimension. Preliminary version appeared
in
Proc. 10th ACM Symp. on Computational Geometry (SCG), 1994, 293302.

M.T. Goodrich. Efficient
PiecewiseLinear Function Approximation Using the Uniform Metric. Preliminary
version appeared in
Proc. 10th ACM Symp. on Computational Geometry (SCG),
1994, 322331.

G. Das and M.T. Goodrich,
On
the Complexity of Optimization Problems for 3Dimensional Convex Polyhedra
and Decision Trees. Preliminary version appeared in 1995 Workshop on
Algorithms and Data Structures (WADS).

C.A. Duncan, M.T. Goodrich, and E.A. Ramos, Efficient
Approximation and Optimization Algorithms for Computational Metrology,8th
ACMSIAM Symp. on Discrete Algorithms (SODA), 1997.

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.

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, 123.

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, 371379.

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,
201212.
LargeScale (Parallel and ExternalMemory) Algorithms

M.T. Goodrich, J.J. Tsay, D.E. Vengroff, J.S. Vitter,
ExternalMemory
Computational Geometry , 34th IEEE Symp. on Foundations of Computer
Science (FOCS), 1993, 714723.

M.T. Goodrich, Y. Matias, and U. Vishkin, Optimal
Parallel Approximation Algorithms for Prefix Sums and Integer Sorting,
Proc.
5th ACMSIAM Symp. on Discrete Algorithms (SODA), 1994, 241250.

M.J. Atallah, M.T. Goodrich, and S.R. Kosaraju.
Parallel
Algorithms for Evaluating Sequences of SetManipulation Operations.
Journal
of the ACM, 41(6), 1994, 10491088.

Y.J. Chiang, M.T. Goodrich, E.F. Grove, R. Tamassia, D.E. Vengroff, J.S.
Vitter,
ExternalMemory
Graph Algorithms, 6th ACMSIAM Symp. on Discrete Algorithms (SODA),
1995.

N.M. Amato, M.T. Goodrich, E.A. Ramos.
Parallel
Algorithms for HigherDimensional Convex Hulls,
Proc. 35th IEEE
Symp. on Foundations of Computer Science (FOCS), 1994, 683694.

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, 672682.

M.T. Goodrich and S.R. Kosaraju. Sorting
on a Parallel Pointer Machine with Applications to Set Expression Evaluation.
J.
ACM, 43(2), 1996, 331361.

M. Ghouse and M.T. Goodrich. "Fast
Randomized Parallel Methods for Planar Convex Hull Construction.
Computational
Geometry: Theory and Applications, 7, 1997, 219235.

M.T. Goodrich and E.A. Ramos, BoundedIndependence
Derandomization of Geometric Partitioning with Applications to Parallel
FixedDimensional Linear Programming,
Discrete and Computational
Geometry, 18, 1997, 397420.
JHU
CS Home Page.
Goodrich's Home Page.