• Book chapters
• Information Security Algorithms
• Parallel, Distributed, and External-Memory Algorithms
• Graph and Network Algorithms
• Data Structures and Algorithms
• Geometric Algorithms

Book Chapters

• Ch-4. M.T. Goodrich and K. Ramaiyer, Geometric data Structures, in J.-R. Sack and J. Urrutia, eds., Handbook of Computational Geometry, 463-489, Elsevier Science, 2000.
• Ch-5. M.T. Goodrich and R. Tamassia, Simplified Analyses of Randomized Algorithms for Searching, Sorting, and Selection, in S. Rajasekaran, P.M. Pardalos, J.H. Reif, and J.D.P. Rolim, eds., Handbook of Randomization, Kluwer Academic Publishers, 2001, Vol. 1, 23-34.
• Ch-6/Ch-3. M.T. Goodrich, Parallel Algorithms in Geometry, in J.E. Goodman and J. O'Rourke, eds., Handbook of Discrete and Computational Geometry, Second Edition, Chapman and Hall/CRC Press, 953-967, 2004.
• Ch-7. C. Duncan and M.T. Goodrich, Approximate Geometric Query Structures, Handbook of Data Structures and Applications, Chapman and Hall/CRC Press, 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 and Hall/CRC Press, 43-1--43-22, 2005.
• Ch-9. C.A. Duncan and M.T. Goodrich, Planar Orthogonal and Polyline Drawing Algorithms, Handbook of Graph Drawing and Visualization, Chapman & Hall/CRC Press, Inc., to appear.
• Ch-10. 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.

Information Security Algorithms

• C-80. G. Ateniese, B. de Medeiros, and M.T. Goodrich, TRICERT: A Distributed Certified E-mail Scheme, Network and Distributed Systems Security Symposium, 2001, 47-56.
• C-83. M.T. Goodrich, R. Tamassia, and A. Schwerin, Implementation of an Authenticated Dictionary with Skip Lists and Commutative Hashing, DARPA Information Survivability Conference & Exposition II (DISCEX II), IEEE Press, 2001, 68-82.
• C-85. A. Anagnostopoulos, M. T. Goodrich, and R. Tamassia, Persistent Authenticated Dictionaries and Their Applications, Proc. Information Security Conference (ISC 2001), Lecture Notes in Computer Science, vol. 2200, Springer-Verlag, pp. 379-393, 2001.
• C-86. M. T. Goodrich, and R. Tamassia and J. Hasic, An Efficient Dynamic and Distributed Cryptographic Accumulator, Proc. Information Security Conference (ISC 2002) Lecture Notes in Computer Science, vol. 2433, Springer-Verlag, pp. 372-388, 2002.
• C-90. M. T. Goodrich, R. Tamassia, N. Triandopoulos and R. Cohen, Efficient Authenticated Data Structures for Graph Connectivity and Geometric Search Problems, Algorithmica, to appear. Earlier version appeared in RSA, Cryptographers' Track, 295-313, Springer, LNCS 2612, 2003.
• C-91. M. T. Goodrich, M. Shin, R. Tamassia, W. H. Winsborough, Authenticated dictionaries for fresh attribute credentials, Proc. Trust Management Conference, 332-347, Springer, LNCS 2692, 2003.
• C-94. A. Bagchi, A. Chaudhary, M.T. Goodrich, and S. Xu, Constructing disjoint paths for secure communication. 17th International Symposium on Distributed Computing (DISC), 181-195, 2003.
• C-98. M. T. Goodrich, J. Z. Sun, and R. Tamassia, Efficient Tree-Based Revocation in Groups of Low-State Devices, CRYPTO 2004, Springer, LNCS 3152, 511-527, 2004.
• C-100. M.J. Atallah, K.B. Frikken, M.T. Goodrich, and R. Tamassia, Secure Biometric Authentication for Weak Computational Devices, 9th Int. Conf. on Financial Cryptograpy and Data Security, 357-371, 2005.
• C-101. M.T. Goodrich, Leap-Frog Packet Linking and Diverse Key Distributions for Improved Integrity in Network Broadcasts, IEEE Symposium on Security and Privacy (SSP), 196-207, 2005.
• C-103. M.J. Atallah, M.T. Goodrich, and R. Tamassia, Indexing Information for Data Forensics, 3rd Applied Cryptography and Network Security Conference (ACNS), Lecture Notes in Computer Science 3531, Springer, 206-221, 2005.
• C-104. W. Du and M.T. Goodrich, Searching for High-Value Rare Events with Uncheatable Grid Computing, 3rd Applied Cryptography and Network Security Conference (ACNS), Lecture Notes in Computer Science 3531, Springer, 122-137, 2005.
• C-108. M.T. Goodrich, R. Tamassia, and D. Yao, Accredited DomainKeys: A Service Architecture for Improved Email Validation, Conference on Email and Anti-Spam (CEAS), 2005.
• C-112. M.T. Goodrich, M. Sirivianos, J. Solis, G. Tsudik, E. Uzun, Loud And Clear: Human-Verifiable Authentication Based on Audio, 26th IEEE Int. Conference on Distributed Computing Systems (ICDCS), 2006.
• C-113. M.T. Goodrich, R. Tamassia, and D. Yao, Notarized Federated Identity Management for Web Services, 20th IFIP WG Working Conference on Data and Application Secuirity (DBSec), Springer, LNCS 4127, 133-147, 2006.
• J-61. M.T. Goodrich, Probabalistic Packet Marking for Large-Scale IP Traceback, IEEE/ACM Transactions on Networking, 16(1), 15--24, 2008. Preliminary version (C-89) appeared at 9th ACM Conf. on Computer and Communications Security (CCS), 2002, 117-126.
• C-115. Y. Cho, L. Bao and M.T. Goodrich, LAAC: A Location-Aware Access Control Protocol, In Proc. of International Workshop on Ubiquitous Access Control (IWUAC), San Jose, CA, July 17, 2006.
• J-64. M.T. Goodrich, Pipelined Algorithms to Detect Cheating in Long-Term Grid Computations, Theoretical Computer Science, vol. 408, 199-207, 2008.
• C-131. M.T. Goodrich, The Mastermind Attack on Genomic Data, 30th IEEE Symp. on Security and Privacy, 2009.
• C-133. M.T. Goodrich, R. Tamassia, and N. Triandopoulos, J.Z. Sun, Reliable Resource Searching in P2P Networks, 5th International ICST Conference on Security and Privacy in Communication Networks (SecureComm), Lecture Notes of ICST, Springer, 2009.
• C-139. W. Du, M.T. Goodrich, T. Luo, and G. Wang, Bureaucratic Protocols for Secure Two-Party Sorting, Selection, and Permuting, 5th ACM Symposium on Information, Computer and Communications Security, 2010.
• C-145. A.U. Asuncion and M.T. Goodrich, Turning Privacy Leaks into Floods: Surreptitious Discovery of Social Network Friendships and Other Sensitive Binary Attribute Vectors, Proc. Workshop on Privacy in the Electronic Society (WPES), held in conjunction with the 17th ACM Conference on Computer and Communications Security (CCS), 2010.
• C-148. D. Eppstein, M.T. Goodrich, R. Tamassia, Privacy-Preserving Data-Oblivious Geometric Algorithms for Geographic Data, Proc. 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS), 2010.

Parallel, Distributed, and External-Memory Algorithms

• 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-24. M.T. Goodrich and S.R. Kosaraju. Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation, J. ACM, 43(2), 1996, 331-361.
• 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'Dunlaing, A Nearly Optimal Deterministic Parallel Voronoi Diagram Algorithm, Algorithmica, 16, 1996, 569-617.
• M.T. Goodrich, J.J. Tsay, D.E. Vengroff, J.S. Vitter, External-Memory Computational Geometry , 34th IEEE Symp. on Foundations of Computer Science (FOCS), 1993, 714-723.
• 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.
• Y.J. Chiang, M.T. Goodrich, E.F. Grove, R. Tamassia, D.E. Vengroff, J.S. Vitter, External-Memory Graph Algorithms, 6th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1995.
• 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.
• N.M. Amato, M.T. Goodrich, E.A. Ramos. Computing Faces in Segment and Simplex Arrangements, Proc. 27th ACM Symp. on Theory of Computing (STOC), 1995, 672-682.
• 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-32. M.T. Goodrich and E.A. Ramos, Bounded-Independence Derandomization of Geometric Partitioning with Applications to Parallel Fixed-Dimensional Linear Programming, Discrete and Computational Geometry, 18, 1997, 397-420. Preliminary version (C-45) appeared in 7th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1996, 132-141.
• 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, March/April 1999, 2-10.
Preliminary version (C-53) appeared in 13th ACM Symp. on Computational Geometry (SCG), 1997.
• J-38. M.T. Goodrich, Communication-Efficient Parallel Sorting, SIAM Journal on Computing, 29(2), 1999, 416-432. Preliminary version (C-47) appeared in 28th ACM Symp. on Theory of Computing (STOC), 1996.
• C-49. M.T. Goodrich, Randomized Fully-Scalable BSP Techniques for Multi-Searching and Convex Hull Construction, 8th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1997.
• O-6. T.H. Cormen and M.T. Goodrich, A Bridging Model for Parallel Computation, Communication, and I/O,ACM Computing Surveys, 28A(4), December 1996.
• C-84. A. Bagchi, A. Chaudhary, R. Carg, M.T. Goodrich, and V. Kumar, Seller-Focused Algorithms for Online Auctioning, 2001 Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science 2125, Springer-Verlag, 2001, 135-147.
• C-105. L. Arge, D. Eppstein, and M.T. Goodrich, Skip-Webs: Efficient Distributed Data Structures for Multi-Dimensional Data Sets, 24th ACM Symp. on Principles of Distributed Computing (PODC), 2005.
• C-111. M.T. Goodrich, M.J. Nelson, and J.Z. Sun, The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree Distributed Data Structure, 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), 384-393, 2006.
• C-114. M.T. Goodrich and D.S. Hirschberg, Efficient Parallel Algorithms for Dead Sensor Diagnosis and Multiple Access Channels, 18th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), 118-127, 2006.
• 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, 18(10), 1352-1367, 2006.
• C-126. L. Arge, M.T. Goodrich, M. Nelson, and N. Sitchinava, Fundamental Parallel Algorithms for Private-Cache Chip Multiprocessors, Proc. 20th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), 2008, 197-206.
• C-138. L. Arge, M.T. Goodrich, and N. Sitchinava, Parallel External Memory Graph Algorithms, 24th IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2010.
• O-12. M.T. Goodrich, Simulating Parallel Algorithms in the MapReduce Framework with Applications to Parallel Computational Geometry, Second Workshop on Massive Data Algorithmics (MASSIVE), 2010.

Graph and Network Algorithms

• J-22. M.T. Goodrich. Planar Separators and Parallel Polygon Triangulation. Journal of Computer & System Sciences, 51(3), 1995, 374-389.
• J-25. A. Garg, M.T. Goodrich, and R. Tamassia. Planar Upward Tree Drawings with Optimal Area. International Journal of Computational Geometry and Applications, 6(3), 1996, 333-356.
• 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.
• J-39. C.A. Duncan, M.T. Goodrich, and S. Kobourov, Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs, Journal of Graph Algorithms and Applications, 4(3), 2000, 19-46. Preliminary version (C-61) appeared in Proceedings of the Sixth Symposium on Graph Drawing, 1998.
• J-40. M.T. Goodrich and C.G. Wagner, A framework for drawing planar graphs with curves and polylines, Journal of Algorithms, vol. 37, 399-421, 2000. Preliminary version (C-60) appeared in 6th Int. Symp. on Graph Drawing (GD), LNCS 1547, Springer-Verlag, 1998, 153-166.
• J-43. C.C. Cheng, C. A. Duncan, M. T. Goodrich, and S. G. Kobourov, Drawing Planar Graphs with Circular Arcs, Discrete & Computational Geometry 25: 405-418 (2001). Preliminary version (C-69) appeared in 7th Int. Symp. on Graph Drawing (GD), LNCS 1731, Springer-Verlag, 1999, 117-126..
• 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, Volume 23, Issue 2 , September 2002, Pages 153-162. Preliminary version (C-48) appeared in Graph Drawing '96, 1996.
• J-48. C. A. Duncan, M. T. Goodrich, and S. G. Kobourov, Planarity-Preserving Clustering and Embedding for Large Planar Graphs, CGTA: Computational Geometry: Theory and Applications 24(2), 95-114, 2003. Preliminary version (C-70) appeared in 7th Int. Symp. on Graph Drawing (GD), Lecture Notes in Computer Science 1731, Springer-Verlag, 1999, 186-196.
• C-96. F. Brandenberg, D. Eppstein, M.T. Goodrich, S.G. Kobourov, G. Liotta, P. Mutzel, Selected Open Problems in Graph Drawing, 11th Int. Symp. on Graph Drawing (GD), LNCS, Springer-Verlag, 2003.
• J-50. G. Barequet, M.T. Goodrich, and C. Riley, Drawing Planar Graphs with Large Vertices and Thick Edges, J. of Graph Algorithms and Applications (JGAA), 8(1), 3-20, 2004. Preliminary version (C-93) appeared in 2003 Workshop and Data Structures and Algorithms (WADS), LNCS 2748, 2003, 281-293.
• 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 (CGTA), 29(1), 3-18, 2004. Preliminary version (C-79) appeared in Graph Drawing 2000, 211-221.
• 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), 2005. Preliminary version (C-95) appeared in 11th Int. Symp. on Graph Drawing (GD), LNCS 2912, 2003, 1-12.
• J-58. D. Eppstein, M.T. Goodrich, and J.Y. Meng, Confluent Layered Drawings, Algorithmica, 47(4), 439--452, 2007. Preliminary version (C-99) appeared in 12th Int. Symp. on Graph Drawing (GD), Springer, Lecture Notes in Computer Science 3383, 184-194, 2004.
• C-109. M.T. Goodrich, G.S. Lueker, and J.Z. Sun, C-Planarity of Extrovert Clustered Graphs, Graph Drawing, 211-222, 2005.
• C-110. D. Eppstein, M.T. Goodrich, J.Y. Meng, Delta-Confluent Drawings, Graph Drawing, 165-176, 2005.
• C-116. M.B. Dillencourt, D. Eppstein, and M.T. Goodrich, Choosing Colors for Geometric Graphs via Color Space Embeddings, Graph Drawing (GD), 2006.
• C-127. D. Eppstein and M.T. Goodrich, Succinct Greedy Graph Drawing in the Hyperbolic Plane, Graph Drawing 2008.
• C-134. C.A. Duncan, M.T. Goodrich, S.G. Kobourov, Planar Drawings of Higher-Genus Graphs, Proc. 17th Int. Symp. on Graph Drawing (GD), Lecture Notes in Computer Science, Springer, 2009.
• C-135. D. Eppstein, M.T. Goodrich, L. Trott, Going Off-road: Transversal Complexity in Road Networks, Proc. 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS), 2009.
• C-136. M.T. Goodrich and Darren Strash, Succinct Greedy Geometric Routing in the Euclidean Plane, 13th Int. Symp. on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science, Springer, 2009.
• C-140. M.T. Dickerson, M.T. Goodrich, and T.D. Dickerson, Round-Trip Voronoi Diagrams and Doubling Density in Geographic Networks, 7th Int. Symp. on Voronoi Diagrams in Science and Engineering (ISVD), IEEE Press, 2010.
• C-142. C.A. Duncan, D. Eppstein, M.T. Goodrich, S. Kobourov, and M. Nollenburg, Lombardi Drawings of Graphs, Proc. 18th Int. Symp. on Graph Drawing (GD), 2010.
• C-143. E. Wolf-Chambers, D. Eppstein, M.T. Goodrich, and M. Loffler, Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area, Proc. 18th Int. Symp. on Graph Drawing (GD), 2010.
• C-144. C.A. Duncan, D. Eppstein, M.T. Goodrich, S. Kobourov, and M. Nollenburg, Drawing Trees with Perfect Angular Resolution and Polynomial Area, Proc. 18th Int. Symp. on Graph Drawing (GD), 2010.
• C-146. D. Eppstein, M.T. Goodrich, D. Strash, and L. Trott, Extended Dynamic Subgraph Statistics Using h-Index Parameterized Data Structures, Proc. 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2010.

Data Structures and Algorithms

• J-23. M.T. Goodrich, M. Ghouse, and J. Bright, Sweep Methods for Parallel Computational Geometry, Algorithmica, 15(2), 1996, 126-153. Preliminary version (C-17) appeared in 2nd ACM Symp. on Parallel Algorithms and Architectures (SPAA), 1990, 280-289.
• J-29. M.T. Goodrich and R. Tamassia. Dynamic Ray Shooting and Shortest Paths via Balanced Geodesic Triangulations. J. Algorithms, 23, 1997, 51-73.
• C-51. M.T. Goodrich, M. Orletsky, and K. Ramaiyer, Methods for Achieving Fast Query Times in Point Location Data Structures, 8th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1997.
• J-35. M.T. Goodrich and R. Tamassia. Dynamic Trees and Dynamic Point Location, SIAM J. Comput., 28(2), 1999, 612-636.
• J-41. C. A. Duncan, M. T. Goodrich, and S. G. Kobourov, Balanced Aspect Ratio Trees: Combining the Advantages of k-d Trees and Octrees, Journal of Algorithms 38:303-333, 2001. Preliminary version (C-65) appeared at ACM-SIAM Symp. on Discrete Algorithms (SODA), 1999, 300-309.
• C-71. M.T. Goodrich and J.G. Kloss II, "Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences," 1999 Workshop on Algorithms and Data Structures (WADS), 1999, 205-216.
• C-72. M.T. Goodrich, Competitive tree-structured dictionaries, 11th ACM/SIAM Symp. on Discrete Algorithms (SODA), 2000, 705-706.
• C-77. A.L. Buchsbaum, M.T. Goodrich, J.R. Westbrook, Range searching over tree cross products, 8th European Symp. on Algorithms (ESA), 120-131, 2000.
• C-78. C.A. Duncan, M.T. Dickerson, and M.T. Goodrich, k-D Trees are Better When Cut on the Longest Side, 8th European Symposium on Algorithms (ESA), LNCS 1879, Springer-Verlag, 2000, 179-190.
• 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.
• C-107. A. Chaudhary and M.T. Goodrich, Balanced Aspect Ratio Trees Revisited, Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science 3608, Springer, 2005.
• J-54. A. Bagchi, A.L. Buchsbaum, and M.T. Goodrich, Biased Skip Lists Algorithmica, 42(1), 31-48, 2005. Preliminary version (C-88) appeared in Algorithms and Computation : 13th International Symposium, ISAAC 2002, 1-13.
• J-57. D. Eppstein, M.T. Goodrich, and J.Z. Sun, The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data, Int. Journal on Computational Geometry and Applications, 18(1/2), 131--160, 2008. Preliminary version (C-102) appeared in 21st ACM Symp. on Computational Geometry (SCG), 2005.
• J-60. D. Eppstein, M.T. Goodrich, and D. Hirschberg, Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes, SIAM Journal on Computing, accepted for publication. Preliminary vesion (C-106) appeared in Workshop on Algorithms and Data Structures (WADS), LNCS 3608, Springer, 2005, 86-98.
• C-120. D. Eppstein and M.T. Goodrich, Space-Efficient Straggler Identification in Round-Trip Data Streams via Newton's Identities and Invertible Bloom Filters, Proc. Workshop on Algorithms and Data Structures (WADS), LNCS 4619, Springer, pp. 638-649, 2007.
• C-132. W. Du, D. Eppstein, M.T. Goodrich, and G.S. Lueker, On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem, Proc. Algorithms and Data Structures Symposium (formerly WADS), LNCS, Springer, 2009.
• J-67. M.T. Goodrich, On the Algorithmic Complexity of the Mastermind Game with Black-Peg Results, Information Processing Letters, 2009.
• C-137. M.T. Goodrich, Randomized Shellsort: A Simple Oblivious Sorting Algorithm, 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010.
• C-147. M.T. Goodrichand D. Strash, Priority Range Trees, Proc. 21st International Symposium on Algorithms and Computation (ISAAC), 2010.
• C-149. M.T. Goodrich, Spin-the-bottle Sort and Annealing Sort: Oblivious Sorting via Round-robin Random Comparisons, 8th annual Workshop on Analytic Algorithmics and Combinatorics (ANALCO), in conjunction with the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.

Geometric Algorithms

• 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-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-20. M.T. Goodrich. Efficient Piecewise-Linear Function Approximation Using the Uniform Metric, Discrete and Computational Geometry, 14, 1995, 445-462. Preliminary version appeared in Proc. 10th ACM Symp. on Computational Geometry (SCG), 1994, 322-331.
• J-21. H. Bronnimann and M.T. Goodrich. Almost Optimal Set Covers in Finite VC-Dimension, Discrete and Computational Geometry, 14, 1995, 463.479. Preliminary version (C-35) appeared in Proc. 10th ACM Symp. on Computational Geometry (SCG), 1994, 293-302.
• 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. Preliminary version appeared in 1995 Workshop on Algorithms and Data Structures (WADS).
• 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. Preliminary version appeared in Proc. 5th Canadian Conference on Computational Geometry (CCCG), 1993, 151-156.
• C-50. C.A. Duncan, M.T. Goodrich, and E.A. Ramos, Efficient Approximation and Optimization Algorithms for Computational Metrology, 8th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1997.
• C-52. M.T. Goodrich, L.J. Guibas, J. Hershberger, P.J. Tanenbaum, Snap Rounding Line Segments Efficiently in Two and Three Dimensions, Proc. 13th ACM Symp. on Computational Geometry (SCG), 1997.
• J-33. M.T. Goodrich. An Improved Ray Shooting Method for Constructive Solid Geometry Models via Tree Contraction. International Journal of Computational Geometry and Applications, 8(1), 1998, 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, vol. 11 (3-4), pp. 125-141, 1998. Preliminary version (C-55) appeared in Proc. 5th Workshop on Algorithms and Data Structures (WADS), LNCS 1272, 378-391, 1997.
• C-54. G. Barequet, A. Briggs, M. Dickerson, C. Dima, and M.T. Goodrich, Animating the Polygon-Offset Distance Function, 13th ACM Symp. on Computational Geometry (SCG), 1997, 479-480, and the Video Review for the 13th ACM Symp. on Computational Geometry.
• 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 (PAMI), 21(4), 1999, 371-379. A preliminary version (C-38) appeared in ACM Symp. on Computational Geometry, 1994, 103-112.
• C-68. G. Barequet, C. Duncan, M.T. Goodrich, S. Kumar, M. Pop, Efficient Perspective-Accurate Silhouette Computation, 15th ACM Symp. on Computational Geometry (SCG), 1999, 417-418, and the Video Review for the 15th ACM Symp. on Computational Geometry (SCG).
• C-73. N.M. Amato, M.T. Goodrich, E.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.
• J-42. G. Barequet, M.T. Dickerson, and M.T. Goodrich, Voronoi diagrams for polygon-offset distance functions, Discrete and Computational Geometry, vol. 25 (2), pp. 271-291, 2001. Preliminary version (C-56) appeared at Workshop on Algorithms and Data Structures (WADS), 1997, LNCS, 200-209.
• C-82. M. Pop, G. Barequet, C.A. Duncan, M.T. Goodrich, W. Hwang, and S. Kumar, Efficient Perspective-Accurate Silhouette Computation and Applications, 17th ACM Symp. on Computational Geometry (SCG), 2001, 60-68.
• 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. Preliminary version (C-76) appeared in 16th ACM Symp. on Computational Geometry (SCG), 2000, 201-212.
• J-46. G. Barequet, D.Z. Chen, O. Daescu, M.T. Goodrich, and J. Snoeyink, Efficiently approximating polygonal paths in three and higher dimensions, Algorithmica, vol. 33 (2), pp. 150-167, 2002. Preliminary version (C-59) appeared in ACM Symp. on Computational Geometry (SoCG), 317-326, 1998.
• J-49. A.L. Buchsbaum and M.T. Goodrich, Three-Dimensional Layers of Maxima, Algorithmica, 39, 275-286, 2004. Preliminary version (C-87) appeared in 10th Annual European Symposium (ESA), 2002, LNCS 2461.
• J-51. G. Barequet, M.T. Goodrich, A. Levi-Steiner, and D. Steiner, Contour Interpolation by Straight Skeletons, Graphical Models (GM), 66(4), 245-260, 2004. Preliminary version (C-92) appeared in 14th ACM-SIAM Symp. on Discrete Algorithms (SODA), 119-127, 2003.
• 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-59. A. Bagchi, A. Chaudhary, D. Eppstein, and M.T. Goodrich, Deterministic sampling and range counting in geometric data streams, ACM Transactions on Algorithms, accepted for publication. Preliminary version (C-97) appeared in 12th ACM Annual Symposium on Computational Geometry (SoCG), 2004.
• C-117. D. Eppstein, M.T. Goodrich, and Sitchinava, Guard Placement for Wireless Localization, Proc. 23rd ACM Symposium on Computational Geometry (SCG), 27-36, 2007.
• C-119. M.J. Atallah, M. Blanton, M.T. Goodrich, and S. Polu, Discrepancy-Sensitive Dynamic Fractional Cascading, Dominated Maxima Searching, and 2-d Nearest Neighbors in Any Minkowski Metric, Proc. Workshop on Algorithms and Data Structures (WADS), LNCS 4619, Springer, pp. 114-126, 2007.
• C-123. D. Eppstein, M.T. Goodrich, E. Kim, and R. Tamstorf, "Approximate Topological Matching of Quadrilateral Meshes," Proc. IEEE Int. Conf. on Shape Modeling and Applications (SMI), 2008, 83--92.
• C-124. G. Bareqet, D. Eppstein, M.T. Goodrich, and A. Waxman, "Straight Skeletons of Three-Dimensional Polyhedra," Proc. 16th European Symposium on Algorithms (ESA), 2008.
• J-65. D. Eppstein, M.T. Goodrich, E. Kim, and R. Tamstorf, "Motorcycle Graphs: Canonical Quad Mesh Partitioning," Proc. 6th European Symposium on Geometry Processing (SGP), 2008.
• C-128. D. Eppstein and M.T. Goodrich, Studying (Non-Planar) Road Networks Through an Algorithmic Lens, Proc. 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM GIS), 2008, 125-134. Best paper award.
• C-130. D. Eppstein, M.T. Goodrich, and D. Strash, Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings, SODA 2009.
• C-141. M.T. Dickerson, D. Eppstein, and M.T. Goodrich, Cloning Voronoi Diagrams via Retroactive Data Structures, 18th European Symposium on Algorithms (ESA), 2010.