CURRICULUM VITAE
`Michael T. Goodrich
`E-mail: mike.t.goodrich (at) gmail.com
`http://www.ics.uci.edu/˜goodrich/
`
`Dept. of Computer Science
`Bren School of Info. & Computer Sciences
`University of California, Irvine
`Irvine, CA 92697-3435
`
`CITIZENSHIP: U.S.A.
`
`EDUCATION
`Ph.D.
`
`1987
`
`M.S.
`B.A.
`
`1985
`1983
`
`Efficient Parallel Techniques for Computational Geometry
`Computer Science, Purdue Univ. (M.J. Atallah, advisor)
`Computer Science, Purdue Univ.
`Mathematics and Computer Science, Calvin Univ.
`
`March ’10 to present
`
`April ’07 to June ’19
`
`July ’12 to June ’13
`
`October ’06 to June ’12
`
`July ’01 to March ’07
`
`Fall ’00
`
`PROFESSIONAL EXPERIENCE
`July ’19 to present
`Distinguished Professor, Dept. of Computer Science
`Univ. of California, Irvine
`Technical Director, Center for Algorithms and Theory of Computation
`Univ. of California, Irvine
`Chancellor’s Professor, Dept. of Computer Science
`Univ. of California, Irvine
`Chair, Dept. of Computer Science
`Univ. of California, Irvine
`Assoc. Dean for Faculty Dev., Bren School of Info. and Comp. Sci.
`Univ. of California, Irvine
`Professor, Dept. of Computer Science
`Univ. of California, Irvine
`Visiting Professor of Computer Science
`Brown Univ.
`Professor of Computer Science (on leave, from July ’01)
`Johns Hopkins Univ.
`Associate Professor of Computer Science
`Johns Hopkins Univ.
`Visiting Associate Professor of Computer Science
`Univ. of Illinois, Urbana-Champaign
`Assistant Professor of Computer Science
`Johns Hopkins Univ.
`Teaching Assistant, Research Assistant
`Purdue Univ.
`Summer intern
`Argonne National Laboratory
`
`July ’96 to June ’02
`
`July ’92 to June ’96
`
`Spring ’94
`
`July ’87 to June ’92
`
`Aug. ’83 to June ’87
`
`Summer ’83
`
`RESEARCH INTERESTS
`
`Algorithm and data structure design
`Networking and parallel and distributed computing
`Computer security and information assurance and privacy
`Machine learning and computer vision
`Databases and high-performance data management
`Information visualization and graph drawing
`Computational geometry and computer graphics
`
`1
`
`Carbyne Ex. 2031, p.1 of 40
`Apple v. Carbyne
`IPR2024-00329
`
`

`

`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 R. Tamassia, N. Triandopoulos,
`D. Yao, and D. Ellis), 2006
`• ACM Distinguished Scientist, 2006
`• 2006 IEEE Computer Society Technical Achievement Award, “for outstanding contributions
`to the design of parallel and distributed algorithms for fundamental combinatorial and
`geometric problems”
`• Fulbright Scholar, 2007, for senior specialist service to University of Aarhus, Denmark
`• 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 professional 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 of The Alejandro L´opez-Ortiz Best Paper Award, for “Zip-zip Trees: Making Zip
`Trees More Balanced, Biased, Compact, or Persistent,” 18th Algorithms and Data Structures
`Symposium, 2023.
`
`PUBLICATIONS
`
`Google Scholar Citation Statistics:
`• Total citations: over 18,000
`• H-index (top H publications with at least H citations): 73
`
`2
`
`Carbyne Ex. 2031, p.2 of 40
`Apple v. Carbyne
`IPR2024-00329
`
`

`

`Patents and Patent Applications:
`
`P-1. M.T. Goodrich and R. Tamassia, “An Efficient Dynamic Distributed Cryptographic
`Accumulator,” International Patent Application Pub. No. WO 02/39212, May 16, 2002.
`P-2. G. Ateniese, B. de Medeiros, and M.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. M.T. Goodrich and R. Tamassia, “Efficient Authenticated Dictionaries with Skip Lists and
`Commutative Hashing,” U.S. Patent No. 7,257,711, August 14, 2007.
`P-4. J.W. Green, J.L. Schultz, Y. Amir, and M.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. R. Tamassia, M.T. Goodrich, and N. Triandopoulos, “Super-efficient Verification of Dynamic
`Outsourced Databases,” International Patent Application Pub. No. WO 2008/014002,
`January 31, 2008.
`P-6. M.T. Goodrich, R. Tamassia, and N. Triandopoulos, “Load-balanced Distributred
`Authentication Structures,” International Patent Application Pub. No. WO 2008/014004,
`January 31, 2008.
`P-7. M.T. Goodrich, D. Yao, and R. Tamassia, “Notarized Federated Identity Management,”
`International Patent Application Pub. No. WO 2008/020991, February 21, 2008.
`P-8. R. Tamassia, M.T. Goodrich, N. Triandopoulos, and C. Papamanthou, “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. R. Tamstorf, M.T. Goodrich, D. 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. N. Triandopoulos, M.T. Goodrich, D. Nguyen, O. Ohrimenko, C. Papamanthou,
`R. Tamassia, C.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. M.T. Goodrich and R. Tamassia, Data Structures and Algorithms in Java, John Wiley and
`Sons, Inc., 1998.
`B-2. M.T. Goodrich and C.C. McGeoch, eds., Algorithm Engineering and Experimentation,
`Lecture Notes in Computer Science (LNCS), Vol. 1619, Springer-Verlag, 1999.
`B-3. M.T. Goodrich and R. Tamassia, Data Structures and Algorithms in Java, Second Edition,
`John Wiley and Sons, Inc., 2001.
`B-4. M.T. Goodrich and R. Tamassia, Algorithm Design: Foundations, Analysis, and Internet
`Examples, John Wiley and Sons, Inc., 2002.
`B-5. M.T. Goodrich and S.G. Kobourov, eds., 10th Int. Symp. on Graph Drawing (GD), Lecture
`Notes in Computer Science, Vol. 2528, Springer-Verlag, 2002.
`B-6. M.T. Goodrich, R. Tamassia, and D. Mount, Data Structures and Algorithms in C++, John
`Wiley and Sons, Inc., 2004.
`B-7. M.T. Goodrich and R. Tamassia, Data Structures and Algorithms in Java, Third Edition,
`John Wiley and Sons, Inc., 2004.
`B-8. M.T. Goodrich and R. Tamassia, Data Structures and Algorithms in Java, Fourth Edition,
`John Wiley and Sons, Inc., 2006.
`
`3
`
`Carbyne Ex. 2031, p.3 of 40
`Apple v. Carbyne
`IPR2024-00329
`
`

`

`B-9. M.T. Goodrich and R. Tamassia, Data Structures and Algorithms in Java, Fifth Edition,
`John Wiley and Sons, Inc., 2011.
`B-10. M.T. Goodrich and R. Tamassia, Introduction to Computer Security, Addison-Wesley, 2011.
`B-11. M.T. Goodrich, R. Tamassia, and D. Mount, Data Structures and Algorithms in C++,
`Second Edition, John Wiley and Sons, Inc., 2011.
`B-12. M.T. Goodrich, R. Tamassia, and M. Goldwasser, Data Structures and Algorithms in Python,
`John Wiley and Sons, Inc., 2013.
`B-13. M.T. Goodrich, R. Tamassia, and M. Goldwasser, Data Structures and Algorithms in Java,
`Sixth Edition, John Wiley and Sons, Inc., 2014.
`B-14. M.T. Goodrich and R. Tamassia, Algorithm Design and Applications, Wiley, 2015.
`B-15. M.T. Goodrich and R. Tamassia, Algorithm Design and Applications, interactive e-book,
`www.zybooks.com/catalog/goodrich-algorithm-design-and-applications/, zyBooks
`(a division of Wiley), 2022.
`
`Book Chapters:
`
`Ch-1. M.J. Atallah and M.T. Goodrich, “Deterministic Parallel Computational Geometry,” in
`Synthesis of Parallel Algorithms, J.H. Reif, ed., Morgan Kaufmann, 497–536, 1993.
`Ch-2. M.T. Goodrich, “The Grand Challenges of Geometric Computing,” in Developing a
`Computer Science Agenda for High-Performance Computing, U. Vishkin, ed., ACM Press,
`64–68, 1994.
`Ch-3. M.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. M.T. Goodrich and K. Ramaiyer, “Geometric Data Structures,” Handbook of Computational
`Geometry, J.-R. Sack and J. Urrutia, eds., Elsevier Science Publishing, 463–489, 2000.
`Ch-5. M.T. Goodrich and R. 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. M.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. C. Duncan and M.T. Goodrich, “Approximate Geometric Query Structures,” Handbook of
`Data Structures and Applications, Chapman & Hall/CRC Press, Inc., 26-1–26-17, 2005.
`Ch-8. M.T. Goodrich, R. Tamassia, and L. Vismara, “Data Structures in JDSL,” Handbook of
`Data Structures and Applications, Chapman & Hall/CRC Press, Inc., 43-1–43-22, 2005.
`Ch-9. Y. Cho, L. Bao and M.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. M.T. Goodrich and M.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. C.A. Duncan and M.T. Goodrich, “Planar Orthogonal and Polyline Drawing Algorithms,”
`Handbook of Graph Drawing and Visualization, CRC Press, Inc., 223–246, 2013.
`Ch-12. M.T. Goodrich, R. Tamassia, and L. 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.
`
`4
`
`Carbyne Ex. 2031, p.4 of 40
`Apple v. Carbyne
`IPR2024-00329
`
`

`

`Journal Papers:
`
`J-1. M.J. Atallah and M.T. Goodrich, “Efficient Parallel Solutions to Some Geometric Problems,”
`Journal of Parallel and Distributed Computing, 3(4), 1986, 492–507.
`J-2. M.T. Goodrich, “Finding the Convex Hull of a Sorted Point Set in Parallel,” Information
`Processing Letters, 26, 1987, 173–179.
`J-3. H. ElGindy and M.T. Goodrich, “Parallel Algorithms for Shortest Path Problems in
`Polygons,” The Visual Computer, 3(6), 1988, 371–378.
`J-4. M.J. Atallah and M.T. Goodrich, “Parallel Algorithms For Some Functions of Two Convex
`Polygons,” Algorithmica, 3, 1988, 535–548.
`J-5. M.J. Atallah, R. Cole, and M.T. Goodrich, “Cascading Divide-and-Conquer: A Technique
`for Designing Parallel Algorithms,” SIAM Journal on Computing, 18(3), 1989, 499–532.
`J-6. M.T. Goodrich, “Triangulating a Polygon in Parallel,” Journal of Algorithms, 10, 1989,
`327–351.
`J-7. M.T. Goodrich and M.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. M.T. Goodrich and J.S. Snoeyink, “Stabbing Parallel Segments with a Convex Polygon,”
`Computer Vision, Graphics and Image Processing, 49, 1990, 152–170.
`J-9. J. Johnstone and M.T. Goodrich, “A Localized Method for Intersecting Plane Algebraic
`Curve Segments,” The Visual Computer, 7(2–3), 1991, 60–71.
`J-10. M.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. R. Cole and M.T. Goodrich, “Optimal Parallel Algorithms for Point-Set and Polygon
`Problems,” Algorithmica, 7, 1992, 3–23.
`J-12. M.T. Goodrich, “A Polygonal Approach to Hidden-Line and Hidden-Surface Elimination,”
`Computer Vision, Graphics, and Image Processing: Graphical Models and Image Processing,
`54(1), 1992, 1–12.
`J-13. M.T. Goodrich, S. Shauck, and S. 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.
`J-14. M.T. Goodrich, C. ´O’D´unlaing, and C. Yap “Constructing the Voronoi Diagram of a Set of
`Line Segments in Parallel,” Algorithmica, 9, 1993, 128–141.
`J-15. M.T. Goodrich, “Constructing the Convex Hull of a Partially Sorted Set of Points,”
`Computational Geometry: Theory and Applications, 2, 1993, 267–278.
`J-16. M.T. Goodrich, “Constructing Arrangements Optimally in Parallel,” Discrete and
`Computational Geometry, 9, 1993, 371–385.
`J-17. M.T. Goodrich, M.J. Atallah, and M. Overmars, “Output-Sensitive Methods for Rectilinear
`Hidden Surface Removal,” Information and Computation, 107(1), 1993, 1–24.
`J-18. M.J. Atallah, P. Callahan, and M.T. Goodrich, “P-Complete Geometric Problems,” Int.
`Journal of Computational Geometry & Applications, 3(4), 1993, 443–462.
`J-19. M.J. Atallah, M.T. Goodrich, and S.R. Kosaraju, “Parallel Algorithms for Evaluating
`Sequences of Set-Manipulation Operations,” Journal of the ACM, 41(6), 1994, 1049–1088.
`J-20. M.T. Goodrich, “Efficient Piecewise-Linear Function Approximation Using the Uniform
`Metric,” Discrete and Computational Geometry, 14, 1995, 445–462.
`J-21. H. Br¨onnimann and M.T. Goodrich, “Almost Optimal Set Covers in Finite VC-Dimension,”
`Discrete and Computational Geometry, 14, 1995, 463–479.
`J-22. M.T. Goodrich, “Planar Separators and Parallel Polygon Triangulation,” J. Computer and
`
`5
`
`Carbyne Ex. 2031, p.5 of 40
`Apple v. Carbyne
`IPR2024-00329
`
`

`

`System Sciences, 51(3), 1995, 374–389.
`J-23. M.T. Goodrich, M. Ghouse, and J. Bright, “Sweep Methods for Parallel Computational
`Geometry,” Algorithmica, 15(2), 1996, 126–153.
`J-24. M.T. Goodrich and S.R. Kosaraju, “Sorting on a Parallel Pointer Machine with Applications
`to Set Expression Evaluation,” Journal of the ACM, 43(2), 1996, 331–361.
`J-25. A. Garg, M.T. Goodrich, and R. Tamassia, “Planar Upward Tree Drawings with Optimal
`Area,” International Journal of Computational Geometry & Applications, 6(3), 1996, 333–
`356.
`J-26. M.H. Nodine, M.T. Goodrich, and J.S. Vitter, “Blocking for External Graph Searching,”
`Algorithmica, 16(2), 1996, 181–214.
`J-27. R. Cole, M.T. Goodrich, C. ´O D´unlaing, “A Nearly Optimal Deterministic Parallel Voronoi
`Diagram Algorithm,” Algorithmica, 16, 1996, 569–617.
`J-28. G. Das and M.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. M.T. Goodrich and R. Tamassia, “Dynamic Ray Shooting and Shortest Paths in Planar
`Subdivisions via Balanced Geodesic Triangulations,” J. Algorithms, 23, 1997, 51–73.
`J-30. M. Ghouse and M.T. Goodrich, “Fast Randomized Parallel Methods for Planar Convex Hull
`Construction,” Computational Geometry: Theory and Applications, 7, 1997, 219–235.
`J-31. 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, 113-124.
`J-32. M.T. Goodrich and E.A. Ramos, “Bounded-Independence Derandomization of Geometric
`Partitioning with Applications to Parallel Fixed-Dimensional Linear Programming,” Discrete
`& Computational Geometry, 18(4), 1997, 397–420.
`J-33. M.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. G. Barequet, A.J. Briggs, M.T. Dickerson, and M.T. Goodrich, “Offset-Polygon Annulus
`Placement Problems,” Computational Geometry: Theory and Applications, 11(3–4), 1998–
`99, 125–141.
`J-35. M.T. Goodrich and R. Tamassia, “Dynamic Trees and Dynamic Point Location,” SIAM J.
`Comput., 28(2), 1999, 612–636.
`J-36. G. Barequet, S.S. Bridgeman, C.A. Duncan, M.T. Goodrich, and R. Tamassia, “GeomNet:
`Geometric Computing Over the Internet,” IEEE Internet Computing, 3(2), 1999, 21–29.
`J-37. 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,
`21(4), 1999, 371–379.
`J-38. M.T. Goodrich, “Communication-Efficient Parallel Sorting,” SIAM Journal on Computing,
`29(2), 1999, 416–432.
`J-39. C.A. Duncan, M.T. Goodrich, S.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 www.cs.brown.edu/publications/jgaa/.
`J-40. M.T. Goodrich and C.G. Wagner, “A Framework for Drawing Planar Graphs with Curves
`and Polylines,” Journal of Algorithms, 37, 2000, 399–421.
`J-41. C.A. Duncan, M.T. Goodrich, S.G. Kobourov, “Balanced Aspect Ratio Trees: Combining
`
`6
`
`Carbyne Ex. 2031, p.6 of 40
`Apple v. Carbyne
`IPR2024-00329
`
`

`

`the Benefits of k-D Trees and Octrees,” J. Algorithms, 38, 2001, 303–333.
`J-42. G. Barequet, M. Dickerson, and M.T. Goodrich, “Voronoi Diagrams for Polygon-Offset
`Distance Functions,” Discrete and Computational Geometry, 25(2), 2001, 271–291.
`J-43. C.C. Cheng, C.A. Duncan, M.T. Goodrich, and S.G. Kobourov, “Drawing Planar Graphs
`with Circular Arcs,” Discrete and Computational Geometry, 25(3), 2001, 405–418.
`J-44. 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, 245–
`265.
`J-45. 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, 21–31.
`J-46. G. Barequet, D.Z. Chen, O. Daescu, M.T. Goodrich, and J.S. Snoeyink, “Efficiently
`Approximating Polygonal Paths in Three and Higher Dimensions,” Algorithmica, 33(2),
`2002, 150–167.
`J-47. T. Chan, M.T. Goodrich, S.R. Kosaraju, and R. Tamassia, “Optimizing Area and Aspect
`Ratio in Straight-Line Orthogonal Tree Drawings,” Computational Geometry: Theory and
`Applications, 23(2), 2002, 153–162.
`J-48. C.A. Duncan, M.T. Goodrich, and S.G. Kobourov, “Planarity-Preserving Clustering and
`Embedding for Large Planar Graphs,” Computational Geometry: Theory and Applications,
`24(2), 2003, 95–114.
`J-49. A.L. Buchsbaum and M.T. Goodrich, “Three-Dimensional Layers of Maxima,” Algorithmica,
`39, 2004, 275–286.
`J-50. G. Barequet, M.T. Goodrich, and C. Riley, “Drawing Graphs with Large Vertices and Thick
`Edges,” J. of Graph Algorithms and Applications (JGAA), 8(1), 2004, 3–20.
`J-51. G. Barequet, M.T. Goodrich, A. Levi-Steiner, and D. Steiner, “Contour Interpolation by
`Straight Skeletons,” Graphical Models (GM), 66(4), 2004, 245–260.
`J-52. P. Gajer, M.T. Goodrich, and S.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. G. Barequet, P. Bose, M.T. Dickerson, and M.T. Goodrich, “Optimizing a Constrained
`Convex Polygonal Annulus,” J. of Discrete Algorithms (JDA), 3(1), 1–26, 2005.
`J-54. A. Bagchi, A.L. Buchsbaum, and M.T. Goodrich, “Biased Skip Lists,” Algorithmica, 42(1),
`31–48, 2005.
`J-55. M. Dickerson, D. Eppstein, M.T. Goodrich, J.Y. 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. A. Bagchi, A. Chaudhary, M.T. Goodrich, C. Li, and M. 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. D. Eppstein, M.T. Goodrich, and J.Y. Meng, “Confluent Layered Drawings,” Algorithmica,
`47(4), 439–452, 2007.
`J-58. A. Bagchi, A. Chaudhary, D. Eppstein, and M.T. Goodrich, “Deterministic Sampling and
`Range Counting in Geometric Data Streams,” ACM Transactions on Algorithms, 3(2),
`Article 16, 2007, 18 pages.
`J-59. D. Eppstein, M.T. Goodrich, and D. Hirschberg, “Improved Combinatorial Group Testing
`
`7
`
`Carbyne Ex. 2031, p.7 of 40
`Apple v. Carbyne
`IPR2024-00329
`
`

`

`Algorithms for Real-World Problem Sizes,” SIAM Journal on Computing, 36(5), 1360–1375,
`2007.
`J-60. D. Eppstein, M.T. Goodrich, and J.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. M.T. Goodrich, “Probabilistic Packet Marking for Large-Scale IP Traceback,” IEEE/ACM
`Transactions on Networking, 16(1), 15–24, 2008.
`J-62. M.T. Goodrich and D.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. M.T. Goodrich, R. Tamassia, and D. Yao, “Notarized Federated ID Management and
`Authentication,” Journal of Computer Security, 16(4), 399–418, 2008.
`J-64. M.T. Goodrich, “Pipelined Algorithms to Detect Cheating in Long-Term Grid Computa-
`tions,” Theoretical Computer Science, 408, 199–207, 2008.
`J-65. D. Eppstein, M.T. Goodrich, E. Kim, and R. 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. M.T. Goodrich, M. Sirivianos, J. Solis, C. Soriente, G. Tsudik, E. Uzun, “Using Audio in
`Secure Device Pairing,” Int. J. Security and Networks, 4(1/2), 57–68, 2009.
`J-67. M.T. Goodrich, “On the Algorithmic Complexity of the Mastermind Game with Black-Peg
`Results,” Information Processing Letters, 109, 675–678, 2009.
`J-68. D. Eppstein, M.T. Goodrich, E. Kim, and R. Tamstorf, “Approximate Topological Matching
`of Quad Meshes,” The Visual Computer, 25(8), 771–783, 2009.
`J-69. D. Eppstein and M.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. D. Eppstein, M.T. Goodrich, and D. Strash, “Linear-Time Algorithms for Geometric Graphs
`with Sublinearly Many Edge Crossings,” SIAM Journal on Computing, 39(8), 3814–3829.
`2010.
`J-71. M.T. Goodrich, R. Tamassia, and N. Triandopoulos, “Efficient Authenticated Data
`Structures for Graph Connectivity and Geometric Search Problems,” Algorithmica, 60(3),
`505–552, 2011.
`J-72. D. Eppstein and M.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. C.A. Duncan, M.T. Goodrich, S.G. Kobourov, “Planar Drawings of Higher-Genus Graphs,”
`Journal of Graph Algorithms and Applications, 15(1), 7–32, 2011.
`J-74. M.T. Dickerson, M.T. Goodrich, T.D. Dickerson, and Y.D. 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. M.T. Goodrich, “Randomized Shellsort: A Simple Data-Oblivious Sorting Algorithm,”
`Journal of the ACM, 58(6), Article No. 27, 2011.
`J-76. C.A. Duncan, D. Eppstein, M.T. Goodrich, S. Kobourov, and M. N¨ollenburg, “Lombardi
`Drawings of Graphs,” Journal of Graph Algorithms and Applications (JGAA), 16(1), 85–
`108, 2012.
`J-77. E. Wolf-Chambers, D. Eppstein, M.T. Goodrich, and M. L¨offler, “Drawing Graphs in the
`
`8
`
`Carbyne Ex. 2031, p.8 of 40
`Apple v. Carbyne
`IPR2024-00329
`
`

`

`Plane with a Prescribed Outer Face and Polynomial Area,” Journal of Graph Algorithms
`and Applications (JGAA), 16(2), 243–259, 2012.
`J-78. M.T. Goodrich, D. Nguyen, O. Ohrimenko, C. Papamanthou, R. Tamassia, N.
`Triandopoulos, and C.V. Lopes, “Efficient Verification of Web-Content Searching Through
`Authenticated Web Crawlers,” Proc. VLDB, 5(10):920-931, 2012.
`J-79. D. Eppstein, M.T. Goodrich, D. Strash, and L. Trott, “Extended Dynamic Subgraph
`Statistics Using h-Index Parameterized Data Structures,” Theoretical Computer Science,
`447, 44–52, 2012.
`J-80. M.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. A.U. Asuncion and M.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. C.A. Duncan, D. Eppstein, M.T. Goodrich, S. Kobourov, and M. N¨ollenburg, “Drawing
`Trees with Perfect Angular Resolution and Polynomial Area,” Discrete & Computational
`Geometry, 49(2), 157–182, 2013.
`J-83. E. Angelino, M.T. Goodrich, M. Mitzenmacher and J. Thaler, “External Memory
`Multimaps,” Algorithmica, 67(1), 23–48, 2013.
`J-84. D. Eppstein, M.T. Goodrich, M. L¨offler, D. Strash and L. Trott, “Category-Based Routing
`in Social Networks: Membership Dimension and the Small-World Phenomenon,” Theoretical
`Computer Science, 514, 96–104, 2013.
`J-85. M.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 M.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. C. Duncan, D. Eppstein, M.T. Goodrich, S.G. Kobourov and M. L¨offler, “Planar and Poly-
`Arc Lombardi Drawings,” Journal of Computational Geometry (JoCG), 9(1), 328–355, 2018.
`J-88. G. Barequet, D. Eppstein, M.T. Goodrich, and N. Mamano, “Stable-Matching Voronoi
`Diagrams: Combinatorial Complexity and Algorithms,” Journal of Computational Geometry
`(JoCG), 11(1), 26–59, 2020.
`J-89. M.T. Goodrich, Z.M. Liang, and S. Zhao, “Inverse-Rendering Based Analysis of the Fine
`Illumination Effects in the Salvator Mundi,” Leonardo, 53(4), 380–386, 2020.
`J-90. W.E. Devanny, M.T. Goodrich, S. Irani, “A Competitive Analysis for the Start-Gap
`Algorithm for Online Memory Wear Leveling,” Information Processing Letters, 116, 106042,
`2021.
`J-91. G. Barequet, M. De, and M.T. Goodrich, “Convex-Straight-Skeleton Voronoi Diagrams for
`Segments and Convex Polygons,” Algorithmica, 83(7), 2245–2272, 2021.
`J-92. G. Da Lozzo, D. Eppstein, M.T. Goodrich, and S. Gupta, “C-Planarity Testing of Embedded
`Clustered Graphs with Bounded Dual Carving-Width,” Algorithmica, 83(8), 2471–2502,
`2021.
`J-93. M. Shinder, M.T. Goodrich, O. Gila, M. Dillencourt, “Beyond Big O: Teaching Experimental
`Algorithmics,” Journal of Computing Sciences in Colleges, 37(10), 23–36, 2022.
`J-94. P. Choudhary, M.T. Goodrich, S. Gupta, H. Khodabandeh, P. Matias, and V. Raman,
`“Improved Kernels for Tracking Paths,” Information Processing Letters, 181, 106360, 2023.
`
`9
`
`Carbyne Ex. 2031, p.9 of 40
`Apple v. Carbyne
`IPR2024-00329
`
`

`

`J-95. M. Dillencourt and M.T. Goodrich, “Simplified Chernoff Bounds with Powers-of-Two
`Probabilities,” Information Processing Letters, 182, 106397, 2023.
`J-96. S. Han, V. Chakraborty, M.T. Goodrich, S. Mehrotra, S. 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. M.A. Bender, M. Farach-Colton, M.T. Goodrich, and H. Komlos, “History-Independent
`Dynamic Partitioning: Operation-Order Privacy in Ordered Data Structures,” Proc. ACM
`Management of Data (PODS), 2(2), 108:1-108:27, 2024. Best Paper Award
`J-98. M. Dillencourt, M.T. Goodrich, and M. Mitzenmacher, “Leveraging Parameterized Chernoff
`Bounds for Simplified Algorithm Analyses,” Information Processing Letters, 187, 106516,
`2025 (posted online June 2024).
`
`Papers in Proceedings:
`
`C-1. M.J. Atallah and M.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. F. Berman, M.T. Goodrich, C. Koelbel, W. Robison, and K. Showell, “Prep-P: A Mapping
`Preprocessor for CHiP Computers,” 1985 IEEE Int. Conf. on Parallel Processing, 731–733.
`C-3. M.J. Atallah and M.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. M.J. Atallah and M.T. Goodrich, “Efficient Plane Sweeping in Parallel,” 2nd ACM Symp.
`on Computational Geometry (SoCG), 1986, 216–225.
`C-5. M.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. M.J. Atallah, R. Cole, and M.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. M.J. Atallah, M.T. Goodrich, and S.R. Kosaraju, “Parallel Algorithms for Evaluating
`Sequences of Set-Manipulation Operations,” 3rd Aegean Workshop on Computing (AWOC),
`Lecture Notes in Computer Science (LNCS): 319, Springer-Verlag, 1988, 1–10. (Proceedings
`version of J-19.)
`C-8. R. Cole and M.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. M.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. M.T. Goodrich and S.R. 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. M.T. Goodrich, C. ´O’D´unlaing, and C. 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-Verlag, 1989, 12–23. (Proceedings version of J-14.)
`C-12. M.T. Goodrich and J.S. Snoeyink, “Stabbing Parallel Segments with a Convex Polygon,”
`Lecture Notes in Computer Science 382, Algorithms and Data Structures (WADS), Springer-
`Verlag, 1989, 231–242. (Proceedings version of J-8.)
`
`10
`
`Carbyne Ex. 2031, p.10 of 40
`Apple v. Carbyne
`IPR2024-00329
`
`

`

`C-13. J. Johnstone and M.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-Verlag, 1989, 165–181.
`(Proceedings version of J-9.)
`C-14. M.J. Atallah, P. Callahan, and M.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. R. Cole, M.T. Goodrich, C. ´O D´unlaing, “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. M.T. Goodrich, M.J. Atallah, and M. 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. M.T. Goodrich, M. Ghouse, and J. Bright, “Generalized Sweep Methods for Parallel
`Computational Geometry,” 2n