CURRICULUM VITAE
`Michael T. Goodrich
`
`Dept. of Computer Science
`Bren School of Info. & Computer Sciences
`University of California, Irvine
`Irvine, CA 92697-3435
`
`E-mail: goodrich (at) ieee.org
`http://www.ics.uci.edu/˜goodrich/
`Phone: (949)824-9366
`Fax: (949)824-4056
`
`CITIZENSHIP: U.S.A.
`
`EDUCATION
`Ph.D.
`
`1987
`
`M.S.
`B.A.
`
`1985
`1983
`
`Efficient Parallel Techniques for Computational Geometry
`Computer Sciences, Purdue Univ. (M.J. Atallah, advisor)
`Computer Sciences, Purdue Univ.
`Mathematics and Computer Science, Calvin College
`
`July ’12 to June ’13
`
`October ’06 to June ’12
`
`July ’01 to March ’07
`
`Fall ’00
`
`PROFESSIONAL EXPERIENCE
`April ’07 to present
`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.
`
`July ’96 to June ’02
`
`July ’92 to June ’96
`
`Spring ’94
`
`July ’87 to June ’92
`
`RESEARCH INTERESTS
`
`Algorithm and Data Structure Design
`Information Assurance and Security
`Parallel and Distributed Computing
`Graph and Geometric Algorithms
`
`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
`
`1
`
`1
`
`SYMC 1004
`
`

`
`• 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 geo-
`metric 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 writ-
`ing,” 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 his contributions in the area of parallel and distributed
`algorithms,” 2014
`
`PUBLICATIONS
`
`Patents and Patent Applications:
`
`P-1. G. Ateniese, B. de Medeiros, and M.T. Goodrich, “Intermediated Delivery Scheme for Asym-
`metric Fair Exchange of Electronic Items,” U.S. Patent Application US 2004/0073790 A1,
`April 15, 2004.
`P-2. M.T. Goodrich and R. Tamassia, “Efficient Authenticated Dictionaries with Skip Lists and
`Commutative Hashing,” U.S. Patent 7,257,711, August 14, 2007.
`P-3. 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 7,299,219, November
`20, 2007.
`P-4. R. Tamstorf, M.T. Goodrich, D. Eppstein, “Attribute Transfer Between Computer Mod-
`els Including Identifying Isomorphic Regions in Polygonal Meshes,” U.S. Patent 8,681,145,
`March 25, 2014.
`
`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, Lec-
`ture 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 International Symposium on Graph Drawing
`(GD), Lecture Notes in Computer Science, Vol. 2528, Springer-Verlag, 2002.
`
`2
`
`2
`
`SYMC 1004
`
`

`
`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.
`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, Inc.,
`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.
`
`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 Com-
`puter 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 Com-
`putational 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.
`
`3
`
`3
`
`SYMC 1004
`
`

`
`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.
`
`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 Poly-
`gons,” 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 Prob-
`lems,” 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 Algorith-
`mica, 9, 1993, 515–516.
`J-14. M.T. Goodrich, C. ´O’D´unlaing, and C. Yap “Computing 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,” Com-
`putational Geometry: Theory and Applications, 2, 1993, 267–278.
`J-16. M.T. Goodrich, “Constructing Arrangements Optimally in Parallel,” Discrete and Compu-
`tational 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 Se-
`quences of Set-Manipulation Operations,” Journal of the ACM, 41(6), 1994, 1049–1088.
`
`4
`
`4
`
`SYMC 1004
`
`

`
`J-20. M.T. Goodrich, “Efficient Piecewise-Linear Function Approximation Using the Uniform Met-
`ric,” 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
`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 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 Mod-
`els 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,
`
`5
`
`5
`
`SYMC 1004
`
`

`
`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
`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 Dis-
`tance 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 Ap-
`proximating 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. 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 Com-
`
`6
`
`6
`
`SYMC 1004
`
`

`
`munication 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), Ar-
`ticle 16, 2007, 18 pages.
`J-59. D. Eppstein, M.T. Goodrich, and D. Hirschberg, “Improved Combinatorial Group Testing
`Algorithmis 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 Combi-
`natorial Optimization, 15(1), 95–121, 2008.
`J-63. M.T. Goodrich, R. Tamassia, and D. Yao, “Notarized Federated Identity Management for
`Web Services,” 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 Eu-
`ropean Symposium 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 Struc-
`tures 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.
`
`7
`
`7
`
`SYMC 1004
`
`

`
`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 Di-
`agrams 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,” Jour-
`nal 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
`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. Triandopou-
`los, 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 Statis-
`tics 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 Engi-
`neering (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 Mul-
`timaps,” 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.
`
`Papers in Reviewed Conference Proceedings:
`
`C-1. M.J. Atallah and M.T. Goodrich, “Efficient Parallel Solutions to Some Geometric Problems,”
`1985 IEEE Int. Conf. on Parallel Processing, 411–417. (Preliminary 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.
`(Preliminary version of J-4.)
`C-4. M.J. Atallah and M.T. Goodrich, “Efficient Plane Sweeping in Parallel,” 2nd ACM Symp.
`
`8
`
`8
`
`SYMC 1004
`
`

`
`on Computational Geometry (SCG), 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. (Preliminary 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. (Preliminary version of J-5.)
`C-7. M.J. Atallah, M.T. Goodrich, and S.R. Kosaraju, “Parallel Algorithms for Evaluating Se-
`quences of Set-Manipulation Operations,” 3rd Aegean Workshop on Computing (AWOC),
`Lecture Notes in Computer Science (LNCS): 319, Springer-Verlag, 1988, 1–10. (Preliminary
`version of J-19.)
`
`C-8. R. Cole and M.T. Goodrich, “Optimal Parallel Algorithms for Point-Set and Polygon Prob-
`lems,” 4th ACM Symp. on Computational Geometry (SCG), 1988, 201–210. (Preliminary 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.
`(Preliminary version of J-10.)
`C-10. M.T. Goodrich and S.R. Kosaraju, “Sorting on a Parallel Pointer Machine with Applica-
`tions to Set Expression Evaluation,” 30th IEEE Symp. on Foundations of Computer Science
`(FOCS), 1989, 190–195. (Preliminary version of J-24.)
`C-11. M.T. Goodrich, C. ´O’D´unlaing, and C. Yap “Computing 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. (Preliminary 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. (Preliminary version of J-8.)
`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 In-
`ternational ’89, R.A. Earnshaw, B. Wyvel, eds., Springer-Verlag, 1989, 165–181. (Preliminary
`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. (Preliminary
`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 Program-
`ming (ICALP), 1990, 432–445. (Preliminary 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. (Preliminary version of J-17.)
`C-17. M.T. Goodrich, M. Ghouse, and J. Bright, “Generalized Sweep Methods for Parallel Com-
`putational Geometry,” 2nd ACM Symp. on Parallel Algorithms and Architectures (SPAA),
`1990, 280–289. (Preliminary version of J-23.)
`C-18. M.T. Goodrich, “Applying Parallel Processing Techniques to Classification Problems in Con-
`structive Solid Geometry,” 1st ACM-SIAM Symp. on Discrete Algorithms (SODA), 1990,
`118–128. (Preliminary version of J-33.)
`
`9
`
`9
`
`SYMC 1004
`
`

`
`C-19. M.T. Goodrich, S. Shauck, and S. Guha, “Parallel Methods for Visibility and Shortest Path
`Problems in Simple Polygons,” 6th ACM Symp. on Computational Geometry (SCG), 1990,
`73–82. (Preliminary version of J-13.)
`C-20. M. Ghouse and M.T. Goodrich, “In-Place Techniques for Parallel Convex Hull Algorithms,”
`3rd ACM Symp. on Parallel Algorithms and Architectures (SPAA), 1991, 192–203. (Preliminary
`version of J-30.)
`
`C-21. M.T. Goodrich, “Constructing Arrangements Optimally in Parallel,” 3rd ACM Symp. on
`Parallel Algorithms and Architectures (SPAA), 1991, 169–179. (Preliminary version of J-16.)
`C-22. M.T. Goodrich and R. Tamassia, “Dynamic Trees and Dynamic Point Location,” 23rd ACM
`Symp. on Theory of Computing (STOC), 1991, 523–533. (Preliminary version of J-35.)
`C-23. M.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. M.T. Goodrich, “Planar Separators and Parallel Polygon Triangulation,” 24th ACM Symp.
`on Theory of Computing (STOC), 1992, 507–516. (Preliminary version of J-22.)
`C-25. M.T. Goodrich, Y. Matias, U. Vishkin, “Approximate Parallel Prefix Computation and Its
`Applications,” 7th IEEE Int. Parallel Processing Symp (IPPS), 1993, 318–325.
`C-26. M. Ghouse and M.T. Goodrich, “Experimental Evidence for the Power of Random Sampling
`in Practical Parallel Algorithms,” 7th IEEE Int. Parallel Processing Symp (IPPS), 1993,
`549–556.
`C-27. L.P. Chew, M.T. Goodrich, D.P. Huttenlocher, K. Kedem, J.M. Kleinberg, and D. Kravets,
`“Geometric Pattern Matching under Euclidean Motion,” Proc. 5th Canadian Conference on
`Computational Geometry (CCCG), 1993, 151–156. (Preliminary version of J-31.)
`C-28. M.T. Goodrich, “Geometric Partitioning Made Easier, Even in Parallel,” 9th ACM Symp.
`on Computational Geometry (SCG), 1993, 73–82.
`C-29. M.T. Goodrich and R. Tamassia, “Dynamic Ray Shooting and Shortest Paths via Balanced
`Geodesic Triangulations,” 9th ACM Symp. on Computational Geometry (SCG), 1993, 318–
`327. (Preliminary version of J-29.)
`C-30. A. Garg, M.T. Goodrich, and R. Tamassia, “Area-Efficient Upward Tree Drawings,” 9th
`ACM Symp. on Computational Geometry (SCG), 1993, 359–368. (Preliminary version of J-25.)
`C-31. M.H. Nodine, M.T. Goodrich, and J.S. Vitter, “Blocking for External Graph Searching,”
`Proc. 12th ACM Symp. on Principles of Database Systems (PODS), 1993, 222–232. (Prelimi-
`nary version of J-26.)
`
`C-32. E.M. Arkin, M.T. Goodrich, J.S.B. Mitchell, D. Mount, and S.S. Skiena, “Point Probe
`Decision Trees for Geometric Concept Classes,” Lecture Notes in Computer Science 709:
`Algorithms and Data Structures (WADS), Springer-Verlag, 1993, 95–106.
`C-33. M.T. Goodrich, J.J. Tsay, D.E. Vengroff, and J.S. Vitter, “External-Memory Computational
`Geometry,” Proc. 34th IEEE Symp. on Foundations of Computer Science (FOCS), 1993,
`714–723.
`C-34. M.T. Goodrich, Y. Matias, and U. Vishkin, “Optimal Parallel Approximation Algorithms
`for Prefix Sums and Integer Sorting,” Proc. 5th ACM-SIAM Symp. on Discrete Algorithms
`(SODA), 1994, 241–250.
`C-35. H. Br¨onnimann and M.T. Goodrich, “Almost Optimal Set Covers in Finite VC-Dimension,”
`Proc. 10th ACM Symp. on Computational Geometry (SCG), 1994, 293–302. (Preliminary version
`
`10
`
`10
`
`SYMC 1004
`
`

`
`of J-21.)
`
`C-36. M.T. Goodrich, “Efficient Piecewise-Linear Function Approximation Using the Uniform Met-
`ric,” Proc. 10th ACM Symp. on Computational Geometry (SCG), 1994, 322–331. (Preliminary
`version of J-20.)
`
`C-37. M.J. Atallah, M.T. Goodrich, and K. Ramaiyer, “Biased Finger Trees and Three-Dimensional
`Layers of Maxima,” Proc. 10th ACM Symp. on Computational Geometry (SCG), 1994, 150–
`159.
`C-38. M.T. Goodrich, J.S.B. Mitchell, and M.W. Orletsky, “Practical Methods for Approximate
`Geometric Pattern Matching under Rigid Motions,” Proc. 10th ACM Symp. on Computa-
`tional Geometry (SCG), 1994, 103–112. (Preliminary version of J-37.)
`C-39. N.M. Amato, M.T. Goodrich, E.A. Ramos, “Parallel Algorithms for Higher-Dimensional
`Convex Hulls,” Proc. 35th IEEE Symp. on Foundations of Computer Science (FOCS), 1994,
`683–694.
`C-40. P.J. Tanenbaum, M.T. Goodrich, and E.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-Verlag, 1994, 234–245.
`C-41. Y.J. Chiang, M.T. Goodrich, E.F. Grove, R. Tamassia, D.E. Vengroff, and J.S. Vitter,
`“External-Memory Graph Algorithms,” 6th ACM-SIAM Symp. on Discrete Algorithms
`(SODA), 1995, 139–149.
`C-42. N.M. Amato, M.T. Goodrich, and E.A. Ramos, “Computing Faces in Segment and Simplex
`Arrangements,” 27th ACM Symp. on Theory of Computing (STOC), 1995, 672–682.
`C-43. P. Callahan, M.T. Goodrich, and K. Ramaiyer, “Topology B-Trees and Their Applications,”
`1995 Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer
`Science 955, Springer-Verlag, 381–392.
`C-44. G. Das and M.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-Verlag, 74–85. (Preliminary version
`of J-28.)
`
`“Fixed-Dimensional Parallel Linear Programming via Relative -
`C-45. M.T. Goodrich,
`Approximations,” 7th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1996, 132–141.
`(Preliminary version of J-32.)
`C-46. M. Chrobak, M.T. Goodrich, and R. Tamassia, “Convex Drawings of Graphs in Two and
`Three Dimensions,” 12th ACM Symp. on Computational Geometry (SCG), 1996, 319–328.
`C-47. M.T. Goodrich, “Communication-Efficient Parallel Sorting,” 28th ACM Symp. on Theory of
`Computing (STOC), 1996, 247–256. (Preliminary version of J-38.)
`C-48. T. Chan, M.T. Goodrich, S.R. Kosaraju, and R. Tamassia, “Optimizing Area and Aspect
`Ratio in Straight-Line Ortho