Selected Publications  Michael T. Goodrich
Book Chapters

Ch4.
M.T. Goodrich and K. Ramaiyer,
Geometric data Structures,
in J.R. Sack and J. Urrutia, eds.,
Handbook of Computational Geometry,
463489, Elsevier Science, 2000.

Ch5.
M.T. Goodrich and R. Tamassia,
Simplified Analyses of Randomized Algorithms for Searching, Sorting,
and Selection,
in S. Rajasekaran, P.M. Pardalos, J.H. Reif, and J.D.P. Rolim, eds.,
Handbook of Randomization,
Kluwer Academic Publishers, 2001, Vol. 1, 2334.

Ch6/Ch3.
M.T. Goodrich,
Parallel Algorithms in Geometry,
in J.E. Goodman and J. O'Rourke, eds.,
Handbook of Discrete and Computational Geometry, Second Edition,
Chapman and Hall/CRC Press, 953967, 2004.

Ch7.
C. Duncan and M.T. Goodrich,
Approximate Geometric Query Structures,
Handbook of Data Structures and Applications,
Chapman and Hall/CRC Press, 2612617, 2005.

Ch8.
M.T. Goodrich, R. Tamassia, and L. Vismara,
Data Structures in JDSL,
Handbook of Data Structures and Applications,
Chapman and Hall/CRC Press, 4314322, 2005.

Ch9.
C.A. Duncan and M.T. Goodrich,
Planar Orthogonal and Polyline
Drawing Algorithms, Handbook of Graph Drawing and
Visualization, Chapman & Hall/CRC Press, Inc., to appear.

Ch10.
Y. Cho, L. Bao and M.T. Goodrich,
Secure LocationBased
Access Control in WLAN Systems,
From Problem Toward Solution:
Wireless and Sensor Networks Security,
Zhen Jiang and Yi Pan, eds., Nova Science Publishers, Inc., Chapter
17, 2007.
Information Security Algorithms

C80.
G. Ateniese, B. de Medeiros, and M.T. Goodrich,
TRICERT: A Distributed Certified Email
Scheme, Network and Distributed Systems Security Symposium, 2001,
4756.

C83.
M.T. Goodrich, R. Tamassia, and A. Schwerin,
Implementation of an Authenticated Dictionary
with Skip Lists and Commutative Hashing,
DARPA Information Survivability Conference & Exposition II
(DISCEX II),
IEEE Press, 2001, 6882.

C85.
A. Anagnostopoulos, M. T. Goodrich, and R. Tamassia, Persistent
Authenticated Dictionaries and
Their Applications, Proc. Information Security
Conference
(ISC 2001), Lecture
Notes
in Computer Science, vol.
2200,
SpringerVerlag, pp. 379393, 2001.

C86.
M. T. Goodrich, and R. Tamassia and J. Hasic, An
Efficient Dynamic and Distributed
Cryptographic Accumulator, Proc. Information Security
Conference (ISC 2002) Lecture
Notes in Computer Science, vol. 2433, SpringerVerlag,
pp. 372388, 2002.

C90.
M. T. Goodrich, R. Tamassia, N. Triandopoulos and R. Cohen,
Efficient Authenticated Data Structures for Graph Connectivity
and Geometric Search Problems, Algorithmica, to appear. Earlier
version appeared in RSA, Cryptographers' Track, 295313,
Springer, LNCS 2612, 2003.

C91.
M. T. Goodrich, M. Shin, R. Tamassia, W. H. Winsborough, Authenticated dictionaries for fresh
attribute
credentials, Proc. Trust Management Conference,
332347, Springer, LNCS 2692, 2003.

C94.
A. Bagchi, A. Chaudhary, M.T. Goodrich, and S. Xu,
Constructing disjoint paths for secure communication.
17th International Symposium on Distributed Computing (DISC), 181195, 2003.

C98.
M. T. Goodrich, J. Z. Sun, and R. Tamassia,
Efficient TreeBased Revocation in Groups of LowState
Devices,
CRYPTO 2004, Springer, LNCS 3152, 511527, 2004.

C100.
M.J. Atallah, K.B. Frikken, M.T. Goodrich, and R. Tamassia,
Secure Biometric Authentication for Weak Computational
Devices,
9th Int. Conf. on Financial Cryptograpy and Data Security, 357371, 2005.

C101.
M.T. Goodrich,
LeapFrog Packet Linking and Diverse Key Distributions for
Improved Integrity in Network Broadcasts,
IEEE Symposium on Security and Privacy (SSP), 196207, 2005.

C103.
M.J. Atallah, M.T. Goodrich, and R. Tamassia,
Indexing Information for Data Forensics,
3rd Applied Cryptography and Network Security Conference (ACNS),
Lecture Notes in Computer Science 3531, Springer, 206221, 2005.

C104.
W. Du and M.T. Goodrich,
Searching for HighValue Rare Events with Uncheatable Grid Computing,
3rd Applied Cryptography and Network Security Conference (ACNS),
Lecture Notes in Computer Science 3531, Springer, 122137, 2005.

C108.
M.T. Goodrich, R. Tamassia, and D. Yao,
Accredited DomainKeys: A Service Architecture for Improved Email
Validation,
Conference on Email and AntiSpam (CEAS), 2005.

C112.
M.T. Goodrich, M. Sirivianos, J. Solis, G. Tsudik, E. Uzun,
Loud
And Clear: HumanVerifiable Authentication Based on Audio,
26th IEEE Int. Conference on Distributed Computing Systems (ICDCS), 2006.

C113.
M.T. Goodrich, R. Tamassia, and D. Yao,
Notarized Federated
Identity Management for Web Services,
20th IFIP WG Working Conference on Data and Application Secuirity
(DBSec), Springer, LNCS 4127, 133147, 2006.

J61.
M.T. Goodrich,
Probabalistic Packet Marking for LargeScale IP Traceback,
IEEE/ACM Transactions on Networking,
16(1), 1524, 2008.
Preliminary version (C89)
appeared at 9th ACM Conf. on Computer and Communications Security (CCS),
2002, 117126.

C115.
Y. Cho, L. Bao and M.T. Goodrich,
LAAC: A LocationAware Access
Control Protocol, In Proc. of International Workshop on Ubiquitous
Access Control (IWUAC), San Jose, CA, July 17, 2006.

J64.
M.T. Goodrich,
Pipelined Algorithms to Detect Cheating in LongTerm Grid
Computations,
Theoretical Computer Science, vol. 408, 199207, 2008.

C131.
M.T. Goodrich,
The Mastermind Attack on Genomic
Data, 30th IEEE Symp. on Security and Privacy, 2009.

C133. M.T. Goodrich, R. Tamassia, and N. Triandopoulos, J.Z. Sun,
Reliable Resource Searching
in P2P Networks,
5th International ICST Conference on
Security and Privacy in Communication
Networks (SecureComm), Lecture Notes of ICST, Springer, 2009.

C139. W. Du, M.T. Goodrich, T. Luo, and G. Wang,
Bureaucratic Protocols for Secure TwoParty Sorting, Selection, and
Permuting, 5th ACM
Symposium on Information, Computer
and Communications Security, 2010.

C145.
A.U. Asuncion and M.T. Goodrich,
Turning Privacy Leaks
into Floods: Surreptitious
Discovery of Social Network Friendships and Other Sensitive Binary
Attribute Vectors,
Proc. Workshop on Privacy in the Electronic Society (WPES), held in
conjunction with the
17th ACM Conference on Computer and Communications Security (CCS),
2010.

C148.
D. Eppstein, M.T. Goodrich, R. Tamassia,
PrivacyPreserving
DataOblivious Geometric
Algorithms for Geographic Data, Proc. 18th ACM SIGSPATIAL
International Conference
on Advances in Geographic Information Systems (ACM GIS), 2010.

C166.
M.T. Goodrich, O. Ohrimenko, M. Mitzenmacher, and R. Tamassia,
Practical Oblivious Storage,"
2nd ACM Conf. on Data and Application Security and Privacy (CODASPY).
1324, 2012.
Parallel, Distributed, and ExternalMemory Algorithms

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

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

J26.
M.H. Nodine, M.T. Goodrich, and J.S. Vitter,
Blocking for External
Graph Searching,
Algorithmica, 16(2), 1996, 181214.

J27.
R. Cole, M.T. Goodrich, C. O'Dunlaing,
A Nearly Optimal
Deterministic Parallel Voronoi Diagram Algorithm,
Algorithmica, 16, 1996, 569617.

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.

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.

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

J32.
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.
Preliminary version (C45) appeared
in 7th ACMSIAM Symp. on Discrete Algorithms
(SODA), 1996, 132141.

J36.
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.
Preliminary version (C53) appeared in
13th ACM Symp. on Computational Geometry (SCG), 1997.

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

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

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

C84.
A. Bagchi, A. Chaudhary, R. Carg, M.T. Goodrich,
and V. Kumar,
SellerFocused Algorithms for Online
Auctioning,
2001 Workshop on Algorithms and Data Structures (WADS),
Lecture Notes in Computer Science 2125, SpringerVerlag, 2001,
135147.

C105.
L. Arge, D. Eppstein, and M.T. Goodrich,
SkipWebs: Efficient Distributed Data Structures
for MultiDimensional Data Sets,
24th ACM Symp. on Principles of Distributed Computing (PODC),
2005.

C111.
M.T. Goodrich, M.J. Nelson, and J.Z. Sun,
The Rainbow Skip
Graph: A FaultTolerant
ConstantDegree Distributed Data Structure, 16th ACMSIAM
Symposium on Discrete
Algorithms (SODA), 384393, 2006.

C114.
M.T. Goodrich and D.S. Hirschberg,
Efficient Parallel Algorithms
for Dead Sensor Diagnosis and Multiple Access Channels,
18th ACM Symp. on Parallelism in Algorithms and
Architectures (SPAA), 118127, 2006.

J56.
A. Bagchi, A. Chaudhary, M.T. Goodrich, C. Li, and M.
ShmueliScheuer,
Achieving Communication
Efficiency through PushPull Partitioning of Semantic Spaces to
Disseminate Dynamic Information,
IEEE Trans. on Knowledge and Data Engineering,
18(10), 13521367, 2006.

C126. L. Arge, M.T. Goodrich, M. Nelson, and N. Sitchinava,
Fundamental Parallel Algorithms
for PrivateCache Chip Multiprocessors, Proc. 20th ACM
Symp. on Parallelism in Algorithms
and Architectures (SPAA), 2008, 197206.

C138. L. Arge, M.T. Goodrich, and N. Sitchinava,
Parallel External Memory Graph Algorithms,
24th IEEE International Parallel & Distributed Processing Symposium
(IPDPS), 2010.

O12.
M.T. Goodrich,
Simulating Parallel Algorithms in
the MapReduce Framework with Applications
to Parallel Computational Geometry, Second Workshop on
Massive Data Algorithmics (MASSIVE), 2010.
Graph and Network Algorithms

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

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

C46.
M. Chrobak, M.T. Goodrich, and R. Tamassia,
Convex
Drawings of Graphs in Two and Three Dimensions,
12th ACM Symp. on Computational Geometry (SCG), 1996.

J39.
C.A. Duncan, M.T. Goodrich, and S. Kobourov,
Balanced Aspect Ratio Trees
and Their Use for Drawing Very Large Graphs,
Journal of Graph Algorithms and Applications, 4(3), 2000,
1946.
Preliminary version (C61)
appeared in Proceedings of the Sixth Symposium on Graph Drawing, 1998.

J40.
M.T. Goodrich and C.G. Wagner,
A framework for drawing planar graphs with curves and polylines,
Journal of Algorithms,
vol. 37, 399421, 2000.
Preliminary version (C60) appeared in
6th Int. Symp. on Graph Drawing (GD),
LNCS 1547, SpringerVerlag, 1998, 153166.

J43.
C.C. Cheng, C. A. Duncan, M. T. Goodrich, and S. G. Kobourov,
Drawing Planar Graphs with Circular Arcs,
Discrete & Computational Geometry 25:
405418 (2001).
Preliminary version (C69)
appeared in 7th Int. Symp. on Graph Drawing (GD),
LNCS 1731, SpringerVerlag, 1999, 117126..

J47.
T. Chan, M.T. Goodrich, S.R. Kosaraju, and R. Tamassia,
Optimizing
Area and Aspect Ratio in StraightLine Orthogonal Tree Drawings,
Computational Geometry: Theory and Applications,
Volume 23, Issue 2 , September 2002, Pages 153162.
Preliminary version (C48)
appeared in
Graph Drawing '96, 1996.

J48.
C. A. Duncan, M. T. Goodrich, and S. G. Kobourov,
PlanarityPreserving Clustering and Embedding for Large Planar
Graphs,
CGTA: Computational Geometry: Theory and Applications
24(2), 95114, 2003.
Preliminary version (C70) appeared in
7th Int. Symp. on Graph Drawing (GD), Lecture
Notes in Computer Science 1731, SpringerVerlag, 1999, 186196.

C96.
F. Brandenberg, D. Eppstein, M.T. Goodrich, S.G. Kobourov, G. Liotta,
P. Mutzel,
Selected Open Problems in Graph Drawing,
11th Int. Symp. on Graph Drawing (GD),
LNCS, SpringerVerlag, 2003.

J50.
G. Barequet, M.T. Goodrich, and C. Riley,
Drawing Planar Graphs with Large Vertices and
Thick Edges,
J. of Graph Algorithms and Applications (JGAA), 8(1), 320,
2004.
Preliminary version (C93) appeared in
2003 Workshop and Data Structures and Algorithms (WADS), LNCS
2748, 2003, 281293.

J52.
P. Gajer, M.T. Goodrich, and S.G. Kobourov,
A MultiDimensional Approach to ForceDirected Layouts
of Large Graphs,
Computational Geometry: Theory and Applications (CGTA),
29(1), 318, 2004.
Preliminary version (C79) appeared in
Graph Drawing 2000, 211221.

J55.
M. Dickerson, D. Eppstein, M.T. Goodrich, J. Meng,
Confluent Drawings: Visualizing Nonplanar Diagrams in a Planar Way,
J. of Graph Algorithms and Applications (JGAA), 2005.
Preliminary version (C95) appeared in
11th Int. Symp. on Graph Drawing (GD), LNCS 2912, 2003, 112.

J58.
D. Eppstein, M.T. Goodrich, and J.Y. Meng,
Confluent Layered Drawings,
Algorithmica, 47(4), 439452, 2007.
Preliminary version (C99) appeared in
12th Int. Symp. on Graph Drawing (GD),
Springer, Lecture Notes in Computer Science 3383, 184194, 2004.

C109. M.T. Goodrich, G.S. Lueker, and J.Z. Sun,
CPlanarity of
Extrovert Clustered Graphs, Graph Drawing, 211222, 2005.

C110.
D. Eppstein, M.T. Goodrich, J.Y. Meng, DeltaConfluent
Drawings, Graph Drawing, 165176, 2005.

C116. M.B. Dillencourt, D. Eppstein, and M.T. Goodrich,
Choosing Colors for Geometric Graphs
via Color Space Embeddings, Graph Drawing (GD), 2006.

C127.
D. Eppstein and M.T. Goodrich,
Succinct Greedy Graph Drawing in the Hyperbolic Plane,
Graph Drawing 2008.

C134. C.A. Duncan, M.T. Goodrich, S.G. Kobourov,
Planar Drawings of HigherGenus Graphs,
Proc. 17th Int. Symp. on Graph Drawing (GD), Lecture Notes in
Computer Science, Springer,
2009.

C135. D. Eppstein, M.T. Goodrich, L. Trott,
Going
Offroad: Transversal Complexity in Road
Networks, Proc. 17th ACM SIGSPATIAL International
Conference on Advances in Geographic
Information Systems (ACM GIS), 2009.

C136. M.T. Goodrich and Darren Strash,
Succinct Greedy
Geometric Routing in the Euclidean
Plane, 13th Int. Symp. on Algorithms and Computation
(ISAAC), Lecture Notes in Computer Science, Springer, 2009.

C140.
M.T. Dickerson, M.T. Goodrich, and T.D. Dickerson,
RoundTrip Voronoi Diagrams and
Doubling Density in Geographic Networks, 7th Int. Symp.
on Voronoi Diagrams in Science
and Engineering (ISVD), IEEE Press, 2010.

C142.
C.A. Duncan, D. Eppstein, M.T. Goodrich, S. Kobourov, and M.
Nollenburg,
Lombardi
Drawings of Graphs, Proc. 18th Int. Symp. on Graph
Drawing (GD), 2010.

C143.
E. WolfChambers, D. Eppstein, M.T. Goodrich, and M. Loffler,
Drawing Graphs in the
Plane with a Prescribed Outer Face and Polynomial Area,
Proc. 18th Int. Symp. on Graph
Drawing (GD), 2010.

C144.
C.A. Duncan, D. Eppstein, M.T. Goodrich, S. Kobourov, and M.
Nollenburg,
Drawing
Trees with Perfect Angular Resolution and Polynomial
Area, Proc. 18th Int. Symp. on
Graph Drawing (GD), 2010.

C146.
D. Eppstein, M.T. Goodrich, D. Strash, and L. Trott,
Extended Dynamic Subgraph Statistics
Using hIndex Parameterized Data Structures, Proc. 4th
Annual International Conference
on Combinatorial Optimization and Applications (COCOA), 2010.
Data Structures and Algorithms

J23.
M.T. Goodrich, M. Ghouse, and J. Bright,
Sweep Methods for Parallel
Computational Geometry, Algorithmica, 15(2), 1996, 126153.
Preliminary version (C17) appeared
in 2nd ACM Symp. on Parallel Algorithms and Architectures (SPAA),
1990, 280289.

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

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

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

J41.
C. A. Duncan, M. T. Goodrich, and S. G. Kobourov,
Balanced Aspect Ratio Trees: Combining the Advantages of kd Trees
and Octrees,
Journal of Algorithms 38:303333, 2001.
Preliminary version (C65)
appeared at ACMSIAM
Symp. on Discrete Algorithms (SODA), 1999, 300309.

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

C72.
M.T. Goodrich,
Competitive treestructured dictionaries,
11th ACM/SIAM Symp. on Discrete Algorithms (SODA), 2000, 705706.

C77.
A.L. Buchsbaum, M.T. Goodrich, J.R. Westbrook,
Range searching over tree cross products,
8th European Symp. on Algorithms (ESA),
120131, 2000.

C78. C.A. Duncan, M.T. Dickerson, and M.T. Goodrich,
kD Trees
are Better When Cut on the Longest Side,
8th European Symposium on Algorithms (ESA),
LNCS 1879, SpringerVerlag, 2000, 179190.

J45.
R. Tamassia, M.T. Goodrich, L. Vismara, M. Handy, G. Shubina,
R. Cohen, B. Hudson, R.S. Baker, N. Gelfand, and U. Brandes,
JDSL: The Data
Structures Library in Java, Dr. Dobbs Journal, 323, 2001, 2131.

C107.
A. Chaudhary and M.T. Goodrich,
Balanced Aspect Ratio Trees Revisited,
Workshop on Algorithms and Data Structures (WADS),
Lecture Notes in Computer Science 3608, Springer, 2005.

J54.
A. Bagchi, A.L. Buchsbaum, and M.T. Goodrich,
Biased Skip Lists
Algorithmica,
42(1), 3148, 2005.
Preliminary version (C88) appeared in
Algorithms and Computation : 13th International Symposium, ISAAC
2002, 113.

J57.
D. Eppstein, M.T. Goodrich, and J.Z. Sun,
The Skip Quadtree: A Simple Dynamic Data Structure for
Multidimensional Data,
Int. Journal on Computational Geometry and Applications,
18(1/2),
131160, 2008.
Preliminary version (C102) appeared in
21st ACM Symp. on Computational Geometry (SCG), 2005.

J60.
D. Eppstein, M.T. Goodrich, and D. Hirschberg,
Improved Combinatorial Group Testing Algorithms
for RealWorld Problem Sizes,
SIAM Journal on Computing, accepted for publication.
Preliminary vesion (C106)
appeared in Workshop on Algorithms and Data Structures (WADS),
LNCS 3608, Springer, 2005, 8698.

C120. D. Eppstein and M.T. Goodrich,
SpaceEfficient Straggler
Identification in RoundTrip
Data Streams via Newton's Identities and Invertible Bloom Filters,
Proc. Workshop on
Algorithms and Data Structures (WADS), LNCS 4619, Springer, pp.
638649, 2007.

C132. W. Du, D. Eppstein, M.T. Goodrich, and G.S. Lueker,
On the
Approximability of Geometric
and Geographic Generalization and the MinMax Bin Covering
Problem, Proc. Algorithms and
Data Structures Symposium (formerly WADS), LNCS, Springer, 2009.

J67.
M.T. Goodrich, On the Algorithmic
Complexity of the Mastermind Game with BlackPeg
Results, Information Processing Letters,
2009.

C137. M.T. Goodrich,
Randomized Shellsort: A Simple
Oblivious Sorting Algorithm, 20th
ACMSIAM Symposium on Discrete Algorithms (SODA), 2010.

C147.
M.T. Goodrichand D. Strash,
Priority Range
Trees, Proc. 21st International Symposium
on Algorithms and Computation (ISAAC), 2010.

C149.
M.T. Goodrich,
Spinthebottle
Sort and Annealing Sort:
Oblivious Sorting via Roundrobin
Random Comparisons, 8th annual Workshop on Analytic
Algorithmics and Combinatorics
(ANALCO), in conjunction with the ACMSIAM Symposium on Discrete
Algorithms
(SODA), 2011.
Geometric Algorithms

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

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

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

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

J28.
G. Das and M.T. Goodrich,
On
the Complexity of Optimization Problems for 3Dimensional Convex Polyhedra
and Decision Trees, Computational Geometry: Theory and
Applications, 8, 1997, 123137.
Preliminary version appeared in 1995 Workshop on
Algorithms and Data Structures (WADS).

J31.
L.P. Chew, M.T. Goodrich, D.P. Huttenlocher, K. Kedem, J.M. Kleinberg,
and D. Kravets.
Geometric Pattern Matching under Euclidean
Motion,
Computational Geometry: Theory and Applications, 7, 1997,
113124.
Preliminary version appeared in
Proc. 5th Canadian Conference on Computational Geometry (CCCG),
1993, 151156.

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

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

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

J34.
G. Barequet, A.J. Briggs, M.T. Dickerson, and M.T. Goodrich,
Offsetpolygon annulus placement problems,
Computational Geometry: Theory and Applications, vol. 11 (34),
pp. 125141, 1998.
Preliminary version (C55)
appeared in Proc. 5th Workshop on Algorithms and Data Structures (WADS),
LNCS 1272, 378391, 1997.

C54.
G. Barequet, A. Briggs, M. Dickerson, C. Dima, and M.T. Goodrich,
Animating the
PolygonOffset Distance Function, 13th ACM Symp. on
Computational Geometry (SCG),
1997, 479480, and the Video Review for the 13th ACM Symp. on
Computational Geometry.

J37.
M.T. Goodrich, J.S.B. Mitchell, and M.W. Orletsky,
"Approximate Geometric Pattern Matching under
Rigid Motion," IEEE Trans. on Pattern Analysis and Machine
Intelligence (PAMI), 21(4), 1999, 371379.
A preliminary version (C38) appeared in ACM
Symp. on Computational Geometry, 1994, 103112.

C68.
G. Barequet, C. Duncan, M.T. Goodrich, S. Kumar, M. Pop,
Efficient PerspectiveAccurate
Silhouette Computation, 15th ACM Symp. on Computational Geometry
(SCG), 1999, 417418,
and the Video Review for the 15th ACM Symp. on Computational Geometry (SCG).

C73.
N.M. Amato, M.T. Goodrich, E.A. Ramos,
Computing the Arrangement of Curve Segments: DivideandConquer
Algorithms via Sampling,
11th ACM/SIAM Symp. on Discrete Algorithms (SODA), 2000, 705706.

J42.
G. Barequet, M.T. Dickerson, and M.T. Goodrich,
Voronoi diagrams for
polygonoffset distance functions,
Discrete and Computational Geometry,
vol. 25 (2), pp. 271291, 2001.
Preliminary version (C56)
appeared at Workshop on Algorithms and Data Structures (WADS), 1997,
LNCS, 200209.

C82.
M. Pop, G. Barequet, C.A. Duncan, M.T. Goodrich, W. Hwang, and
S. Kumar,
Efficient
PerspectiveAccurate Silhouette Computation and Applications,
17th ACM Symp. on Computational Geometry (SCG), 2001, 6068.

J44.
N.M. Amato, M.T. Goodrich, and E.A. Ramos,
A Randomized Algorithm for Triangulating a Simple Polygon in Linear
Time,
Discrete and Computational Geometry, 26(2), 2001, 245265.
Preliminary version (C76) appeared in
16th ACM Symp. on Computational Geometry (SCG), 2000,
201212.

J46.
G. Barequet, D.Z. Chen, O. Daescu, M.T. Goodrich, and J. Snoeyink,
Efficiently approximating polygonal paths in three and higher
dimensions, Algorithmica, vol. 33 (2), pp. 150167, 2002.
Preliminary version (C59) appeared
in ACM Symp. on Computational Geometry (SoCG), 317326, 1998.

J49.
A.L. Buchsbaum and M.T. Goodrich,
ThreeDimensional Layers of Maxima,
Algorithmica,
39, 275286, 2004.
Preliminary version (C87) appeared in
10th Annual European Symposium (ESA), 2002, LNCS 2461.

J51.
G. Barequet, M.T. Goodrich, A. LeviSteiner, and D. Steiner,
Contour Interpolation by Straight Skeletons,
Graphical Models (GM), 66(4), 245260, 2004.
Preliminary
version (C92) appeared in
14th ACMSIAM Symp. on Discrete Algorithms (SODA),
119127, 2003.

J53.
G. Barequet, P. Bose, M.T. Dickerson, and M.T. Goodrich,
Optimizing a Constrained Convex Polygonal Annulus,
J. of Discrete Algorithms (JDA),
3(1), 126, 2005.

J59.
A. Bagchi, A. Chaudhary, D. Eppstein, and M.T. Goodrich,
Deterministic sampling and
range counting in geometric data streams,
ACM Transactions on Algorithms, accepted for publication.
Preliminary version (C97) appeared in
12th ACM Annual Symposium on Computational Geometry (SoCG), 2004.

C117. D. Eppstein, M.T. Goodrich, and Sitchinava,
Guard Placement
for Wireless Localization,
Proc. 23rd ACM Symposium on Computational Geometry (SCG), 2736,
2007.

C119.
M.J. Atallah, M. Blanton, M.T. Goodrich, and S. Polu,
DiscrepancySensitive Dynamic
Fractional Cascading, Dominated Maxima Searching, and 2d Nearest
Neighbors in Any
Minkowski Metric, Proc. Workshop on Algorithms and Data
Structures (WADS), LNCS
4619, Springer, pp. 114126, 2007.

C123.
D. Eppstein, M.T. Goodrich, E. Kim, and R. Tamstorf,
"Approximate Topological Matching of Quadrilateral Meshes,"
Proc. IEEE Int. Conf. on Shape Modeling and Applications (SMI),
2008, 8392.

C124.
G. Bareqet, D. Eppstein, M.T. Goodrich, and A. Waxman,
"Straight Skeletons of ThreeDimensional Polyhedra,"
Proc. 16th European Symposium on Algorithms (ESA),
2008.

J65.
D. Eppstein, M.T. Goodrich, E. Kim, and R. Tamstorf,
"Motorcycle Graphs: Canonical Quad Mesh Partitioning,"
Proc. 6th European Symposium on Geometry Processing (SGP),
2008.

C128. D. Eppstein and M.T. Goodrich,
Studying (NonPlanar) Road
Networks Through an Algorithmic Lens,
Proc. 16th ACM SIGSPATIAL International Conference on Advances
in Geographic Information Systems (ACM GIS), 2008, 125134.
Best paper award.

C130.
D. Eppstein, M.T. Goodrich, and D. Strash,
LinearTime Algorithms for Geometric Graphs
with Sublinearly Many Crossings, SODA 2009.

C141. M.T. Dickerson, D. Eppstein, and M.T. Goodrich,
Cloning Voronoi Diagrams via Retroactive
Data Structures, 18th European Symposium on Algorithms (ESA), 2010.
Goodrich's Home Page.