CURRICULUM VITAE

[nom]

Dept. of Computer Science · E-mail: mike.t.goodrich (at) [lien]

Bren School of Info. & Computer Sciences · [lien] goodrich/

University of California, Irvine

Irvine, CA [téléphone]

CITIZENSHIP: U.S.A.

EDUCATION

Ph.D. · 1987 · Efficient Parallel Techniques for Computational Geometry

Computer Science, Purdue Univ. (Mikhail J. Atallah, advisor)

M.S. · 1985 · Computer Science, Purdue Univ.

B.A. · 1983 · Mathematics and Computer Science, Calvin Univ.

[nom]

July ’19 to present · Distinguished Professor, Dept. of Computer Science

Univ. of California, Irvine

March ’10 to present · Technical Director, Center for Algorithms and Theory of Computation

Univ. of California, Irvine

April ’07 to June ’19 · Chancellor’s Professor, Dept. of Computer Science

Univ. of California, Irvine

July ’12 to June ’13 · Chair, Dept. of Computer Science

Univ. of California, Irvine

October ’06 to June ’12 · Assoc. Dean for Faculty Dev., Bren School of Info. and Comp. Sci.

Univ. of California, Irvine

July ’01 to March ’07 · Professor, Dept. of Computer Science

Univ. of California, Irvine

Fall ’00 · Visiting Professor of Computer Science

Brown Univ.

July ’96 to June ’02 · Professor of Computer Science (on leave, from July ’01)

Johns Hopkins Univ.

July ’92 to June ’96 · Associate Professor of Computer Science

Johns Hopkins Univ.

Spring ’94 · Visiting Associate Professor of Computer Science

Univ. of Illinois, Urbana-Champaign

July ’87 to June ’92 · Assistant Professor of Computer Science

Johns Hopkins Univ.

Aug. ’83 to June ’87 · Teaching Assistant, Research Assistant

Purdue Univ.

Summer ’83 · Summer intern

Argonne National Laboratory

RESEARCH INTERESTS

Algorithm and data structure design

Networking and parallel and distributed computing

Computer security and information assurance and privacy

Foundations of artificial intelligence, machine learning, and computer vision

Databases and high-performance data management

User interfaces, information visualization, and graph drawing

Computational geometry and computer graphics

1

PRIZES, HONORS, AND AWARDS

• Compere Loveless Fellowship in Computer Sciences, Purdue Univ., 1985
• Research Initiation Award, National Science Foundation, 1988
• Oraculum Award for Excellence in Teaching, Johns Hopkins, 1993, 1994, 1995
• ACM Recognition of Service Award, 1996
• Robert B. Pond, Sr. Award for Excellence in Undergraduate Teaching, Johns Hopkins, 1998
• Elected Senior Member, the Institute of Electrical and Electronics Engineers (IEEE), 1999
• Spirit of Technology Transition Award, DARPA Dynamic Coalitions Program, 2002
• Brown Univ. Award for Technological Innovation (with Roberto Tamassia, Nikos Triandopou- los, Danfeng Yao, and D. Ellis), 2006
• ACM Distinguished Scientist, 2006
• Edward J. McCluskey Technical Achievement Award, IEEE Computer Society, “for out- standing contributions to the design of parallel and distributed algorithms for fundamental combinatorial and geometric problems,” 2007
• Fulbright Scholar, for senior specialist service to University of Aarhus, Denmark, 2007
• Fellow of the San Diego Supercomputer Center, 2007
• Fellow of the American Association for the Advancement of Science (AAAS), “for distin- guished contributions to parallel and distributed algorithms for combinatorial and geometric problems, and excellence in teaching, academic and [nom] service, and textbook writing,” 2007
• Named as Chancellor’s Professor, for “demonstrated unusual academic merit and whose continued promise for scholarly achievement is unusually high,” Univ. of California, Irvine, 2007
• Fellow of the Institute of Electrical and Electronics Engineers (IEEE), “for contributions to parallel and distributed algorithms for combinatorial and geometric problems,” 2009
• Fellow of the ACM, “for contributions to data structures and algorithms for combinatorial and geometric problems,” 2009
• ICS Dean’s Award for Research, “for contributions in the area of parallel and distributed algorithms,” 2014
• Chancellor’s Award for Excellence in Fostering Undergraduate Research, Univ. of California, Irvine, 2016
• Faculty Mentor of the Month, Undergraduate Research Opportunities Program (UROP), Univ. of California, Irvine, April 2016
• Elected as a foreign member, Royal Danish Academy of Sciences and Letters, April 2018
• Named as Distinguished Professor, for achieving “the highest levels of scholarship” over the course of a career and having “earned national and international level distinctions and honors of the highest level,” Univ. of California, Irvine, 2019
• Recipient, Alejandro López-Ortiz Best Paper Award, for “Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent,” 18th Algorithms and Data Structures Symposium, 2023.
• Recipient, SIGMOD Research Highlight Award, for “History-Independent Dynamic Partition- ing: Operation-Order Privacy in Ordered Data Structures,” 2024. This award recognizes research projects that exemplify core database research and that address an important problem, represent a definitive milestone in solving the problem, and have the potential of significant impact.
• Distinguished Science Alumni Award, Purdue University, 2025.

2

PUBLICATIONS

Google Scholar Citation Statistics:

• Total citations: over 19,000
• H-index (top H publications with at least H citations): 77 Patents and Patent Applications:

P-1. Michael T. Goodrich and Roberto Tamassia, “An Efficient Dynamic Distributed

Cryptographic Accumulator,” International Patent Application Pub. No. WO 2002/39212, May 16, 2002.

P-2. Giuseppe Ateniese, Breno de Medeiros, and Michael T. Goodrich, “Intermediated Delivery

Scheme for Asymmetric Fair Exchange of Electronic Items,” U.S. Patent Application Pub.

No. US 2004/0073790, April 15, 2004.

P-3. Michael T. Goodrich and Roberto Tamassia, “Efficient Authenticated Dictionaries with Skip Lists and Commutative Hashing,” U.S. Patent No. 7,257,711, August 14, 2007.

P-4. Jacob W. Green, John L. Schultz, Yair Amir, and Michael T. Goodrich, “High Refresh- Rate Retrieval of Freshly Published Content using Distributed Crawling,” U.S. Patent No.

7,299,219, November 20, 2007.

P-5. Roberto Tamassia, Michael T. Goodrich, and Nikos Triandopoulos, “Super-efficient

Verification of Dynamic Outsourced Databases,” International Patent Application Pub.

No. WO 2008/014002, January 31, 2008.

P-6. Michael T. Goodrich, Roberto Tamassia, and Nikos Triandopoulos, “Load-balanced

Distributred Authentication Structures,” International Patent Application Pub. No. WO

2008/014004 (U.S. PCT/US2007/017046), January 31, 2008.

P-7. Michael T. Goodrich, Danfeng Yao, and Roberto Tamassia, “Notarized Federated Identity

Management,” International Patent Application Pub. No. WO 2008/020991, February 21, 2008.

P-8. Roberto Tamassia, Michael T. Goodrich, Nikos Triandopoulos, and Charalampos

Papmanthou, “Authentication for Operations over an Outsourced File System Stored by an Untrusted Unit,” International Patent Application Pub. No. WO 2008/147400, December

4, 2008.

P-9. Rasmus Tamstorf, Michael T. Goodrich, David Eppstein, “Attribute Transfer Between

Computer Models Including Identifying Isomorphic Regions in Polygonal Meshes,”

U.S. Patent No. 8,681,145, March 25, 2014.

P-10. Nikos Triandopoulos, Michael T. Goodrich, Duy Nguyen, Olga Ohrimenko, Charalampos

Papmanthou, Roberto Tamassia, Cristina V. Lopes, “Techniques for Verifying Search

Results Over a Distributed Collection,” U.S. Patent No. 9,152,716, October 6, 2015.

Books and Monographs:

B-1. Michael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, John

Wiley and Sons, Inc., 1998.

B-2. Michael T. Goodrich and Catherine C. McGeoch, eds., Algorithm Engineering and Experimentation, Lecture Notes in Computer Science (LNCS), Vol. 1619, Springer, 1999.

B-3. Michael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, Second Edition, John Wiley and Sons, Inc., 2001.

B-4. Michael T. Goodrich and Roberto Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley and Sons, Inc., 2002.

3

B-5. Michael T. Goodrich and Stephen G. Kobourov, eds., 10th Int. Symp. on Graph Drawing

(GD), Lecture Notes in Computer Science, Vol. 2528, Springer, 2002.

B-6. Michael T. Goodrich, Roberto Tamassia, and David Mount, Data Structures and Algorithms in C++, John Wiley and Sons, Inc., 2004.

B-7. Michael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, Third

Edition, John Wiley and Sons, Inc., 2004.

B-8. Michael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, Fourth Edition, John Wiley and Sons, Inc., 2006.

B-9. Michael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, Fifth

Edition, John Wiley and Sons, Inc., 2011.

B-10. Michael T. Goodrich and Roberto Tamassia, Introduction to Computer Security, Addison- Wesley, 2011.

B-11. Michael T. Goodrich, Roberto Tamassia, and David Mount, Data Structures and Algorithms in C++, Second Edition, John Wiley and Sons, Inc., 2011.

B-12. Michael T. Goodrich, Roberto Tamassia, and Michael Goldwasser, Data Structures and Algorithms in Python, John Wiley and Sons, Inc., 2013.

B-13. Michael T. Goodrich, Roberto Tamassia, and Michael Goldwasser, Data Structures and Algorithms in Java, Sixth Edition, John Wiley and Sons, Inc., 2014.

B-14. Michael T. Goodrich and Roberto Tamassia, Algorithm Design and Applications, Wiley, 2015.

B-15. Michael T. Goodrich and Roberto Tamassia, Algorithm Design and Applications, interactive e-book, [lien]

zyBooks (a division of Wiley), 2022.

Book Chapters:

Ch-1. Mikhail J. Atallah and Michael T. Goodrich, “Deterministic Parallel Computational

Geometry,” in Synthesis of Parallel Algorithms, J.H. Reif, ed., Morgan Kaufmann, 497–

536, 1993.

Ch-2. Michael T. Goodrich, “The Grand Challenges of Geometric Computing,” in Developing a Computer Science Agenda for High-Performance Computing, Uzi Vishkin, ed., ACM Press, 64–68, 1994.

Ch-3. Michael T. Goodrich, “Parallel Algorithms in Geometry,” CRC Handbook of Discrete and Computational Geometry, J.E. Goodman and J. O’Rourke, eds., CRC Press, Inc., 669–682, 1997.

Ch-4. Michael T. Goodrich and Kumar Ramaiyer, “Geometric Data Structures,” Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, eds., Elsevier Science Publishing, 463–489, 2000.

Ch-5. Michael T. Goodrich and Roberto Tamassia, “Simplified Analyses of Randomized

Algorithms for Searching, Sorting, and Selection,” Handbook of Randomized Computing, S. Rajasekaran, P.M. Pardalos, J.H. Reif, and J.D.P. Rolim, eds., Kluwer Academic

Publishers, Vol. 1, 23–34, 2001.

Ch-6. Michael T. Goodrich, “Parallel Algorithms in Geometry,” Handbook of Discrete and Computational Geometry, Second Edition, J.E. Goodman and J. O’Rourke, eds., Chapman

& Hall/CRC Press, Inc., 953–967, 2004. (Revised version of Ch-3.)

Ch-7. Christian A. Duncan and Michael T. Goodrich, “Approximate Geometric Query

Structures,” Handbook of Data Structures and Applications, Chapman & Hall/CRC Press, Inc., 26-1–26-17, 2005.

4

Ch-8. Michael T. Goodrich, Roberto Tamassia, and Luca Vismara, “Data Structures in JDSL,”

Handbook of Data Structures and Applications, Chapman & Hall/CRC Press, Inc., 43-1–

43-22, 2005.

Ch-9. YounSun Cho, Lichun Bao and Michael T. Goodrich, “Secure Location-Based 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.

Ch-10. Michael T. Goodrich and Michael J. Nelson, “Distributed Peer-to-Peer Data Structures,”

Handbook of Parallel Computing: Models, Algorithms and Applications, R. Rajasekaran and J. Reif, eds., CRC Press, 17-1–17-17, 2008.

Ch-11. Christian A. Duncan and Michael T. Goodrich, “Planar Orthogonal and Polyline Drawing

Algorithms,” Handbook of Graph Drawing and Visualization, CRC Press, Inc., 223–246, 2013.

Ch-12. Michael T. Goodrich, Roberto Tamassia, and Luca Vismara, “Data Structures in JDSL,”

Handbook of Data Structures and Applications, 2nd edition, Chapman and Hall/CRC, Taylor & Francis, Inc., 43-1–43-22, 2018.

Journal Papers:

J-1. Mikhail J. Atallah and Michael T. Goodrich, “Efficient Parallel Solutions to Some Geometric

Problems,” Journal of Parallel and Distributed Computing, 3(4), 1986, 492–507.

J-2. Michael T. Goodrich, “Finding the Convex Hull of a Sorted Point Set in Parallel,”

Information Processing Letters, 26, 1987, 173–179.

J-3. Hossam A. ElGindy and Michael T. Goodrich, “Parallel Algorithms for Shortest Path

Problems in Polygons,” The Visual Computer, 3(6), 1988, 371–378.

J-4. Mikhail J. Atallah and Michael T. Goodrich, “Parallel Algorithms For Some Functions of Two Convex Polygons,” Algorithmica, 3, 1988, 535–548.

J-5. Mikhail J. Atallah, Richard Cole, and Michael T. Goodrich, “Cascading Divide-and- Conquer: A Technique for Designing Parallel Algorithms,” SIAM Journal on Computing, 18(3), 1989, 499–532.

J-6. Michael T. Goodrich, “Triangulating a Polygon in Parallel,” Journal of Algorithms, 10, 1989, 327–351.

J-7. Michael T. Goodrich and Mikhail J. Atallah, “On Performing Robust Order Statistics in Tree-Structured Dictionary Machines,” Journal of Parallel and Distributed Computing, 9(1), 1990, 69–76.

J-8. Michael T. Goodrich and Jack S. Snoeyink, “Stabbing Parallel Segments with a Convex

Polygon,” Computer Vision, Graphics and Image Processing, 49, 1990, 152–170.

J-9. John K. Johnstone and Michael T. Goodrich, “A Localized Method for Intersecting Plane

Algebraic Curve Segments,” The Visual Computer, 7(2–3), 1991, 60–71.

J-10. Michael T. Goodrich, “Intersecting Line Segments in Parallel with an Output-Sensitive

Number of Processors,” SIAM Journal on Computing, 20(4), 1991, 737–755.

J-11. Richard Cole and Michael T. Goodrich, “Optimal Parallel Algorithms for Point-Set and Polygon Problems,” Algorithmica, 7, 1992, 3–23.

J-12. Michael 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.

J-13. Michael T. Goodrich, Steven B. Shauck, and Sumanta Guha, “Parallel Methods for Visibility and Shortest Path Problems in Simple Polygons,” Algorithmica, 8, 1992, 461–

486, with addendum in Algorithmica, 9, 1993, 515–516.

5

J-14. Michael T. Goodrich, Colm Ó’Dúnlaing, and Chee Yap “Constructing the Voronoi Diagram of a Set of Line Segments in Parallel,” Algorithmica, 9, 1993, 128–141.

J-15. Michael T. Goodrich, “Constructing the Convex Hull of a Partially Sorted Set of Points,”

Computational Geometry: Theory and Applications, 2, 1993, 267–278.

J-16. Michael T. Goodrich, “Constructing Arrangements Optimally in Parallel,” Discrete and Computational Geometry, 9, 1993, 371–385.

J-17. Michael T. Goodrich, Mikhail J. Atallah, and Mark H. Overmars, “Output-Sensitive

Methods for Rectilinear Hidden Surface Removal,” Information and Computation, 107(1), 1993, 1–24.

J-18. Mikhail J. Atallah, Paul H. Callhan, and Michael T. Goodrich, “P-Complete Geometric

Problems,” Int. Journal of Computational Geometry & Applications, 3(4), 1993, 443–462.

J-19. Mikhail J. Atallah, Michael T. Goodrich, and S. Rao Kosaraju, “Parallel Algorithms for Evaluating Sequences of Set-Manipulation Operations,” Journal of the ACM, 41(6), 1994, 1049–1088.

J-20. Michael T. Goodrich, “Efficient Piecewise-Linear Function Approximation Using the Uniform Metric,” Discrete and Computational Geometry, 14, 1995, 445–462.

J-21. Hervé Brönnimann and Michael T. Goodrich, “Almost Optimal Set Covers in Finite VC- Dimension,” Discrete and Computational Geometry, 14, 1995, 463–479.

J-22. Michael T. Goodrich, “Planar Separators and Parallel Polygon Triangulation,” J. Computer and System Sciences, 51(3), 1995, 374–389.

J-23. Michael T. Goodrich, Mujtaba R. Ghouse, and Jonathan Bright, “Sweep Methods for Parallel Computational Geometry,” Algorithmica, 15(2), 1996, 126–153.

J-24. Michael T. Goodrich and S. Rao Kosaraju, “Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation,” Journal of the ACM, 43(2), 1996, 331–361.

J-25. Ashim Garg, Michael T. Goodrich, and Roberto Tamassia, “Planar Upward Tree Drawings with Optimal Area,” International Journal of Computational Geometry & Applications, 6(3), 1996, 333–356.

J-26. Mark H. Nodine, Michael T. Goodrich, and Jeffrey S. Vitter, “Blocking for External Graph

Searching,” Algorithmica, 16(2), 1996, 181–214.

J-27. Richard Cole, Michael T. Goodrich, Colm Ó Dúnlaing, “A Nearly Optimal Deterministic

Parallel Voronoi Diagram Algorithm,” Algorithmica, 16, 1996, 569–617.

J-28. Gautam Das and Michael T. Goodrich, “On the Complexity of Optimization Problems for 3-Dimensional Convex Polyhedra and Decision Trees,” Computational Geometry: Theory and Applications, 8, 1997, 123–137.

J-29. Michael T. Goodrich and Roberto Tamassia, “Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations,” J. Algorithms, 23, 1997, 51–73.

J-30. Mujtaba R. Ghouse and Michael T. Goodrich, “Fast Randomized Parallel Methods for Planar Convex Hull Construction,” Computational Geometry: Theory and Applications, 7, 1997, 219–235.

J-31. L. Paul Chew, Michael T. Goodrich, Daniel P. Huttenlocher, Klara Kedem, Jon M.

Kleinberg, and Dina Kravets, “Geometric Pattern Matching under Euclidean Motion,”

Computational Geometry: Theory and Applications, 7, 1997, 113-124.

J-32. Michael T. Goodrich and Edgar A. Ramos, “Bounded-Independence Derandomization of Geometric Partitioning with Applications to Parallel Fixed-Dimensional Linear

Programming,” Discrete & Computational Geometry, 18(4), 1997, 397–420.

6

J-33. Michael T. Goodrich, “An Improved Ray Shooting Method for Constructive Solid Geometry

Models via Tree Contraction,” International Journal of Computational Geometry &

Applications, 8(1), 1998, 1–23.

J-34. Gill Barequet, Amy J. Briggs, Matthew T. Dickerson, and Michael T. Goodrich, “Offset-Polygon Annulus Placement Problems,” Computational Geometry: Theory and Applications, 11(3–4), 1998–99, 125–141.

J-35. Michael T. Goodrich and Roberto Tamassia, “Dynamic Trees and Dynamic Point Location,”

SIAM J. Comput., 28(2), 1999, 612–636.

J-36. Gill Barequet, Stina S. Bridgeman, Christian A. Duncan, Michael T. Goodrich, and Roberto Tamassia, “GeomNet: Geometric Computing Over the Internet,” IEEE Internet

Computing, 3(2), 1999, 21–29.

J-37. Michael T. Goodrich, Joseph S.B. Mitchell, and Mark W. Orletsky, “Approximate

Geometric Pattern Matching Under Rigid Motion,” IEEE Trans. on Pattern Analysis and Machine Intelligence, 21(4), 1999, 371–379.

J-38. Michael T. Goodrich, “Communication-Efficient Parallel Sorting,” SIAM Journal on Computing, 29(2), 1999, 416–432.

J-39. Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov, “Balanced Aspect Ratio

Trees and Their Use for Drawing Very Large Graphs,” Journal of Graph Algorithms and Applications, 4(3), 2000, 19–46. Also available at [lien]

J-40. Michael T. Goodrich and Christopher G. Wagner, “A Framework for Drawing Planar

Graphs with Curves and Polylines,” Journal of Algorithms, 37, 2000, 399–421.

J-41. Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov, “Balanced Aspect Ratio

Trees: Combining the Benefits of k-D Trees and Octrees,” J. Algorithms, 38, 2001, 303–333.

J-42. Gill Barequet, Matthew T. Dickerson, and Michael T. Goodrich, “Voronoi Diagrams for Polygon-Offset Distance Functions,” Discrete and Computational Geometry, 25(2), 2001, 271–291.

J-43. C.C. Cheng, Christian A. Duncan, Michael T. Goodrich, and Stephen G. Kobourov, “Drawing Planar Graphs with Circular Arcs,” Discrete and Computational Geometry, 25(3), 2001, 405–418.

J-44. Nancy M. Amato, Michael T. Goodrich, and Edgar A. Ramos, “A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time,” Discrete and Computational Geometry, 26(2), 2001, 245–265.

J-45. Roberto Tamassia, Michael T. Goodrich, Luca Vismara, Mark Handy, Galina Shubina, Robert Cohen, Benoı̂t Hudson, Ryan S. Baker, Natasha Gelfand, and Ulrik Brandes, “JDSL:

The Data Structures Library in Java,” Dr. Dobbs Journal, 323, 2001, 21–31.

J-46. Gill Barequet, Danny Z. Chen, Ovidiu Daescu, Michael T. Goodrich, and Jack S.

Snoeyink, “Efficiently Approximating Polygonal Paths in Three and Higher Dimensions,”

Algorithmica, 33(2), 2002, 150–167.

J-47. Timothy M. Chan, Michael T. Goodrich, S. Rao Kosaraju, and Roberto Tamassia, “Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings,”

Computational Geometry: Theory and Applications, 23(2), 2002, 153–162.

J-48. Christian A. Duncan, Michael T. Goodrich, and Stephen G. Kobourov, “Planarity- Preserving Clustering and Embedding for Large Planar Graphs,” Computational Geometry:

Theory and Applications, 24(2), 2003, 95–114.

J-49. Adam L. Buchsbaum and Michael T. Goodrich, “Three-Dimensional Layers of Maxima,”

Algorithmica, 39, 2004, 275–286.

7

J-50. Gill Barequet, Michael T. Goodrich, and Chris Riley, “Drawing Graphs with Large Vertices and Thick Edges,” J. of Graph Algorithms and Applications (JGAA), 8(1), 2004, 3–20.

J-51. Gill Barequet, Michael T. Goodrich, Aya Levi-Steiner, and Dvir Steiner, “Contour

Interpolation by Straight Skeletons,” Graphical Models (GM), 66(4), 2004, 245–260.

J-52. Pawel Gajer, Michael T. Goodrich, and Stephen G. Kobourov, “A Multi-Dimensional

Approach to Force-Directed Layouts of Large Graphs,” Computational Geometry: Theory and Applications, 29(1), 3–18, 2004.

J-53. Gill Barequet, Prosenjit Bose, Matthew T. Dickerson, and Michael T. Goodrich, “Optimizing a Constrained Convex Polygonal Annulus,” J. of Discrete Algorithms (JDA), 3(1), 1–26, 2005.

J-54. Amitabha Bagchi, Adam L. Buchsbaum, and Michael T. Goodrich, “Biased Skip Lists,”

Algorithmica, 42(1), 31–48, 2005.

J-55. Matthew T. Dickerson, David Eppstein, Michael T. Goodrich, Jeremy Yu Meng, “Confluent

Drawings: Visualizing Non-planar Diagrams in a Planar Way,” J. of Graph Algorithms and Applications (JGAA), 9(1), 31–52, 2005.

J-56. Amitabha Bagchi, Amitabh Chaudhary, Michael T. Goodrich, Chen Li, and Michal

Shmueli-Scheuer, “Achieving Communication Efficiency through Push-Pull Partitioning of Semantic Spaces to Disseminate Dynamic Information,” IEEE Trans. on Knowledge and Data Engineering (TKDE), 18(10), 1352–1367, 2006.

J-57. David Eppstein, Michael T. Goodrich, and Jeremy Yu Meng, “Confluent Layered

Drawings,” Algorithmica, 47(4), 439–452, 2007.

J-58. Amitabha Bagchi, Amitabh Chaudhary, David Eppstein, and Michael T. Goodrich, “Deterministic Sampling and Range Counting in Geometric Data Streams,” ACM

Transactions on Algorithms, 3(2), Article 16, 2007, 18 pages.

J-59. David Eppstein, Michael T. Goodrich, and Daniel S. Hirschberg, “Improved Combinatorial

Group Testing Algorithms for Real-World Problem Sizes,” SIAM Journal on Computing, 36(5), 1360–1375, 2007.

J-60. David Eppstein, Michael T. Goodrich, and Jonathan Z. Sun, “Skip Quadtrees: Dynamic

Data Structures for Multidimensional Point Sets,” Int. Journal on Computational Geometry and Applications, 18(1/2), 131–160, 2008.

J-61. Michael T. Goodrich, “Probabilistic Packet Marking for Large-Scale IP Traceback,”

IEEE/ACM Transactions on Networking, 16(1), 15–24, 2008.

J-62. Michael T. Goodrich and Daniel S. Hirschberg, “Improved Adaptive Group Testing

Algorithms with Applications to Multiple Access Channels and Dead Sensor Diagnosis,”

Journal of Combinatorial Optimization, 15(1), 95–121, 2008.

J-63. Michael T. Goodrich, Roberto Tamassia, and Danfeng Yao, “Notarized Federated ID

Management and Authentication,” Journal of Computer Security, 16(4), 399–418, 2008.

J-64. Michael T. Goodrich, “Pipelined Algorithms to Detect Cheating in Long-Term Grid

Computations,” Theoretical Computer Science, 408, 199–207, 2008.

J-65. David Eppstein, Michael T. Goodrich, Ethan Kim, and Rasmus Tamstorf, “Motorcycle

Graphs: Canonical Quad Mesh Partitioning,” Computer Graphics Forum, special issue on papers from 6th European Symp. on Geometry Processing (SGP), 27(6), 1477–1486, 2008.

J-66. Michael T. Goodrich, Michael Sirivianos, John Solis, Claudio Soriente, Gene Tsudik, Ersin

Uzun, “Using Audio in Secure Device Pairing,” Int. J. Security and Networks, 4(1/2), 57–68, 2009.

8

J-67. Michael T. Goodrich, “On the Algorithmic Complexity of the Mastermind Game with Black-Peg Results,” Information Processing Letters, 109, 675–678, 2009.

J-68. David Eppstein, Michael T. Goodrich, Ethan Kim, and Rasmus Tamstorf, “Approximate

Topological Matching of Quad Meshes,” The Visual Computer, 25(8), 771–783, 2009.

J-69. David Eppstein and Michael T. Goodrich, “Succinct Greedy Geometric Routing Using Hyperbolic Geometry,” IEEE Transactions on Computers, 60(11), 1571–1580, 2011. Posted online Dec. 2010, IEEE Computer Society Digital Library.

J-70. David Eppstein, Michael T. Goodrich, and Darren Strash, “Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Edge Crossings,” SIAM Journal on Computing, 39(8), 3814–3829, 2010.

J-71. Michael T. Goodrich, Roberto Tamassia, and Nikos Triandopoulos, “Efficient Authenticated

Data Structures for Graph Connectivity and Geometric Search Problems,” Algorithmica, 60(3), 505–552, 2011.

J-72. David Eppstein and Michael T. Goodrich, “Straggler Identification in Round-Trip Data

Streams via Newton’s Identities and Invertible Bloom Filters,” IEEE Transactions on Knowledge and Data Engineering (TKDE), 23(2), 297–306, 2011.

J-73. Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov, “Planar Drawings of Higher-Genus Graphs,” Journal of Graph Algorithms and Applications, 15(1), 7–32, 2011.

J-74. Matthew T. Dickerson, Michael T. Goodrich, Thomas D. Dickerson, and Ying Daisy

Zhuo “Round-Trip Voronoi Diagrams and Doubling Density in Geographic Networks,”

Transactions on Computational Science, M.L. Gavrilova et al. (Eds.), Vol. 14, LNCS 6970, 211–238, 2011.

J-75. Michael T. Goodrich, “Randomized Shellsort: A Simple Data-Oblivious Sorting

Algorithm,” Journal of the ACM, 58(6), Article No. 27, 2011.

J-76. Christian A. Duncan, David Eppstein, Michael T. Goodrich, Stephen G. Kobourov, and Martin Nöllenburg, “Lombardi Drawings of Graphs,” Journal of Graph Algorithms and Applications (JGAA), 16(1), 85–108, 2012.

J-77. Erin Wolf-Chambers, David Eppstein, Michael T. Goodrich, and Maarten Löffler, “Drawing

Graphs in the Plane with a Prescribed Outer Face and Polynomial Area,” Journal of Graph

Algorithms and Applications (JGAA), 16(2), 243–259, 2012.

J-78. Michael T. Goodrich, Duy Nguyen, Olga Ohrimenko, Charalmpos Papamanthou, Roberto

Tamassia, Nikos Triandopoulos, and Cristina V. Lopes, “Efficient Verification of Web- Content Searching Through Authenticated Web Crawlers,” Proc. VLDB, 5(10):920-931, 2012.

J-79. David Eppstein, Michael T. Goodrich, Darren Strash, and Lowell Trott, “Extended

Dynamic Subgraph Statistics Using h-Index Parameterized Data Structures,” Theoretical

Computer Science, 447, 44–52, 2012.

J-80. Michael T. Goodrich, “Learning Character Strings via Mastermind Queries, With a Case

Study Involving mtDNA,” IEEE Transactions on Information Theory, 58(11), 6726–6736, 2012.

J-81. Arthur U. Asuncion and Michael T. Goodrich, “Nonadaptive Mastermind Algorithms for String and Vector Databases, with Case Studies,” IEEE Transactions on Knowledge and Data Engineering (TKDE), 25(1), 131–144, 2013.

J-82. Christian A. Duncan, David Eppstein, Michael T. Goodrich, Stephen G. Kobourov, and Martin Nöllenburg, “Drawing Trees with Perfect Angular Resolution and Polynomial Area,”

Discrete & Computational Geometry, 49(2), 157–182, 2013.

9

J-83. Elaine Angelino, Michael T. Goodrich, Michael Mitzenmacher and Justin Thaler, “External

Memory Multimaps,” Algorithmica, 67(1), 23–48, 2013.

J-84. David Eppstein, Michael T. Goodrich, Maarten Löffler, Darren Strash and Lowell Trott, “Category-Based Routing in Social Networks: Membership Dimension and the Small-World

Phenomenon,” Theoretical Computer Science, 514, 96–104, 2013.

J-85. Michael T. Goodrich, “Spin-the-bottle Sort and Annealing Sort: Oblivious Sorting via Round-robin Random Comparisons,” Algorithmica, 68(4), 835–858, 2014.

J-86. Michael J. Bannister, William E. Devanny, David Eppstein, and Michael T. Goodrich, “The Galois Complexity of Graph Drawing: Why Numerical Solutions are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings,” Journal of Graph Algorithms and Applications, 19(2), 619–656, 2015.

J-87. Christian Duncan, David Eppstein, Michael T. Goodrich, Stephen G. Kobourov and Maarten Löffler, “Planar and Poly-Arc Lombardi Drawings,” Journal of Computational

Geometry (JoCG), 9(1), 328–355, 2018.

J-88. Gill Barequet, David Eppstein, Michael T. Goodrich, and Nil Mamano, “Stable-Matching

Voronoi Diagrams: Combinatorial Complexity and Algorithms,” Journal of Computational

Geometry (JoCG), 11(1), 26–59, 2020.

J-89. Michael T. Goodrich, Zhanhang Marco Liang, and Shuang Zhao, “Inverse-Rendering Based

Analysis of the Fine Illumination Effects in the Salvator Mundi,” Leonardo, 53(4), 380–386, 2020.

J-90. William E. Devanny, Michael T. Goodrich, Sandy Irani, “A Competitive Analysis for the Start-Gap Algorithm for Online Memory Wear Leveling,” Information Processing Letters, 116, 106042, 2021.

J-91. Gill Barequet, Minati De, and Michael T. Goodrich, “Convex-Straight-Skeleton Voronoi

Diagrams for Segments and Convex Polygons,” Algorithmica, 83(7), 2245–2272, 2021.

J-92. Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, and Siddharth Gupta, “C- Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width,”

Algorithmica, 83(8), 2471–2502, 2021.

J-93. Michael Shindler, Michael T. Goodrich, Ofek Gila, Michael B. Dillencourt, “Beyond Big O:

Teaching Experimental Algorithmics,” Journal of Computing Sciences in Colleges, 37(10), 23–36, 2022.

J-94. Pratibha Choudhary, Michael T. Goodrich, Siddharth Gupta, Hadi Khodabandeh, Pedro

Matias, and Venkatesh Raman, “Improved Kernels for Tracking Paths,” Information

Processing Letters, 181, 106360, 1–11, 2023.

J-95. Michael B. Dillencourt and Michael T. Goodrich, “Simplified Chernoff Bounds with Powers-of-Two Probabilities,” Information Processing Letters, 182, 106397, 1–7, 2023.

J-96. Shanshan Han, Vishal Chakraborty, Michael T. Goodrich, Sharad Mehrotra, Shantanu

Sharma, “VEIL: A Storage and Communication Efficient Volume-Hiding Algorithm,” Proc.

ACM Management of Data (SIGMOD), 1(4), 265:1-265:27, 2023.

J-97. Michael B. Dillencourt, Michael T. Goodrich, and Michael Mitzenmacher, “Leveraging

Parameterized Chernoff Bounds for Simplified Algorithm Analyses,” Information Processing

Letters, 187, 106516, 1–7, 2025.

J-98. Michael T. Goodrich, “A Lower Bound for the Quickhull Convex Hull Algorithm that

Disproves the Quickhull Precision Conjecture,” Information Processing Letters, 189, 106558, 1–7, 2025.

10

J-99. Michael A. Bender, Martin Farach-Colton, Michael T. Goodrich, and Hanna Komlos, “History-Independent Dynamic Partitioning: Operation-Order Privacy in Ordered Data

Structures,” ACM SIGMOD Record, 54(1), 17–26, 2025.

J-100. Ofek Gila, Michael T. Goodrich, and Robert E. Tarjan, “Zip-zip Trees: Making Zip Trees

More Balanced, Biased, Compact, or Persistent,” Algorithmica, accepted.

J-101. Michael A. Bender, Martin Farach-Colton, Michael T. Goodrich, and Hanna Komlos, “History-Independent Dynamic Partitioning with Applications to B-Trees, Skip Lists and Fusion Trees,” ACM Transactions on Database Systems, accepted.

J-102. Alvin Chiu, Thomas Depian, David Eppstein, Michael T. Goodrich, and Martin Nöllenburg, “Visualizing Treewidth,” Journal of Graph Algorithms and Applications, accepted.

Papers in Proceedings:

C-1. Mikhail J. Atallah and Michael T. Goodrich, “Efficient Parallel Solutions to Geometric

Problems,” 1985 IEEE Int. Conf. on Parallel Processing (ICPP), 411–417. ( Proceedings version of J-1.)

C-2. Francine Berman, Michael T. Goodrich, Charles Koelbel, W.J. Robison III, and Karen

Showell, “Prep-P: A Mapping Preprocessor for CHiP Computers,” 1985 IEEE Int. Conf.

on Parallel Processing, 731–733.

C-3. Mikhail J. Atallah and Michael T. Goodrich, “Parallel Algorithms For Some Functions of Two Convex Polygons,” 24th Allerton Conf. on Communication, Control and Computing, 1986, 758–767. ( Proceedings version of J-4.)

C-4. Mikhail J. Atallah and Michael T. Goodrich, “Efficient Plane Sweeping in Parallel,” 2nd

ACM Symp. on Computational Geometry (SoCG), 1986, 216–225.

C-5. Michael T. Goodrich, “A Polygonal Approach to Hidden-Line Elimination,” 25th Allerton

Conf. on Communication, Control, and Computing, 1987, 849–858. ( Proceedings version of J- 12.)

C-6. Mikhail J. Atallah, Richard Cole, and Michael T. Goodrich, “Cascading Divide-and- Conquer: A Technique for Designing Parallel Algorithms,” 28th IEEE Symp. on Foundations of Computer Science (FOCS), 1987, 151-160. ( Proceedings version of J-5.)

C-7. Mikhail J. Atallah, Michael T. Goodrich, and S. Rao Kosaraju, “Parallel Algorithms for Evaluating Sequences of Set-Manipulation Operations,” 3rd Aegean Workshop on Computing (AWOC), Lecture Notes in Computer Science (LNCS): 319, Springer, 1988, 1–10. ( Proceedings version of J-19.)

C-8. Richard Cole and Michael T. Goodrich, “Optimal Parallel Algorithms for Polygon and Point-Set Problems,” 4th ACM Symp. on Computational Geometry (SoCG), 1988, 201–

210. ( Proceedings version of J-11.)

C-9. Michael T. Goodrich, “Intersecting Line Segments in Parallel with an Output-Sensitive

Number of Processors,” 1989 ACM Symp. on Parallel Algorithms and Architectures

(SPAA), 127–137. ( Proceedings version of J-10.)

C-10. Michael T. Goodrich and S. Rao Kosaraju, “Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation,” 30th IEEE Symp. on Foundations of Computer

Science (FOCS), 1989, 190–195. ( Proceedings version of J-24.)

C-11. Michael T. Goodrich, Colm Ó’Dúnlaing, and Chee Yap “Constructing the Voronoi Diagram of a Set of Line Segments in Parallel,” Lecture Notes in Computer Science 382, Algorithms and Data Structures (WADS), Springer, 1989, 12–23. ( Proceedings version of J-14.)

11

C-12. Michael T. Goodrich and Jack S. Snoeyink, “Stabbing Parallel Segments with a Convex

Polygon,” Lecture Notes in Computer Science 382, Algorithms and Data Structures

(WADS), Springer, 1989, 231–242. ( Proceedings version of J-8.)

C-13. John K. Johnstone and Michael T. Goodrich, “A Localized Method for Intersecting Plane

Algebraic Curve Segments,” New Advances in Computer Graphics: Proc. of Computer

Graphics International ’89, R.A. Earnshaw, B. Wyvel, eds., Springer, 1989, 165–181.

( Proceedings version of J-9.)

C-14. Mikhail J. Atallah, Paul H. Callhan, and Michael T. Goodrich, “P-Complete Geometric

Problems,” 2nd ACM Symp. on Parallel Algorithms and Architectures (SPAA), 1990, 317–

326. ( Proceedings version of J-18.)

C-15. Richard Cole, Michael T. Goodrich, Colm Ó Dúnlaing, “Merging Free Trees in Parallel for Efficient Voronoi Diagram Construction”, 17th Int. Conf. on Automata, Languages, and Programming (ICALP), 1990, 432–445. ( Proceedings version of J-27.)

C-16. Michael T. Goodrich, Mikhail J. Atallah, and Mark H. Overmars, “An Input-Size/Output- Size Trade-Off in the Time-Complexity of Rectilinear Hidden-Surface Removal”, 17th Int.

Conf. on Automata, Languages, and Programming (ICALP), 1990, 689–702. ( Proceedings version of J-17.)

C-17. Michael T. Goodrich, Mujtaba R. Ghouse, and Jonathan Bright, “Generalized Sweep

Methods for Parallel Computational Geometry,” 2nd ACM Symp. on Parallel Algorithms and Architectures (SPAA), 1990, 280–289. ( Proceedings version of J-23.)

C-18. Michael T. Goodrich, “Applying Parallel Processing Techniques to Classification Problems in Constructive Solid Geometry,” 1st ACM-SIAM Symp. on Discrete Algorithms (SODA), 1990, 118–128. ( Proceedings version of J-33.)

C-19. Michael T. Goodrich, Steven B. Shauck, and Sumanta Guha, “Parallel Methods for Visibility and Shortest Path Problems in Simple Polygons,” 6th ACM Symp. on Computational Geometry (SoCG), 1990, 73–82. ( Proceedings version of J-13.)

C-20. Mujtaba R. Ghouse and Michael T. Goodrich, “In-Place Techniques for Parallel Convex

Hull Algorithms,” 3rd ACM Symp. on Parallel Algorithms and Architectures (SPAA), 1991, 192–203. ( Proceedings version of J-30.)

C-21. Michael T. Goodrich, “Constructing Arrangements Optimally in Parallel,” 3rd ACM Symp.

on Parallel Algorithms and Architectures (SPAA), 1991, 169–179. ( Proceedings version of J- 16.)

C-22. Michael T. Goodrich and Roberto Tamassia, “Dynamic Trees and Dynamic Point Location,”

23rd ACM Symp. on Theory of Computing (STOC), 1991, 523–533. ( Proceedings version of J- 35.)

C-23. Michael T. Goodrich, “Using Approximation Algorithms to Design Parallel Algorithms that

May Ignore Processor Allocation,” 32nd IEEE Symp. on Foundations of Computer Science

(FOCS), 1991, 711–722.

C-24. Michael T. Goodrich, “Planar Separators and Parallel Polygon Triangulation,” 24th ACM

Symp. on Theory of Computing (STOC), 1992, 507–516. ( Proceedings version of J-22.)

C-25. Michael T. Goodrich, Yossi Matias, Uzi Vishkin, “Approximate Parallel Prefix Computation and Its Applications,” 7th IEEE Int. Parallel Processing Symp (IPPS), 1993, 318–325.

C-26. Mujtaba R. Ghouse and Michael T. Goodrich, “Experimental Evidence for the Power of Random Sampling in Practical Parallel Algorithms,” 7th IEEE Int. Parallel Processing

Symp (IPPS), 1993, 549–556.

12

C-27. L. Paul Chew, Michael T. Goodrich, Daniel P. Huttenlocher, Klara Kedem, Jon M.

Kleinberg, and Dina Kravets, “Geometric Pattern Matching under Euclidean Motion,” 5th

Canadian Conf. on Computational Geometry (CCCG), 1993, 151–156. ( Proceedings version of J-31.)

C-28. Michael T. Goodrich, “Geometric Partitioning Made Easier, Even in Parallel,” 9th ACM

Symp. on Computational Geometry (SoCG), 1993, 73–82.

C-29. Michael T. Goodrich and Roberto Tamassia, “Dynamic Ray Shooting and Shortest Paths via Balanced Geodesic Triangulations,” 9th ACM Symp. on Computational Geometry

(SoCG), 1993, 318–327. ( Proceedings version of J-29.)

C-30. Ashim Garg, Michael T. Goodrich, and Roberto Tamassia, “Area-Efficient Upward

Tree Drawings,” 9th ACM Symp. on Computational Geometry (SoCG), 1993, 359–368.

( Proceedings version of J-25.)

C-31. Mark H. Nodine, Michael T. Goodrich, and Jeffrey S. Vitter, “Blocking for External Graph

Searching,” 12th ACM Symp. on Principles of Database Systems (PODS), 1993, 222–232.

( Proceedings version of J-26.)

C-32. Esther M. Arkin, Michael T. Goodrich, Joseph S.B. Mitchell, David Mount, and Steven

S. Skiena, “Point Probe Decision Trees for Geometric Concept Classes,” Lecture Notes in Computer Science 709: Algorithms and Data Structures (WADS), Springer, 1993, 95–106.

C-33. Michael T. Goodrich, Jyh-Jong Tsay, Darren E. Vengroff, and Jeffrey S. Vitter, “External- Memory Computational Geometry,” 34th IEEE Symp. on Foundations of Computer Science

(FOCS), 1993, 714–723.

C-34. Michael T. Goodrich, Yossi Matias, and Uzi Vishkin, “Optimal Parallel Approximation

Algorithms for Prefix Sums and Integer Sorting,” 5th ACM-SIAM Symp. on Discrete

Algorithms (SODA), 1994, 241–250.

C-35. Hervé Brönnimann and Michael T. Goodrich, “Almost Optimal Set Covers in Finite

VC-Dimension,” 10th ACM Symp. on Computational Geometry (SoCG), 1994, 293–302.

( Proceedings version of J-21.)

C-36. Michael T. Goodrich, “Efficient Piecewise-Linear Function Approximation Using the Uniform Metric,” 10th ACM Symp. on Computational Geometry (SoCG), 1994, 322–331.

( Proceedings version of J-20.)

C-37. Mikhail J. Atallah, Michael T. Goodrich, and Kumar Ramaiyer, “Biased Finger Trees and Three-Dimensional Layers of Maxima,” 10th ACM Symp. on Computational Geometry

(SoCG), 1994, 150–159.

C-38. Michael T. Goodrich, Joseph S.B. Mitchell, and Mark W. Orletsky, “Practical Methods for Approximate Geometric Pattern Matching under Rigid Motions,” 10th ACM Symp. on Computational Geometry (SoCG), 1994, 103–112. ( Proceedings version of J-37.)

C-39. Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos, “Parallel Algorithms for Higher-Dimensional Convex Hulls,” 35th IEEE Symp. on Foundations of Computer Science

(FOCS), 1994, 683–694.

C-40. Paul J. Tanenbaum, Michael T. Goodrich, and Edward R. Scheinerman, “Characterization and Recognition of Point-Halfspace and Related Orders,” 2nd Int. Symp. on Graph Drawing

(GD), Lecture Notes in Computer Science 894, Springer, 1994, 234–245.

C-41. Yi-Jen Chiang, Michael T. Goodrich, Edward F. Grove, Roberto Tamassia, Darren E.

Vengroff, and Jeffrey S. Vitter, “External-Memory Graph Algorithms,” 6th ACM-SIAM

Symp. on Discrete Algorithms (SODA), 1995, 139–149.

13

C-42. Nancy M. Amato, Michael T. Goodrich, and Edgar A. Ramos, “Computing Faces in Segment and Simplex Arrangements,” 27th ACM Symp. on Theory of Computing (STOC), 1995, 672–682.

C-43. Paul H. Callhan, Michael T. Goodrich, and Kumar Ramaiyer, “Topology B-Trees and Their

Applications,” 1995 Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science 955, Springer, 381–392.

C-44. Gautam Das and Michael T. Goodrich, “On the Complexity of Approximating and Illuminating Three-Dimensional Convex Polyhedra,” 1995 Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science 955, Springer, 74–85.

( Proceedings version of J-28.)

C-45. Michael T. Goodrich, “Fixed-Dimensional Parallel Linear Programming via Relative ϵ- Approximations,” 7th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1996, 132–141.

( Proceedings version of J-32.)

C-46. Marek Chrobak, Michael T. Goodrich, and Roberto Tamassia, “Convex Drawings of Graphs in Two and Three Dimensions,” 12th ACM Symp. on Computational Geometry (SoCG), 1996, 319–328.

C-47. Michael T. Goodrich, “Communication-Efficient Parallel Sorting,” 28th ACM Symp. on Theory of Computing (STOC), 1996, 247–256. ( Proceedings version of J-38.)

C-48. Timothy M. Chan, Michael T. Goodrich, S. Rao Kosaraju, and Roberto Tamassia, “Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings,” 4th Int.

Symp. on Graph Drawing (GD), Lecture Notes in Computer Science 1190, Springer, 1996, 63–75. ( Proceedings version of J-47.)

C-49. Michael T. Goodrich, “Randomized Fully-Scalable BSP Techniques for Multi-Searching and Convex Hull Construction,” 8th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1997, 767–776.

C-50. Christian A. Duncan, Michael T. Goodrich, and Edgar A. Ramos, “Efficient Approximation and Optimization Algorithms for Computational Metrology,” 8th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1997, 121–130.

C-51. Michael T. Goodrich, Mark W. Orletsky, and Kumar Ramaiyer, “Methods for Achieving

Fast Query Times in Point Location Data Structures,” 8th ACM-SIAM Symp. on Discrete

Algorithms (SODA), 1997, 757–766.

C-52. Michael T. Goodrich, Leonidas J. Guibas, John Hershberger, Paul J. Tanenbaum, “Snap

Rounding Line Segments Efficiently in Two and Three Dimensions,” 13th ACM Symp. on Computational Geometry (SoCG), 1997, 284–293.

C-53. Gill Barequet, Stina S. Bridgeman, Christian A. Duncan, Michael T. Goodrich, and Roberto Tamassia, “Classical Computational Geometry in GeomNet,” 13th ACM Symp.

on Computational Geometry (SoCG), 1997, 412–414.

C-54. Gill Barequet, Amy J. Briggs, Matthew T. Dickerson, Cristian Dima, and Michael

T. Goodrich, “Animating the Polygon-Offset Distance Function,” 13th ACM Symp. on Computational Geometry (SoCG), 1997, 479–480, and the Video Review for the 13th ACM

Symp. on Computational Geometry (SoCG).

C-55. Gill Barequet, Amy J. Briggs, Matthew T. Dickerson, and Michael T. Goodrich, “Offset- Polygon Annulus Placement Problems,” 1997 Workshop on Algorithms and Data Structures

(WADS), 1997, 378–391. ( Proceedings version of J-34.)

14

C-56. Gill Barequet, Matthew T. Dickerson, and Michael T. Goodrich, “Voronoi Diagrams for Polygon-Offset Distance Functions,” 1997 Workshop on Algorithms and Data Structures

(WADS), 1997, 200–209. ( Proceedings version of J-42.)

C-57. Natasha Gelfand, Michael T. Goodrich, and Roberto Tamassia, “Teaching Data Structure

Design Patterns,” 29th ACM SIGCSE Technical Symp. on Computer Science Education, 1998, 331–335.

C-58. Michael T. Goodrich and Roberto Tamassia, “Teaching the Analysis of Algorithms with Visual Proofs,” 29th ACM SIGCSE Technical Symp. on Computer Science Education, 1998, 207–211.

C-59. Gill Barequet, Danny Z. Chen, Ovidiu Daescu, Michael T. Goodrich, and Jack S. Snoeyink, “Efficiently Approximating Polygonal Paths in Three and Higher Dimensions,” 1998 ACM

Symp. on Computational Geometry (SoCG), 1998, 317–326. ( Proceedings version of J-46.)

C-60. Michael T. Goodrich and Christopher G. Wagner, “A Framework for Drawing Planar

Graphs with Curves and Polylines,” 6th Int. Symp. on Graph Drawing (GD), Lecture Notes in Computer Science 1547, Springer, 1998, 153–166. ( Proceedings version of J-40.)

C-61. Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov, “Balanced Aspect Ratio

Trees and Their Use for Drawing Very Large Graphs,” 6th Int. Symp. on Graph Drawing

(GD), Lecture Notes in Computer Science 1547, Springer, 1998, 111–124. ( Proceedings version of J-39.)

C-62. Michael T. Goodrich, Mark Handy, Benoı̂t Hudson, and Roberto Tamassia, “Abstracting

Positional Information in Data Structures: Locators and Positions in JDSL,” Object- Oriented Programming, Systems, Languages & Applications (OOPSLA) ’98 Technical

Notes, 1998.

C-63. Michael T. Goodrich and John G. Kloss II, “Tiered Vector: An Efficient Dynamic Array for JDSL,” Object-Oriented Programming, Systems, Languages & Applications (OOPSLA)

’98 Technical Notes, 1998.

C-64. Michael T. Goodrich, Mark Handy, Benoı̂t Hudson, and Roberto Tamassia, “Accessing the Internal Organization of Data Structures in the JDSL Library,” Int. Workshop on Algorithm Engineering and Experimentation (ALENEX), Springer, Lecture Notes in Computer Science, Vol. 1619, 1999, 124–139.

C-65. Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov, “Balanced Aspect Ratio

Trees: Combining the Benefits of k-D Trees and Octrees,” 10th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1999, 300–309. ( Proceedings version of J-41.)

C-66. Ryan S. Baker, Michael Boilen, Michael T. Goodrich, Roberto Tamassia, and B. Aaron

Stibel, “Testers and Visualizers for Teaching Data Structures,” 30th ACM SIGCSE

Technical Symp. on Computer Science Education, 1999, 261–265.

C-67. Michael T. Goodrich and Roberto Tamassia, “Using Randomization in the Teaching of Data

Structures and Algorithms,” 30th ACM SIGCSE Technical Symp. on Computer Science

Education, 1999, 53–57. ( Proceedings version of Ch-5.)

C-68. Gill Barequet, Christian Duncan, Michael T. Goodrich, Sudodh Kumar, Mihai

Pop, “Efficient Perspective-Accurate Silhouette Computation,” 15th ACM Symp. on Computational Geometry (SoCG), 1999, 417–418, and the Video Review for the 15th ACM

Symp. on Computational Geometry (SoCG).

C-69. C.C. Cheng, Christian A. Duncan, Michael T. Goodrich, and Stephen G. Kobourov, “Drawing Planar Graphs with Circular Arcs,” 7th Int. Symp. on Graph Drawing (GD), Lecture Notes in Computer Science 1731, Springer, 1999, 117–126. ( Proceedings version of J- 43.)

15

C-70. Christian A. Duncan, Michael T. Goodrich, and Stephen G. Kobourov, “Planarity- Preserving Clustering and Embedding for Large Planar Graphs,” 7th Int. Symp. on Graph Drawing (GD), Lecture Notes in Computer Science 1731, Springer, 1999, 186–196.

( Proceedings version of J-48.)

C-71. Michael T. Goodrich and J.G. Kloss II, “Tiered Vectors: Efficient Dynamic Arrays for Rank- Based Sequences,” 1999 Workshop on Algorithms and Data Structures (WADS), Lecture

Notes in Computer Science 1663, Springer, 1999, 205–216.

C-72. Michael T. Goodrich, “Competitive Tree-Structured Dictionaries,” 11th ACM-SIAM Symp.

on Discrete Algorithms (SODA), 2000, 494–495.

C-73. Nancy M. Amato, Michael T. Goodrich, and Edgar A. Ramos, “Computing the Arrangement of Curve Segments: Divide-and-Conquer Algorithms via Sampling,” 11th

ACM-SIAM Symp. on Discrete Algorithms (SODA), 2000, 705–706.

C-74. S. Bridgeman, Michael T. Goodrich, Stephen G. Kobourov, and Roberto Tamassia, “PILOT: An Interactive Tool for Learning and Grading,” 31st ACM SIGCSE Technical

Symp. on Computer Science Education, 2000, 139–143.

C-75. S. Bridgeman, Michael T. Goodrich, Stephen G. Kobourov, and Roberto Tamassia, “SAIL:

A System for Generating, Archiving, and Retrieving Specialized Assignments in LaTeX,”

31st ACM SIGCSE Technical Symp. on Computer Science Education, 2000, 300–304.

C-76. Nancy M. Amato, Michael T. Goodrich, and Edgar A. Ramos, “Linear-Time Triangulation of a Simple Polygon Made Easier Via Randomization,” 16th ACM Symp. on Computational

Geometry (SoCG), 2000, 201-212. ( Proceedings version of J-44.)

C-77. Adam L. Buchsbaum, Michael T. Goodrich, and Jeffery R. Westbrook, “Range Searching

Over Tree Cross Products,” 8th European Symp. on Algorithms (ESA), Lecture Notes in Computer Science 1879, Springer, 2000, 120–131.

C-78. Christian A. Duncan, Matthew T. Dickerson, and Michael T. Goodrich, “k-D Trees are

Better When Cut on the Longest Side,” 8th European Symp. on Algorithms (ESA), Lecture

Notes in Computer Science 1879, Springer, 2000, 179–190.

C-79. Pawel Gajer, Michael T. Goodrich, and Stephen G. Kobourov, “A Fast Multi-Dimensional

Algorithm for Drawing Large Graphs,” 8th Int. Symp. on Graph Drawing (GD), Lecture

Notes in Computer Science 1984, Springer, 2001, 211–221. ( Proceedings version of J-52.)

C-80. Giuseppe Ateniese, Breno de Medeiros, and Michael T. Goodrich, “TRICERT: A Distributed Certified E-mail Scheme,” Network and Distributed Systems Security Symp.

(NDSS), 2001, 47–56.

C-81. Michael T. Goodrich and Roberto Tamassia, “Teaching Internet Algorithmics,” 32nd ACM

SIGCSE Technical Symp. on Computer Science Education, 2001, 129–133.

C-82. Mihai Pop, Gill Barequet, Christian A. Duncan, Michael T. Goodrich, Wenjing

Hwang, and Sudodh Kumar, “Efficient Perspective-Accurate Silhouette Computation and Applications,” 17th ACM Symp. on Computational Geometry (SoCG), 2001, 60–68.

C-83. Michael T. Goodrich and Roberto Tamassia, “Implementation of an Authenticated

Dictionary with Skip Lists and Commutative Hashing,” DARPA Information Survivability

Conf. & Exposition II (DISCEX), IEEE Press, 2001, 68–82.

C-84. Amitabha Bagchi, Amitabh Chaudhary, Rahul Garg, Michael T. Goodrich, and Vijay

Kumar, “Seller-Focused Algorithms for Online Auctioning,” 2001 Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science 2125, Springer, 2001, 135–147.

16

C-85. Aris Anagnostopoulos, Michael T. Goodrich, Roberto Tamassia, “Persistent Authenticated

Dictionaries and Their Applications,” Information Security Conf. (ISC), Lecture Notes in Computer Science 2200, Springer, 2001, 379–393.

C-86. Matthew T. Dickerson and Michael T. Goodrich, “Matching Points to a Convex Polygonal

Boundary,” 13th Canadian Conf. on Computational Geometry (CCCG), 2001, 8 pages.

C-87. Michael T. Goodrich, Roberto Tamassia, and Jasminka Hasic, “An Efficient Dynamic and Distributed Cryptographic Accumulator,” 5th Information Security Conf. (ISC), Lecture

Notes in Computer Science 2433, Springer, 2002, 372–388.

C-88. Adam L. Buchsbaum and Michael T. Goodrich, “Three-Dimensional Layers of Maxima,”

10th European Symp. on Algorithms (ESA), Lecture Notes in Computer Science 2461, Springer, 2002, 257–267. ( Proceedings version of J-49.)

C-89. Amitabha Bagchi, Adam L. Buchsbaum, and Michael T. Goodrich, “Biased Skip Lists,”

13th Int. Symp. on Algorithms and Computation (ISAAC), Lecture Notes in Computer

Science 2518, Springer, 2002, 1–13. ( Proceedings version of J-54.)

C-90. Michael T. Goodrich, “Efficient Packet Marking for Large-Scale IP Traceback,” 9th ACM

Conf. on Computer and Communications Security (CCS), 2002, 117–126. ( Proceedings version of J-61.)

C-91. Michael T. Goodrich, Roberto Tamassia, Nikos Triandopoulos, and Robert Cohen, “Authenticated Data Structures for Graph and Geometric Searching,” RSA Conf.—

Cryptographers’ Track (CT-RSA), Lecture Notes in Computer Science 2612, Springer, 2003, 295–313. ( Proceedings version of J-71.)

C-92. Michael T. Goodrich, Michael Shin, Roberto Tamassia, and William H. Winsborough, “Authenticated Dictionaries for Fresh Attribute Credentials,” 1st Int. Conf. on Trust

Management (iTrust), Lecture Notes in Computer Science 2692, Springer, 2003, 332–347.

C-93. Gill Barequet, Michael T. Goodrich, Aya Levi-Steiner, and Dvir Steiner, “Straight-Skeleton

Based Contour Interpolation,” 14th ACM-SIAM Symp. on Discrete Algorithms (SODA), 2003, 119–127. ( Proceedings version of J-51.)

C-94. Gill Barequet, Michael T. Goodrich, and Chris Riley, “Drawing Graphs with Large Vertices and Thick Edges,” 2003 Workshop and Data Structures and Algorithms (WADS), Lecture

Notes in Computer Science 2748, Springer, 2003, 281–293. ( Proceedings version of J-50.)

C-95. Amitabha Bagchi, Amitabh Chaudhary, Michael T. Goodrich, and Shouhuai Xu, “Constructing Disjoint Paths for Secure Communication,” 17th Int. Symp. on Distributed

Computing (DISC), Lecture Notes in Computer Science 2848, Springer, 2003, 181–195.

C-96. Matthew T. Dickerson, David Eppstein, Michael T. Goodrich, Jeremy Yu Meng, “Confluent

Drawings: Visualizing Non-planar Diagrams in a Planar Way,” 11th Int. Symp. on Graph

Drawing (GD), Lecture Notes in Computer Science 2912, Springer, 2003, 1–12. ( Proceedings version of J-55.)

C-97. Franz-Josef Brandenberg, David Eppstein, Michael T. Goodrich, Stephen G. Kobourov, Giuseppe Liotta, Petra Mutzel, “Selected Open Problems in Graph Drawing,” 11th Int.

Symp. on Graph Drawing (GD), Lecture Notes in Computer Science 2912, Springer, 2003, 515–539.

C-98. Amitabha Bagchi, Amitabh Chaudhary, David Eppstein, and Michael T. Goodrich, “Deterministic Sampling and Range Counting in Geometric Data Streams,” 20th ACM

Symp. on Computational Geometry (SoCG), 144–151, 2004. ( Proceedings version of J-58.)

17

C-99. Michael T. Goodrich, Jonathan Z. Sun, and Roberto Tamassia, “Efficient Tree-Based

Revocation in Groups of Low-State Devices,” Advances in Cryptology (CRYPTO), Springer, Lecture Notes in Computer Science 3152, 511–527, 2004.

C-100. David Eppstein, Michael T. Goodrich, and Jeremy Yu Meng, “Confluent Layered

Drawings,” 12th Int. Symp. on Graph Drawing (GD), Springer, Lecture Notes in Computer

Science 3383, 184–194, 2004. ( Proceedings version of J-57.)

C-101. Mikhail J. Atallah, Keith B. Frikken, Michael T. Goodrich, and Roberto Tamassia, “Secure

Biometric Authentication for Weak Computational Devices,” 9th Int. Conf. on Financial

Cryptography and Data Security, Springer, Lecture Notes in Computer Science 3570, 357–

371, 2005.

C-102. Michael T. Goodrich, “Leap-Frog Packet Linking and Diverse Key Distributions for Improved Integrity in Network Broadcasts,” IEEE Symp. on Security and Privacy (S&P), 196–207, 2005.

C-103. David Eppstein, Michael T. Goodrich, and Jonathan Z. Sun, “The Skip Quadtree: A Simple

Dynamic Data Structure for Multidimensional Data,” 21st ACM Symp. on Computational

Geometry (SoCG), 296–305, 2005. ( Proceedings version of J-60.)

C-104. Mikhail J. Atallah, Michael T. Goodrich, and Roberto Tamassia, “Indexing Information for Data Forensics,” 3rd Applied Cryptography and Network Security Conf. (ACNS), Lecture

Notes in Computer Science 3531, Springer, 206–221, 2005.

C-105. Wenliang Du and Michael T. Goodrich, “Searching for High-Value Rare Events with Uncheatable Grid Computing,” 3rd Applied Cryptography and Network Security Conf.

(ACNS), Lecture Notes in Computer Science 3531, Springer, 122–137, 2005.

C-106. Lars Arge, David Eppstein, and Michael T. Goodrich, “Skip-Webs: Efficient Distributed

Data Structures for Multi-Dimensional Data Sets,” 24th ACM Symp. on Principles of Distributed Computing (PODC), 2005.

C-107. David Eppstein, Michael T. Goodrich, and Daniel S. Hirschberg, “Improved Combinatorial

Group Testing for Real-World Problem Sizes,” Workshop on Algorithms and Data

Structures (WADS), Lecture Notes in Computer Science 3608, Springer, 86–98, 2005.

( Proceedings version of J-59.)

C-108. Amitabh Chaudhary and Michael T. Goodrich, “Balanced Aspect Ratio Trees Revisited,”

Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science

3608, Springer, 73–85, 2005.

C-109. Michael T. Goodrich, Roberto Tamassia, and Danfeng Yao, “Accredited DomainKeys: A Service Architecture for Improved Email Validation,” 2nd Conf. on Email and Anti-Spam

(CEAS), 1–8, 2005.

C-110. Michael T. Goodrich, George S. Lueker, and Jonathan Z. Sun, “C-Planarity of Extrovert

Clustered Graphs,” 13th Int. Symp. Graph Drawing (GD), 211–222, 2005.

C-111. David Eppstein, Michael T. Goodrich, Jeremy Yu Meng, “Delta-Confluent Drawings,” 13th

Int. Symp. Graph Drawing (GD), 165–176, 2005.

C-112. Michael T. Goodrich, Michael J. Nelson, and Jonathan Z. Sun, “The Rainbow Skip Graph:

A Fault-Tolerant Constant-Degree Distributed Data Structure,” 17th ACM-SIAM Symp.

on Discrete Algorithms (SODA), 384–393, 2006.

C-113. Michael T. Goodrich, Michael Sirivianos, John Solis, Gene Tsudik, Ersin Uzun, “Loud

And Clear: Human-Verifiable Authentication Based on Audio,” 26th IEEE Int. Conf. on Distributed Computing Systems (ICDCS), 1–8, 2006. ( Proceedings version of J-66.)

18

C-114. Michael T. Goodrich, Roberto Tamassia, and Danfeng Yao, “Notarized Federated Identity

Management for Web Services,” 20th IFIP WG Working Conf. on Data and Application

Security (DBSec), Springer, Lecture Notes in Computer Science, Vol. 4127, 133–147, 2006.

( Proceedings version of J-63.)

C-115. Michael T. Goodrich and Daniel S. Hirschberg, “Efficient Parallel Algorithms for Dead

Sensor Diagnosis and Multiple Access Channels,” 18th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), 118–127, 2006. ( Proceedings version of J-62.)

C-116. YounSun Cho, Lichun Bao, and Michael T. Goodrich, “LAAC: A Location-Aware Access

Control Protocol,” 2006 3rd Annual Int. Conf. on Mobile and Ubiquitous Systems -

Workshop on Ubiquitous Access Control (IWUAC), 1–7, 2006.

C-117. Michael B. Dillencourt, David Eppstein, and Michael T. Goodrich, “Choosing Colors for Geometric Graphs via Color Space Embeddings,” 14th Int. Symp. Graph Drawing (GD), Lecture Notes in Computer Science, Vol. 4372, Springer, 294–305, 2006.

C-118. David Eppstein, Michael T. Goodrich, and Nodari Sitchinava, “Guard Placement for Wireless Localization,” 23rd ACM Symp. on Computational Geometry (SoCG), 27–36, 2007.

C-119. Michael T. Goodrich, Charalampos Papmanthou, and Roberto Tamassia, “On the Cost of Persistence and Authentication in Skip Lists,” 6th Workshop on Experimental Algorithms

(WEA), LNCS 4525, 94–107, 2007.

C-120. Mikhail J. Atallah, M. Blanton, Michael T. Goodrich, and S. Polu, “Discrepancy-Sensitive

Dynamic Fractional Cascading, Dominated Maxima Searching, and 2-d Nearest Neighbors in Any Minkowski Metric,” Workshop on Algorithms and Data Structures (WADS), LNCS, Vol. 4619, Springer, 114–126, 2007.

C-121. David Eppstein and Michael T. Goodrich, “Space-Efficient Straggler Identification in Round-Trip Data Streams via Newton’s Identities and Invertible Bloom Filters,” Workshop on Algorithms and Data Structures (WADS), LNCS, Vol. 4619, Springer, 2007, 638–649.

( Proceedings version of J-72.)

C-122. Michael T. Goodrich and Jonathan Z. Sun, “Checking Value-Sensitive Data Structures in Sublinear Space,” 18th Int. Symp. on Algorithms and Computation (ISAAC), LNCS, vol. 4835, Springer, 2007, 353–364.

C-123. Michael T. Goodrich, Roberto Tamassia, and Nikos Triandopoulos, “Super-Efficient

Verification of Dynamic Outsourced Databases,” RSA Conf.—Cryptographers’ Track (CT- RSA), LNCS, vol. 4964, Springer, 2008, 407–424.

C-124. David Eppstein, Michael T. Goodrich, Ethan Kim, and Rasmus Tamstorf, “Approximate

Topological Matching of Quadrilateral Meshes,” IEEE Int. Conf. on Shape Modeling and Applications (SMI), 20