Straight Skeletons of Three-Dimensional Polyhedra (2009)
Gill Barequet, Michael T. Goodrich, Amir Vaxman
Abstract. This paper studies the straight skeleton of polyhedra in three dimensions. We first address voxel-based polyhedra (polycubes), formed as the union of a collection of cubical (axis-aligned)...
The Visual Computer manuscript No. (will be inserted by the editor) (2009)
Michael T. Goodrich, Ethan Kim, Rasmus Tamstorf
Abstract In this paper, we study the problem of approximate topological matching for quadrilateral meshes, that is, the problem of finding as large a set as possible of matching portions of two...
Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings (2009)
Darren Strash, Michael T. Goodrich
We provide linear-time algorithms for geometric graphs with sublinearly many crossings. That is, we provide algorithms running in O(n) time on connected geometric graphs having n vertices and k...
Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings (2009)
Darren Strash, Michael T. Goodrich
We provide linear-time algorithms for geometric graphs with sublinearly many crossings. That is, we provide algorithms running in O(n) time on connected geometric graphs having n vertices and k...
Int. J. Security and Networks, Vol. 4, Nos. 1/2, 2009 57 Using (2009)
Michael T. Goodrich, Michael Sirivianos, John Solis, Claudio Soriente, Gene Tsudik, Ersin Uzun
audio in secure device pairing
Motorcycle Graphs: Canonical Quad Mesh Partitioning (2009)
Pierre Alliez, Szymon Rusinkiewicz, Michael T. Goodrich, Ethan Kim, Rasmus Tamstorf
We describe algorithms for canonically partitioning semi-regular quadrilateral meshes into structured submeshes, using an adaptation of the geometric motorcycle graph of Eppstein and Erickson to quad...
Society. TECHNICAL ACHIEVEMENT AWARD Each year, the IEEE Computer Society selects several (2009)
sponsors an active and prestigious awards program as part of its mission to promote the free exchange of ideas among computer professionals around the world and to recognize its members for their...
Notarized Federated Identity Management for Web Services ⋆ (2009)
Michael T. Goodrich, Roberto Tamassia, Danfeng Yao
Abstract. We propose a notarized federated identity management model that supports efficient user authentication when providers are unknown to each other. Our model introduces a notary service, owned...
Going Off-road: Transversal Complexity in Road Networks (2009)
Eppstein, David, Goodrich, Michael T., Trott, Lowell
A geometric graph is a graph embedded in the plane with vertices at points and edges drawn as curves (which are usually straight line segments) between those points. The average transversal...
Randomized Shellsort: A Simple Oblivious Sorting Algorithm (2009)
In this paper, we describe randomized Shellsort--a simple, randomized, data-oblivious version of the Shellsort algorithm that always runs in O(n log n) time and, as we show, succeeds in sorting any...
Efficient Authenticated Data Structures for Graph Connectivity and Geometric Search Problems (2009)
Goodrich, Michael T., Tamassia, Roberto, Triandopoulos, Nikos
Authenticated data structures provide cryptographic proofs that their answers are as accurate as the author intended, even if the data structure is being controlled by a remote untrusted host. We...
Planar Drawings of Higher-Genus Graphs (2009)
Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
In this paper, we give polynomial-time algorithms that can take a graph G with a given combinatorial embedding on an orientable surface S of genus g and produce a planar drawing of G in R^2, with a...
Pipelined Algorithms to Detect Cheating in Long-Term Grid Computations (2009)
This paper studies pipelined algorithms for protecting distributed grid computations from cheating participants, who wish to be rewarded for tasks they receive but don't perform. We present improved...
The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree P2P Relay Structure (2009)
Goodrich, Michael T., Nelson, Michael J., Sun, Jonathan Z.
We present a distributed data structure, which we call the rainbow skip graph. To our knowledge, this is the first peer-to-peer data structure that simultaneously achieves high fault tolerance,...
Goodrich, Michael T., Hirschberg, Daniel S.
We study group-testing algorithms for resolving broadcast conflicts on a multiple access channel (MAC) and for identifying the dead sensors in a mobile ad hoc wireless network. In group-testing...
An Efficient Dynamic and Distributed RSA Accumulator (2009)
Goodrich, Michael T., Tamassia, Roberto, Hasic, Jasminka
We show how to use the RSA one-way accumulator to realize an efficient and dynamic authenticated dictionary, where untrusted directories provide cryptographically verifiable answers to membership...
On the Algorithmic Complexity of the Mastermind Game with Black-Peg Results (2009)
In this paper, we study the algorithmic complexity of the Mastermind game, where results are single-color black pegs. This differs from the usual dual-color version of the game, but better...
Atallah, Mikhail J., Blanton, Marina, Goodrich, Michael T., Polu, Stanislas
This paper studies a discrepancy-sensitive approach to dynamic fractional cascading. We provide an efficient data structure for dominated maxima searching in a dynamic set of points in the plane,...
The Mastermind Attack on Genomic Data (2009)
In this paper, we study the degree to which a genomic string, $Q$, leaks details about itself any time it engages in comparison protocols with a genomic querier, Bob, even if those protocols are...
Du, Wenliang, Eppstein, David, Goodrich, Michael T., Lueker, George S.
We study the problem of abstracting a table of data about individuals so that no selection query can identify fewer than k individuals. We show that it is impossible to achieve arbitrarily good...
Foundational Algorithms for Computational Distributed Robot Swarms (2009)
Michael T. Goodrich, Nodari Sitchinava
In this paper, we study discrete swarm algorithms, where mobile robots (or “mobots”) move around interacting in an environment to solve computational problems. This work extends recent work on...
Parallel External Memory Graph Algorithms (2009)
Lars Arge, Michael T. Goodrich, Nodari Sitchinava
In this paper, we study parallel I/O efficient graph algorithms in the Parallel External Memory (PEM) model, one of the private-cache chip multiprocessor (CMP) models. We study the fundamental...
Accredited DomainKeys: A Service Architecture for Improved Email Validation ∗ (2008)
goodrich(at)acm.org We present an architecture called Accredited DomainKeys, which builds on the DomainKeys email authentication infrastructure to address the following questions: • “Did the...
TRICERT: A Distributed Certified E-Mail Scheme (2008)
Breno Medeiros, Michael T. Goodrich
ateniese,breno,goodrich¡&cs.jhu.edu In this paper we present protocols for distributed certified e-mail, which use encryption to ensure both confidentiality and fairness. As with other protocols...
Michael T. Goodrich, Edgar A. Ramos
We give fast and efficient methods for constructing... time using linear work on an EREW PRAM.
Succinct Greedy Geometric Routing in R^2 (2008)
Goodrich, Michael T., Strash, Darren
In greedy geometric routing, messages are passed in a network embedded in a metric space according to the greedy strategy of always forwarding messages to nodes that are closer to the destination. In...
Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings (2008)
Eppstein, David, Goodrich, Michael T., Strash, Darren
We provide linear-time algorithms for geometric graphs with sublinearly many crossings. That is, we provide algorithms running in O(n) time on connected geometric graphs having n vertices and k...
ABSTRACT The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data (2008)
Michael T. Goodrich, Jonathan Z. Sun
We present a new multi-dimensional data structure, which we call the skip quadtree (for point data in R 2) or the skip octree (for point data in R d, with constant d> 2). Our data structure...
Studying (Non-Planar) Road Networks Through an Algorithmic Lens (2008)
Eppstein, David, Goodrich, Michael T.
This paper studies real-world road networks from an algorithmic perspective, focusing on empirical studies that yield useful properties of road networks that can be exploited in the design of fast...
Abstract The Rainbow Skip Graph: A Fault-Tolerant Constant-Degree Distributed Data Structure (2008)
Michael T. Goodrich, Michael J. Nelson, Jonathan Z. Sun
We present a distributed data structure, which we call the rainbow skip graph. To our knowledge, this is the first peer-to-peer data structure that simultaneously achieves high fault-tolerance,...
Stina Bridgeman, Michael T. Goodrich
In this paper we present a package for the creation of
Chapter 16 Fixed-Dimensional Parallel Linear Programming via Relative c-Approximations (2008)
We show that linear programming in IRd can be solved deterministically in O((loglogn)d) time using linear work in the PRAM model of computation, for any fixed constant d. Our method is developed for...
Nancy M. Amato, Michael T. Goodrich
We describe two deterministic algorithms for constructing the arrangement determined by a set of (algebraic) curve segments in the plane. They both use a divide-and-conquer approach based on...
Succinct Greedy Graph Drawing in the Hyperbolic Plane (2008)
Eppstein, David, Goodrich, Michael T.
We describe an efficient method for drawing any n-vertex simple graph G in the hyperbolic plane. Our algorithm produces greedy drawings, which support greedy geometric routing, so that a message M...
Straight Skeletons of Three-Dimensional Polyhedra (2008)
Barequet, Gill, Eppstein, David, Goodrich, Michael T., Vaxman, Amir
This paper studies the straight skeleton of polyhedra in three dimensions. We first address voxel-based polyhedra (polycubes), formed as the union of a collection of cubical (axis-aligned) voxels. We...
Checking Value-Sensitive Data Structures in Sublinear Space (2008)
Michael T. Goodrich, Jonathan Z. Sun
Abstract. Checking value-sensitive data structures in sublinear space has been an open problem for over a decade. In this paper, we suggest a novel approach to solving it. We show that, in...
ABSTRACT The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data (2008)
Michael T. Goodrich, Jonathan Z. Sun
We present a new multi-dimensional data structure, which we call the skip quadtree (for point data in R 2) or the skip octree (for point data in R d, with constant d> 2). Our data structure...
Balanced Aspect Ratio Trees Revisited (2008)
Amitabh Chaudhary, Michael T. Goodrich
Abstract. Spatial databases support a variety of geometric queries on point data such as range searches, nearest neighbor searches, etc. Balanced Aspect Ratio (BAR) trees are hierarchical space...
DOI: 10.1007/s00453-004-1138-6 Biased Skip Lists 1 (2008)
Amitabha Bagchi, Adam L. Buchsbaum, Michael T. Goodrich
Abstract. We design a variation of skip lists that performs well for generally biased access sequences. Given n items, each with a positive weight wi,1 ≤ i ≤ n, the time to access item i is O(1 +...
Using Randomization in the Teaching of Data Structures and Algorithms Abstract (2008)
goodrichQcs.jhu.edu We describe an approach for incorporating randomiza-tion in the teaching of data structures and algorithms. The proofs we include are quite simple and can easily to Data...
Three-dimensional layers of maxima (2008)
Adam L. Buchsbaum, Michael T. Goodrich
Abstract. We present an O(n log n)-time algorithm to solve the threedimensional layers-of-maxima problem, an improvement over the prior O(n log n log log n)-time solution. A previous claimed O(n log...
Foundational Algorithms for Distributed Robot Swarms (2008)
Michael T. Goodrich, Nodari Sitchinava
In this paper, we study discrete swarm algorithms, where mobile robots (or “mobots”) move around interacting in an environment to solve computational problems. This work extends recent work on...
Delta-Confluent Drawings ⋆ (2008)
Michael T. Goodrich, Jeremy Yu Meng
Abstract. We generalize the tree-confluent graphs to a broader class of graphs called ∆-confluent graphs. This class of graphs and distancehereditary graphs, a well-known class of graphs, coincide....
Choosing Colors for Geometric Graphs via Color Space Embeddings (2008)
Michael B. Dillencourt, Michael T. Goodrich
Abstract. Graph drawing research traditionally focuses on producing geometric embeddings of graphs satisfying various aesthetic constraints. However additional work must still be done to draw a graph...
Graphics, and Image Processing, 44(1):1–29, 1988. (2008)
M. Alexa, J. Behr, D. Cohen-or, S. Fleishman, D. Levin, Rajit L. Bajaj, ...
based contour interpolation. In Proc. 14th Symp. Discrete Algorithms, pages
Michael T Goodrich, John Hershberger, Leonidas J. Guibast
We study the problem of robustly rounding a set S of n line segments in R2 using the snap rounding paradigm. In this paradigm each pixel containing an endpoint or intersection point is called “hot,...
DS: Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes 2005 (2008)
Michael T. Goodrich, Daniel S. Hirschberg
We study practically efficient methods for performing combinatorial group testing. We present efficient non-adaptive and two-stage combinatorial group testing algorithms, which identify the at most d...
Balanced Aspect Ratio Trees Revisited (2008)
Amitabh Chaudhary, Michael T. Goodrich
Abstract. Spatial databases support a variety of geometric queries on point data such as range searches, nearest neighbor searches, etc. Balanced Aspect Ratio (BAR) trees are hierarchical space...
42 PARALLEL ALGORITHMS IN GEOMETRY (2008)
The goal of parallel algorithm design is to develop parallel computational methods that run very fast with as few processors as possible, and there is an extensive literature of such algorithms for...
Stina Bridgeman, Brown Univ, Michael T. Goodrich
We describe a Web-based interactive system, called PILOT, for testing computer science concepts. The strengths of PILOT are its universal access and plat-form independence, its use as an algorithm...
DOI: 10.1007/s00453-004-1082-5 Three-Dimensional Layers of Maxima 1 (2008)
Adam L. Buchsbaum, Michael T. Goodrich
Abstract. We present an O(n log n)-time algorithm to solve the three-dimensional layers-of-maxima problem. This is an improvement over the prior O(n log n log log n)-time solution. A previous claimed...
Mikhail J. Atallah, Marina Blanton, Michael T. Goodrich, Stanislas Polu, École Polytechnique
Abstract. This paper studies a discrepancy-sensitive approach to dynamic fractional cascading. We provide an efficient data structure for dominated maxima searching in a dynamic set of points in the...
DS: Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes 2005 (2008)
David Eppstein, Michael T. Goodrich, S. Hirschberg
Abstract. We study practically efficient methods for performing combinatorial group testing. We present efficient nonadaptive and two-stage combinatorial group testing algorithms, which identify the...
Michael T. Goodrich, Jyh-jong Tsay
In this paper we give new techniques for designing e cient algorithms for computational geometry problems that are too large to be solved in internal memory. We use these techniques to develop...
TRICERT: A Distributed Certified E-Mail Scheme (2008)
Breno Medeiros, Michael T. Goodrich
In this paper we present protocols for distributed certified e-mail, which use encryption to ensure both confidentiality and fairness. As with other protocols for certified e-mail, ours achieve...
Amitabha Bagchi, Amitabh Chaudhary, Michael T. Goodrich, Chen Li, Michal Shmueli-scheuer
Many database applications that need to disseminate dynamic information from a server to various clients can suffer from heavy communication costs. Data caching at a client can help mitigate these...
Notarized Federated Identity Management for Web Services ⋆ (2008)
Michael T. Goodrich, Roberto Tamassia, Danfeng Yao
Abstract. We propose a notarized federated identity management model that supports efficient user authentication when providers are unknown to each other. Our model introduces a notary service, owned...
Specialized Assignments Using L A T E (2008)
Michael T. Goodrich, Stephen G. Kobourov, Roberto Tamassia
Abstract We present SAIL, a package for the creation of Specialized Assignment In LATEX. We describe several features which allow an instructor to create sufficiently different instances of the...
Selected Open Problems in Graph Drawing (2008)
Franz Br, Michael T. Goodrich, Stephen Kobourov, Petra Mutzel
Abstract. In this manuscript, we present several challenging and interesting open problems in graph drawing. The goal of the listing in this paper is to stimulate future research in graph drawing. 1
Notarized Federated Identity Management for Web Services ⋆ (2008)
Michael T. Goodrich, Roberto Tamassia, Danfeng Yao
Abstract. We propose a notarized federated identity management model that supports efficient user authentication when providers are unknown to each other. Our model introduces a notary service, owned...
Amitabha Bagchi, Adam L. Buchsbaum, Michael T. Goodrich
We design a variation of skip lists that performs well for generally biased access sequences. Given n items, each with a positive weight w i , 1 i n, the time to access item i is O 1 + log , where W...
Parameterized Balanced Aspect Ratio Trees (2008)
Amitabh Chaudhary, Michael T. Goodrich
Spatial databases support a variety of geometric queries on point data such as range searches, nearest neighbor searches, etc. Hierarchical space decomposition structures like k-d trees and quad...
Massively parallel algorithms for private-cache chip multiprocessors. Under submission (2008)
Lars Arge, Michael T. Goodrich, Nodari Sitchinava, Michael Nelson
In this paper, we study massively parallel algorithms for private-cache chip multiprocessors (CMPs), focusing on methods for foundational problems that can scale to hundreds or even thousands of...
Succinct greedy graph drawing in the hyperbolic plane (2008)
Abstract. We describe an efficient method for drawing any n-vertex simple graph G in the hyperbolic plane. Our algorithm produces greedy drawings, which support greedy geometric routing, so that a...
Fundamental parallel algorithms for privatecache chip multiprocessors (2008)
Lars Arge, Michael T. Goodrich, Nodari Sitchinava, Michael Nelson
In this paper, we study parallel algorithms for private-cache chip multiprocessors (CMPs), focusing on methods for foundational problems that can scale to hundreds or even thousands of cores. By...
Optimal Parallel Approximation Algorithms for Prefix Sums and Integer Sorting (2007)
Extend Ed, Michael T. Goodrich, Yossi Matias
) Michael T. Goodrich Yossi Matias y Uzi Vishkin z Abstract Parallel prefix computation is perhaps the most frequently used subroutine in parallel algorithms today. Its time complexity on the...
Convex Drawings of Graphs in Two and Three Dimensions (Preliminary Version) (2007)
Marek Chrobak, Michael T. Goodrich, Roberto Tamassia
We provide O(n)-time algorithms for constructing the following types of drawings of n-vertex 3-connected planar graphs: ffl 2D convex grid drawings with (3n) \Theta (3n=2) area under the edge L1...
External-Memory Graph Algorithms (2007)
Appeared In, Michael T. Goodrich, Edward F. Grove, Roberto Tamassia, Darren Erik Vengroff, ...
We present a collection of new techniques for designing and analyzing efficient external-memory algorithms for graph problems and illustrate how these techniques can be applied to a wide variety of...
Convex Drawings of Graphs in Two and Three Dimensions (Preliminary Version) (2007)
Marek Chrobak, Michael T. Goodrich, Roberto Tamassia
We provide O(n)-time algorithms for constructing the following types of drawings of n-vertex 3-connected planar graphs: ffl 2D convex grid drawings with (3n) \Theta (3n=2) area under the edge L 1...
On the Volume and Resolution of 3-Dimensional Convex Graph Drawing (Extended Abstract) (2007)
Marek Chrobak, Michael T. Goodrich, Roberto Tamassia
We address the problem of drawing a 3-connected planar graph as a convex polyhedron in R³. We give an efficient algorithm for producing such a realization using O(n) volume under the...
Topology B-Trees and Their Applications (2007)
Paul Callahan, Michael T. Goodrich, Kumar Ramaiyer
. The well-known B-tree data structure provides a mechanism for dynamically maintaining balanced binary trees in external memory. We present an external-memory dynamic data structure for maintaining...
Area-Efficient Upward Tree Drawings (Extended Abstract) (2007)
Ashim Garg, Michael T. Goodrich, Roberto Tamassia
) Ashim Garg Dept. of Computer Science Brown University Providence, RI 02912--1910 ag@cs.brown.edu Michael T. Goodrich Dept. of Computer Science The Johns Hopkins University Baltimore, MD 21218--2694...
Marek Chrobak, Michael T. Goodrich, Roberto Tamassia
We provide O(n)-time algorithms for constructing the following types of drawings of n-vertex 3-connected planar graphs: ffl 2D convex grid drawings with (3n) \Theta (3n=2) area under the edge L...
TRICERT: A Distributed Certified E-Mail Scheme (2007)
Breno Medeiros, Michael T. Goodrich
In this paper we present protocols for distributed certified e-mail, which use encryption to ensure both confidentiality and fairness. As with other protocols for certified e-mail, ours achieve...
Amitabha Bagchi, Amitabh Chaudhary, Rahul Garg, Michael T. Goodrich
Abstract. In this paper we provide an algorithmic approach to the study of online auctioning. From the perspective of the seller we formalize the auctioning problem as that of designing an...
Roberto Tamassia, Pankaj K. Agarwal, Nancy Amato, Danny Z. Chen, David Dobkin, ...
The proposed research will be in the area of applied algorithms in both the sequential and parallel domains. The focus of this work will be on the design and testing of realistic algorithms for...
Michael T. Goodrich, National Chung Cheng, Darren Erik Vengroff, Jeffrey Scott Vitter
j svcs. duke. edu In this paper, we give new techniques for designing efficient algorithms for computational geometry problems that are too large to be solved in internal memory, and we use these...
Tiered Vectors: Ecient Dynamic Arrays for Rank-Based Sequences (2007)
Abstract. We describe a data structure, the tiered vector, which is an implementation of the Vector ADT that provides O(1=) worst case time performance for rank-based retrieval and O(n) amortized...
Gill Barequet, Danny Z. Chen, Ovidiu Daescu, Michael T. Goodrich, Jack Snoeyink
We present efficient algorithms for solving polygonal-path approximation problems in three and higher dimensions. Given an n-vertex polygonal curve P in IR
TRICERT: A Distributed Certified E-Mail Scheme (2007)
Breno Medeiros, Michael T. Goodrich
In this paper we present protocols for distributed certified e-mail, which use encryption to ensure both confidentiality and fairness. As with other protocols for certified e-mail, ours achieve...
Aris Anagnostopoulos, Michael T. Goodrich, Roberto Tamassia
Abstract. We introduce the notion of persistent authenticated dictionaries, that is, dictionaries where the user can make queries of the type "was element e in set S at time t? "...
We present algorithms for the well-known hidden-line and hidden-surface elimination problems. Our algorithms are optimal in the worst case, and are also able to take advantage of problem instances...
Michael T. Goodrich, Mikhail J. Atallah, Mark H. Overmars
x We present an algorithm for the hidden-surface elimination problem for rectangles, which is also known as window rendering. The time complexity of our algorithm is dependent on both the number of...
Using Randomization in the Teaching of Data Structures and Algorithms (2007)
Michael T. Goodrich, Roberto Tamassia
We describe an approach for incorporating randomization in the teaching of data structures and algorithms. The proofs we include are quite simple and can easily to Data Structures (CS2) course and a...
Michael T. Goodrich, Leonidas J. Guibas, John Hershberger, Paul J. Tanenbaum
We study the problem of robustly rounding a set S of n line segments in R 2 using the snap rounding paradigm. In this paradigm each pixel containing an endpoint or intersection point is called...
Using Randomization in the Teaching of Data Structures and Algorithms (2007)
Michael T. Goodrich, Roberto Tamassia
We describe an approach for incorporating randomization in the teaching of data structures and algorithms. The proofs we include are quite simple and can easily to Data Structures (CS2) course and a...
Amitabha Bagchi, Amitabh Chaudhary, Rahul Garg, Michael T. Goodrich
Abstract. In this paper we provide an algorithmic approach to the study of online auctioning. From the perspective of the seller, we formalize the auctioning problem as that of designing an...
Matching Points to a Convex Polygonal Boundary EXTENDED ABSTRACT (2007)
Matthew T. Dickerson, Michael T. Goodrich
A set of problems studied recently by Barequet et al. in [BBDG] and [BBD] involve the optimal placement of a polygonal annulus region, dened as the
Eppstein, David, Goodrich, Michael T.
We introduce the straggler identification problem, in which an algorithm must determine the identities of the remaining members of a set after it has had a large number of insertion and deletion...
Choosing Colors for Geometric Graphs via Color Space Embeddings (2007)
Dillencourt, Michael B., Eppstein, David, Goodrich, Michael T.
Graph drawing research traditionally focuses on producing geometric embeddings of graphs satisfying various aesthetic constraints. After the geometric embedding is specified, there is an additional...
Choosing Colors for Geometric Graphs via Color Space Embeddings (2007)
Dillencourt, Michael B., Eppstein, David, Goodrich, Michael T.
Graph drawing research traditionally focuses on producing geometric embeddings of graphs satisfying various aesthetic constraints. After the geometric embedding is specified, there is an additional...
Sorting in parallel external-memory multicores (2007)
Michael T. Goodrich, Michael Nelson, Nodari Sitchinava
Abstract. In this paper, we introduce a model for multicore architectures, which takes into explicit consideration the cache-oriented nature of inputs and outputs in modern CPUs. In addition, we...
Guard placement for efficient point-in-polygon proofs (2007)
Michael T. Goodrich, Nodari Sitchinava
We consider the problem of placing a small number of angle guards inside a simple polygon P so as to provide efficient proofs that any given point is inside P. Each angle guard views an infinite...
Choosing Colors for Geometric Graphs via Color Space Embeddings (2006)
Dillencourt, Michael B., Eppstein, David, Goodrich, Michael T.
Graph drawing research traditionally focuses on producing geometric embeddings of graphs satisfying various aesthetic constraints. After the geometric embedding is specified, there is an additional...
Guard Placement For Wireless Localization (2006)
Eppstein, David, Goodrich, Michael T., Sitchinava, Nodari
Motivated by secure wireless networking, we consider the problem of placing fixed localizers that enable mobile communication devices to prove they belong to a secure region that is defined by the...
Delta-confluent Drawings (2006)
Eppstein, David, Goodrich, Michael T., Meng, Jeremy Y.
We generalize the tree-confuent graphs to a broader class of graphs called delta-confluent graphs. This class of graphs and distance-hereditary graphs, a well-known class of graphs, coincide. Some...
C-Planarity of Extrovert Clustered Graphs (2006)
Goodrich, Michael T., Lueker, George S., Sun, Jonathan Z.
A clustered graph has its vertices grouped into clusters in a hierarchical way via subset inclusion, thereby imposing a tree structure on the clustering relationship. The c-planarity problem is to...
Delta-confluent Drawings (2006)
Eppstein, David, Goodrich, Michael T., Meng, Jeremy Yu
We generalize the tree-confuent graphs to a broader class of graphs called delta-confluent graphs. This class of graphs and distance-hereditary graphs, a well-known class of graphs, coincide. Some...
C-Planarity of Extrovert Clustered Graphs (2006)
Goodrich, Michael T., Lueker, George S., Sun, Jonathan Z.
A clustered graph has its vertices grouped into clusters in a hierarchical way via subset inclusion, thereby imposing a tree structure on the clustering relationship. The c-planarity problem is to...
Delta-confluent Drawings (2006)
Eppstein, David, Goodrich, Michael T., Meng, Jeremy Yu
We generalize the tree-confuent graphs to a broader class of graphs called delta-confluent graphs. This class of graphs and distance-hereditary graphs, a well-known class of graphs, coincide. Some...
C-Planarity of Extrovert Clustered Graphs (2006)
Goodrich, Michael T., Lueker, George S., Sun, Jonathan Z.
A clustered graph has its vertices grouped into clusters in a hierarchical way via subset inclusion, thereby imposing a tree structure on the clustering relationship. The c-planarity problem is to...
Loud and clear: Human-verifiable authentication based on audio (2006)
Michael T. Goodrich, Michael Sirivianos, John Solis, Gene Tsudik, Ersin Uzun
Authentication of communication channels between devices that lack any previous association is an challenging problem. It has been considered in many contexts and in various flavors, most recently,...
Loud and clear: Human-verifiable authentication based on audio (2006)
Michael T. Goodrich, Michael Sirivianos, John Solis, Gene Tsudik, Ersin Uzun
Secure pairing of electronic devices that lack any previous association is a challenging problem which has been considered in many contexts and in various flavors. In this paper, we investigate the...
Amitabha Bagchi, Amitabh Chaudhary, Michael T. Goodrich, Senior Member, Chen Li, Michal Shmueli-scheuer
Many database applications that need to disseminate dynamic information from a server to various clients can suffer from heavy communication costs. Data caching at a client can help mitigate these...
Efficient parallel algorithms for dead sensor diagnosis and multiple access channels (2006)
Michael T. Goodrich, Daniel S. Hirschberg
We study parallel algorithms for identifying the dead sensors in a mobile ad hoc wireless network and for resolving broadcast conflicts on a multiple access channel (MAC). Our approach involves the...
Loud and clear: Human-verifiable authentication based on audio (2006)
Michael T. Goodrich, Michael Sirivianos, John Solis, Gene Tsudik, Ersin Uzun
Secure pairing of electronic devices that lack any previous association is a challenging problem which has been considered in many contexts and in various flavors. In this paper, we investigate the...
Amitabha Bagchi, Amitabh Chaudhary, Michael T. Goodrich, Chen Li, Michal Shmueli-scheuer
Client-server databases that require query results to be up-to-date despite storing data that changes dynamically suffer from heavy communication costs. Client-side caching can help mitigate these...
Loud and clear: Human-verifiable authentication based on audio (2006)
Michael T. Goodrich, Michael Sirivianos, John Solis, Gene Tsudik, Computer Science
Index Terms: Human-assisted authentication, Man-in-the-middle attack, Audio, Text-to-speech, Public key, Key agreement,Personal device, Wireless networks.
Efficient parallel algorithms for dead sensor diagnosis and multiple access channels (2006)
Michael T. Goodrich, Daniel S. Hirschberg
We study parallel algorithms for identifying the dead sensors in a mobile ad hoc wireless network and for resolving broadcast conflicts on a multiple access channel (MAC). Our approach involves the...
Loud and clear: Human-verifiable authentication based on audio (2006)
Michael T. Goodrich, Michael Sirivianos, John Solis, Gene Tsudik, Ersin Uzun
Secure pairing of electronic devices that lack any previous association is a challenging problem which has been considered in many contexts and in various flavors. In this paper, we investigate the...
Efficient parallel algorithms for dead sensor diagnosis and multiple access channels (2006)
Michael T. Goodrich, Daniel S. Hirschberg
We study parallel algorithms for identifying the dead sensors in a mobile ad hoc wireless network and for resolving broadcast conflicts on a multiple access channel (MAC). Our approach involves the...
Loud and clear: Human-verifiable authentication based on audio (2006)
Michael T. Goodrich, Michael Sirivianos, John Solis, Gene Tsudik, Ersin Uzun
Secure pairing of electronic devices that lack any previous association is a challenging problem which has been considered in many contexts and in various flavors. In this paper, we investigate the...
Delta-confluent Drawings (2005)
Eppstein, David, Goodrich, Michael T., Meng, Jeremy Yu
We generalize the tree-confluent graphs to a broader class of graphs called Delta-confluent graphs. This class of graphs and distance-hereditary graphs, a well-known class of graphs, coincide. Some...
The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data (2005)
Eppstein, David, Goodrich, Michael T., Sun, Jonathan Z.
We present a new multi-dimensional data structure, which we call the skip quadtree (for point data in R^2) or the skip octree (for point data in R^d, with constant d>2). Our data structure combines...
Skip-Webs: Efficient Distributed Data Structures for Multi-Dimensional Data Sets (2005)
Arge, Lars, Eppstein, David, Goodrich, Michael T.
We present a framework for designing efficient distributed data structures for multi-dimensional data. Our structures, which we call skip-webs, extend and improve previous randomized distributed data...
Confluent Layered Drawings (2005)
Eppstein, David, Goodrich, Michael T., Meng, Jeremy Yu
We combine the idea of confluent drawings with Sugiyama style drawings, in order to reduce the edge crossings in the resultant drawings. Furthermore, it is easier to understand the structures of...
Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes (2005)
Eppstein, David, Goodrich, Michael T., Hirschberg, Daniel S.
We study practically efficient methods for performing combinatorial group testing. We present efficient non-adaptive and two-stage combinatorial group testing algorithms, which identify the at most d...
Amitabha Bagchi, Adam L. Buchsbaum, Michael T. Goodrich
We design a variation of skip lists that performs well for generally biased access sequences. Given n items, each with a positive weight w i, 1
Improved combinatorial group testing for real-world problem sizes (2005)
Michael T. Goodrich, Daniel S. Hirschberg
{eppstein, goodrich, dan}(at)ics.uci.edu Abstract. We study practically efficient methods for performing combinatorial group testing. We present efficient non-adaptive and two-stage combinatorial...
Skip-webs: Efficient distributed data structures for multi-dimensional data sets (2005)
Lars Arge, Michael T. Goodrich
large(at)daimi.au.dk eppstein(at)ics.uci.edu goodrich(at)acm.org We present a framework for designing efficient distributed data structures for multi-dimensional data. Our structures, which we call...
We present two new approaches to improving the integrity of network broadcasts and multicasts with low storage and computation overhead. The first approach is a leapfrog linking protocol for securing...
C-planarity of extrovert clustered graphs (2005)
Michael T. Goodrich, George S. Lueker, Jonathan Z. Sun
Abstract. A clustered graph has its vertices grouped into clusters in a hierarchical way via subset inclusion, thereby imposing a tree structure on the clustering relationship. The c-planarity...
Amitabha Bagchi, Adam L. Buchsbaum, Michael T. Goodrich
We design a variation of skip lists that performs well for generally biased access sequences. Given � n items, each with a positive weight wi, 1 ≤ i ≤ n, the time to access item i is O 1 + log...
Secure Biometric Authentication for Weak Computational Devices (2005)
Mikhail J. Atallah, Keith B. Frikken, Michael T. Goodrich, Roberto Tamassia
This paper presents computationally "lightweight" schemes for performing biometric authentication that carry out the comparison stage without revealing any information that can later be...
Loud and Clear: Human-Verifiable Authentication Based on Audio (2005)
Michael T. Goodrich, Michael Sirivianos, John Solis, Gene Tsudik, Ersin Uzun
Secure pairing of electronic devices that lack any previous association is a challenging problem which has been considered in many contexts and in various flavors. In this paper, we investigate the...
Searching for High-Value Rare Events with Uncheatable Grid Computing (2005)
Wenliang Du, Michael T. Goodrich
goodrich(at)acm.org Abstract. High-value rare-event searching is arguably the most natural application of grid computing, where computational tasks are distributed to a large collection of clients...
The skip quadtree: a simple dynamic data structure for multidimensional data (2005)
Michael T. Goodrich, Jonathan Z. Sun
We present a new multi-dimensional data structure, which we call the skip quadtree (for point data in R 2) or the skip octree (for point data in R d, with constant d> 2). Our data structure...
Indexing information for data forensics (2005)
Michael T. Goodrich, Mikhail J. Atallah, Roberto Tamassia
Abstract. We introduce novel techniques for organizing the indexing structures of how data is stored so that alterations from an original version can be detected and the changed values specifically...
Amitabha Bagchi, Adam L. Buchsbaum, Michael T. Goodrich
Abstract. We design a variation of skip lists that performs well for generally biased access sequences. Given n items, each � with a positive weight wi, 1 ≤ i ≤ n, the time to access item i is...
Searching for High-Value Rare Events with Uncheatable Grid Computing (2005)
Wenliang Du, Michael T. Goodrich
goodrich(at)acm.org Abstract. High-value rare-event searching is arguably the most natural application of grid computing, where computational tasks are distributed to a large collection of clients...
Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way (2004)
Dickerson, Matthew, Eppstein, David, Goodrich, Michael T., Meng, Jeremy Yu
We introduce a new approach for drawing diagrams. Our approach is to use a technique we call confluent drawing for visualizing non-planar graphs in a planar way. This approach allows us to draw, in a...
Selected Open Problems in Graph Drawing (2004)
Brandenburg, Franz J., Eppstein, David, Goodrich, Michael T., Kobourov, Stephen G., Liotta, Giuseppe, Mutzel, Petra
In this manuscript, we present several challenging and interesting open problems in graph drawing. The goal of the listing in this paper is to stimulate future research in graph drawing.
Confluent Layered Drawings (2004)
Eppstein, David, Goodrich, Michael T., Meng, Jeremy Yu
We combine the idea of confluent drawings with Sugiyama style drawings, in order to reduce the edge crossings in the resultant drawings. Furthermore, it is easier to understand the structures of...
Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way (2004)
Dickerson, Matthew, Eppstein, David, Goodrich, Michael T., Meng, Jeremy Yu
We introduce a new approach for drawing diagrams. Our approach is to use a technique we call confluent drawing for visualizing non-planar graphs in a planar way. This approach allows us to draw, in a...
Selected Open Problems in Graph Drawing (2004)
Brandenburg, Franz J., Eppstein, David, Goodrich, Michael T., Kobourov, Stephen G., Liotta, Giuseppe, Mutzel, Petra
In this manuscript, we present several challenging and interesting open problems in graph drawing. The goal of the listing in this paper is to stimulate future research in graph drawing.
Confluent Layered Drawings (2004)
Eppstein, David, Goodrich, Michael T., Meng, Jeremy Yu
We combine the idea of confluent drawings with Sugiyama style drawings, in order to reduce the edge crossings in the resultant drawings. Furthermore, it is easier to understand the structures of...
Data Structures and Algorithms in C++ [i.e. C Plus Plus] (2004)
Goodrich, Michael T., Tamassia, Roberto, Mount, David M.
Contenido: Programación básica con C++; Diseño orientado a objetos; Análisis de herramientas; Apilados, colas y repeticiones; Vectores, listas y secuencias; Arboles; Colas prioritarias;...
Data Structures and Algorithms in C++ [i.e. C Plus Plus] (2004)
Goodrich, Michael T., Tamassia, Roberto, Mount, David M.
0-471-20208-8
Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way (2004)
Dickerson, Matthew, Eppstein, David, Goodrich, Michael T., Meng, Jeremy Yu
We introduce a new approach for drawing diagrams. Our approach is to use a technique we call confluent drawing for visualizing non-planar graphs in a planar way. This approach allows us to draw, in a...
Selected Open Problems in Graph Drawing (2004)
Brandenburg, Franz J., Eppstein, David, Goodrich, Michael T., Kobourov, Stephen G., Liotta, Giuseppe, Mutzel, Petra
In this manuscript, we present several challenging and interesting open problems in graph drawing. The goal of the listing in this paper is to stimulate future research in graph drawing.
Confluent Layered Drawings (2004)
Eppstein, David, Goodrich, Michael T., Meng, Jeremy Yu
We combine the idea of confluent drawings with Sugiyama style drawings, in order to reduce the edge crossings in the resultant drawings. Furthermore, it is easier to understand the structures of...
Deterministic sampling and range counting in geometric data streams (2004)
Amitabha Bagchi, Amitabh Chaudhary, Michael T. Goodrich
We present memory-efficient deterministic algorithms for constructing ɛ-nets and ɛ-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide...
Efficient tree-based revocation in groups of low-state devices (2004)
Michael T. Goodrich, Jonathan Z. Sun, Roberto Tamassia
Abstract. We study the problem of broadcasting confidential information to a collection of n devices while providing the ability to revoke an arbitrary subset of those devices (and tolerating...
Deterministic sampling and range counting in geometric data streams (2004)
Amitabha Bagchi, Amitabh Chaudhary, Michael T. Goodrich
We present memory-efficient deterministic algorithms for constructing ɛ-nets and ɛ-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide...
Deterministic Sampling and Range Counting in Geometric Data Streams (2004)
Amitabha Bagchi, Amitabh Chaudhary, David Eppstein, Michael T. Goodrich
We present memory-efficient deterministic algorithms for constructing #-nets and #-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide...
Deterministic Sampling and Range Counting in Geometric Data Streams (2004)
Amitabha Bagchi, Amitabh Chaudhary, David Eppstein, Michael T. Goodrich
We present memory-efficient deterministic algorithms for constructing #-nets and #-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide...
Efficient tree-based revocation in groups of low-state devices (2004)
Michael T. Goodrich, Jonathan Z. Sun
Abstract. We study the problem of broadcasting confidential information to a collection of n devices while providing the ability to revoke an arbitrary subset of those devices (and tolerating...
Drawing Planar Graphs with Large Vertices and Thick Edges (2004)
Gill Barequet, Michael T. Goodrich, Chris Riley
We consider the problem of representing size information in the edges and vertices of a planar graph. Such information can be used, for example, to depict a network of computers and information...
Confluent layered drawings (2004)
Michael T. Goodrich, Jeremy Yu Meng
Abstract. We combine the idea of confluent drawings with Sugiyama style drawings, in order to reduce the edge crossings in the resultant drawings. Furthermore, it is easier to understand the...
Deterministic sampling and range counting in geometric data streams (2004)
Amitabha Bagchi, Amitabh Chaudhary, Michael T. Goodrich
We present memory-efficient deterministic algorithms for constructing ɛ-nets and ɛ-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide...
Contour interpolation by straight skeletons, Graphical Models (2004)
Gill Barequet, Michael T. Goodrich, Aya Levi-steiner, Dvir Steiner D
In this paper we present an efficient method for interpolating a piecewise-linear surface between two parallel slices, each consisting of an arbitrary number of (possibly nested) polygons that define...
Confluent layered drawings (2004)
Michael T. Goodrich, Jeremy Yu Meng
Abstract. We combine the idea of confluent drawings with Sugiyama style drawings, in order to reduce the edge crossings in the resultant drawings. Furthermore, it is easier to understand the...
Deterministic sampling and range counting in geometric data streams (2004)
Amitabha Bagchi, Amitabh Chaudhary, Michael T. Goodrich
We present memory-efficient deterministic algorithms for constructing ɛ-nets and ɛ-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide...
Deterministic Sampling and Range Counting in Geometric Data Streams (2003)
Bagchi, Amitabha, Chaudhary, Amitabh, Eppstein, David, Goodrich, Michael T.
We present memory-efficient deterministic algorithms for constructing epsilon-nets and epsilon-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic...
Constructing disjoint paths for secure communication (2003)
Amitabha Bagchi, Amitabh Chaudhary, Michael T. Goodrich, Shouhuai Xu
Abstract. We propose a bandwidth-efficient algorithmic solution for perfectly-secure communication in the absence of secure infrastructure. Our solution involves connecting vertex pairs by a set of k...
Constructing disjoint paths for secure communication (2003)
Amitabha Bagchi, Amitabh Chaudhary, Michael T. Goodrich
Abstract. We propose a bandwidth-efficient algorithmic solution for perfectly-secure communication in the absence of secure infrastructure. Our solution involves connecting vertex pairs by a set of k...
Confluent drawings: Visualizing Non-Planar Diagrams in a Planar Way (2003)
Matthew Dickerson, Michael T. Goodrich, Jeremy Y. Meng
We introduce a new approach for drawing diagrams. Our approach is to use a technique we call confluent drawing for visualizing non-planar graphs in a planar way. This approach allows us to draw, in a...
Authenticated dictionaries for fresh attribute credentials (2003)
Michael T. Goodrich, Michael Shin, Roberto Tamassia, William H. Winsborough
Abstract. We describe several schemes for efficiently populating an authenticated dictionary with fresh credentials. The thrust of this effort is directed at allowing for many data authors, called...
Authenticated data structures for graph and geometric searching (2003)
Michael T. Goodrich, Roberto Tamassia, Nikos Tri, Opoulos Robert Cohen
Following in the spirit of data structure and algorithm correctness checking, authenticated data structures provide cryptographic proofs that their answers are as accurate as the author intended,...
Confluent drawings: Visualizing Non-Planar Diagrams in a Planar Way (2003)
Matthew Dickerson, Michael T. Goodrich, Jeremy Y. Meng
We introduce a new approach for drawing diagrams. Our approach is to use a technique we call confluent drawing for visualizing non-planar graphs in a planar way. This approach allows us to draw, in a...
Confluent drawings: Visualizing Non-Planar Diagrams in a Planar Way (2003)
Matthew Dickerson, Michael T. Goodrich, Jeremy Yu Meng
Abstract. We introduce a new approach for drawing diagrams. Our approach is to use a technique we call confluent drawing for visualizing non-planar graphs in a planar way. This approach allows us to...
Constructing Disjoint Paths for Secure Communication (2003)
Amitabha Bagchi, Amitabh Chaudhary, Michael T. Goodrich, Shouhuai Xu
We propose a bandwidth-e#cient algorithmic solution for perfectly-secure communication in the absence of secure infrastructure.
Planar Upward Tree Drawings With Optimal Area (2003)
Ashim Garg, Michael T. Goodrich, Roberto Tamassia
Rooted trees are usually drawn planar and upward, i.e., without crossings and without any parent placed below its child. In this paper we investigate the area requirement of planar upward drawings of...
Drawing graphs with large vertices and thick edges (2003)
Gill Barequet, Michael T. Goodrich, Chris Riley
Abstract. We consider the problem of representing size information in the edges and vertices of a planar graph. Such information can be used, for example, to depict a network of computers and...
Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way (2002)
Dickerson, Matthew, Eppstein, David, Goodrich, Michael T., Meng, Jeremy
In this paper, we introduce a new approach for drawing diagrams that have applications in software visualization. Our approach is to use a technique we call confluent drawing for visualizing...
Estructuras de datos y algoritmos en Java (2002)
Goodrich, Michael T., Tamassia, Roberto
Traducción de: Data Structures and Algorithms in Java
Estructuras de datos y algoritmos en Java (2002)
Goodrich, Michael T., Tamassia, Roberto
970-24-0330-8
An efficient dynamic and distributed cryptographic accumulator (2002)
Michael T. Goodrich, Roberto Tamassia, Jasminka Hasic
We show how to use the RSA one-way accumulator to realize an efficient and dynamic authenticated dictionary, where untrusted directories provide cryptographically verifiable answers to membership...
An efficient dynamic and distributed cryptographic accumulator (2002)
Michael T. Goodrich, Roberto Tamassia
One-way accumulators allow insecure directories to provide cryptographically secure answers to membership queries on a set maintained by a trusted third party (TTP). Such usage implements the...
A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs (2001)
Gajer, Pawel, Goodrich, Michael T., Kobourov, Stephen G.
We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space \mathbb{E} of any dimension. A two or three dimensional...
A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs (2001)
Gajer, Pawel, Goodrich, Michael T., Kobourov, Stephen G.
We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space \mathbb{E} of any dimension. A two or three dimensional...
A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs (2001)
Gajer, Pawel, Goodrich, Michael T., Kobourov, Stephen G.
We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space \mathbb{E} of any dimension. A two or three dimensional...
Implementation of an Authenticated Dictionary with Skip Lists and Commutative Hashing (2001)
We present the software architecture and implementation of an efficient data structure for dynamically maintaining an authenticated dictionary. The building blocks of the data structure are skip...
Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos
We describe a randomized algorithm for computing the trapezoidal decomposition of a simple polygon. Its expected running time is linear in the size of the polygon. By a well-known and simple linear...
Persistent Authenticated Dictionaries and Their Applications (2001)
Aris Anagnostopoulos, Michael T. Goodrich, Roberto Tamassia
Abstract. We introduce the notion of persistent authenticated dictionaries, that is, dictionaries where the user can make queries of the type “was element e in set S at time t? ” and get...
Implementation of an Authenticated Dictionary with Skip Lists and Commutative Hashing (2001)
We present the software architecture and implementation of an efficient data structure for dynamically maintaining an authenticated dictionary. The building blocks of the data structure are skip...
Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos
We describe a randomized algorithm for computing the trapezoidal decomposition of a simple polygon. Its expected running time is linear in the size of the polygon. By a well-known and simple linear...
Authenticated Data Structures for Graph and Geometric Searching (2001)
Michael T. Goodrich, Roberto Tamassia, Nikos Triandopoulos, Robert Cohen, Opoulos Robert Cohen
Following in the spirit of data structure and algorithm correctness checking, authenticated data structures provide cryptographic proofs that their answers are as accurate as the author intended,...
Seller-Focused Algorithms for Online Auctioning (2001)
Amitabha Bagchi, Amitabh Chaudhary, Rahul Garg, Michael T. Goodrich, Vijay Kumar
In this paper we provide an algorithmic approach to the study of online auctioning. From the perspective of the seller we formalize the auctioning problem as that of designing an algorithmic strategy...
Persistent Authenticated Dictionaries and Their Applications (2001)
Aris Anagnostopoulos, Michael T. Goodrich, Roberto Tamassia
Abstract. We introduce the notion of persistent authenticated dictionaries, that is, dictionaries where the user can make queries of the type “was element e in set S at time t? ” and get...
Seller-focused algorithms for online auctioning (2001)
Amitabha Bagchi, Amitabh Chaudhary, Rahul Garg, Michael T. Goodrich
Abstract. In this paper we provide an algorithmic approach to the study of online auctioning. From the perspective of the seller we formalize the auctioning problem as that of designing an...
Efficient and Secure Network Routing Algorithms. provisional patent filing (2001)
We present several algorithms for network routing that are resilient to various attacks on the routers themselves. Our methods for securing routing algorithms are based on a novel “leapfrog”...
Efficient perspective-accurate silhouette computation and applications (2001)
Mihai Pop, Christian A. Duncan, Gill Barequet, Michael T. Goodrich, Wenjing Huang
� � � � � �Æ � � � � � � � � � � � ��Æ � � � � � � � � �Æ � � � � � � � �Æ � � � � � � � � � � � �...
A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs (2000)
Pawel Gajer, Michael T. Goodrich, Stephen G. Kobourov
Abstract. We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space E of any dimension. A two or three dimensional...
Efficient authenticated dictionaries with skip lists and commutative hashing (2000)
Michael T. Goodrich, Roberto Tamassia
We present an efficient and practical technique for dynamically maintaining an authenticated dictionary. The main building blocks of our scheme are the skip list data structure and cryptographic...
A fast multi-dimensional algorithm for drawing large graphs (2000)
Pawel Gajer, Michael T. Goodrich, Stephen G. Kobourov
We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space E of any dimension. A two or three dimensional drawing...
Computing the arrangement of curve segments: divide-and-conquer algorithms via sampling (2000)
Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos
Random sampling provides a natural approach for computing the arrangement of a set of geometric objects via divide-and-conquer. Unfortunately, in many cases it does not lead to an optimal algorithm....
A fast multi-dimensional algorithm for drawing large graphs (2000)
Pawel Gajer, Michael T. Goodrich, Stephen G. Kobourov
We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space E of any dimension. A two or three dimensional drawing...
Range Searching Over Tree Cross Products (2000)
Adam L. Buchsbaum, Michael T. Goodrich, Jeffery R. Westbrook
We introduce the tree cross-product problem, which abstracts a data structure common to applications in graph visualization, string matching, and software analysis. We design solutions with a variety...
Linear-Time Triangulation of a Simple Polygon Made Easier Via Randomization (2000)
Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos
We describe a randomized algorithm for computing the trapezoidal decomposition of a simple polygon. Its expected running time is linear in the size of the polygon. By a well-known and simple linear...
A System for Generating, Archiving, and Retrieving Specialized Assignments Using LATEX (2000)
Stina Bridgeman, Michael T. Goodrich, Stephen G. Kobourov, Roberto Tamassia
We present SAIL, a package for the creation of Specialized Assignment In L A T E X. We describe several features which allow an instructor to create su- ciently dierent instances of the \same"...
PILOT: An Interactive Tool for Learning and Grading (2000)
Stina Bridgeman, Michael T. Goodrich, Stephen G. Kobourov, Roberto Tamassia
We describe a Web-based interactive tool, called PILOT, for testing computer science concepts. The strengths of our system are its universal access and platform independence, its ability to test...
A fast multi-dimensional algorithm for drawing large graphs (2000)
Pawel Gajer, Michael T. Goodrich, Stephen G. Kobourov
Abstract. We present a novel hierarchical force-directed method for drawing large graphs. The algorithm produces a graph embedding in an Euclidean space � of any dimension. A two or three...
Drawing Planar Graphs with Circular Arcs (1999)
Cheng, C. C., Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
In this paper we address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small drawing area. We present a lower bound on the area of drawings in...
Planarity-Preserving Clustering and Embedding for Large Planar Graphs (1999)
Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
In this paper we present a novel approach for cluster-based drawing of large planar graphs that maintains planarity. Our technique works for arbitrary planar graphs and produces a clustering which...
Drawing Planar Graphs with Circular Arcs (1999)
Cheng, C. C., Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
In this paper we address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small drawing area. We present a lower bound on the area of drawings in...
Planarity-Preserving Clustering and Embedding for Large Planar Graphs (1999)
Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
In this paper we present a novel approach for cluster-based drawing of large planar graphs that maintains planarity. Our technique works for arbitrary planar graphs and produces a clustering which...
Drawing Planar Graphs with Circular Arcs (1999)
Cheng, C. C., Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
In this paper we address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small drawing area. We present a lower bound on the area of drawings in...
Planarity-Preserving Clustering and Embedding for Large Planar Graphs (1999)
Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
In this paper we present a novel approach for cluster-based drawing of large planar graphs that maintains planarity. Our technique works for arbitrary planar graphs and produces a clustering which...
Planarity-preserving clustering and embedding for large planar graphs (1999)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
Abstract. In this paper we present a novel approach for cluster-based drawing of large planar graphs that maintains planarity. Our technique works for arbitrary planar graphs and produces a...
Approximate geometric pattern matching under rigid motions (1999)
Michael T. Goodrich, Senior Member, Mark W. Orletsky
Abstract—We present techniques for matching point-sets in two and three dimensions under rigid-body transformations. We prove bounds on the worst-case performance of these algorithms to be within a...
Testers and visualizers for teaching data structures (1999)
Ryan S. Baker, Michael Boilen, Michael T. Goodrich, Roberto Tamassia, Brown Univ, Brown Univ, ...
Johns Hopkins Univ.
Planarity-preserving clustering and embedding for large planar graphs (1999)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
Abstract. In this paper we present a novel approach for cluster-based drawing of large planar graphs that maintains planarity. Our technique works for arbitrary planar graphs and produces a...
Computing the Arrangement of Curve Segments: Divide-and-Conquer Algorithms via Sampling (1999)
Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos
We describe two deterministic algorithms for constructing the arrangement determined by a set of (algebraic) curve segments in the plane. They both use a divide-and-conquer approach based on...
Balanced Aspect Ratio Trees: Combining the Advantages of (1999)
Trees And Octrees, Christian A. Duncan, Michael T. Goodrich, Stephen Kobourov
Given a set S of n points in IR d , we show, for fixed d, how to construct in O(n log n) time a data structure we call the Balanced Aspect Ratio (BAR) tree. A BAR tree is a binary space partition...
Balanced Aspect Ratio Trees: Combining the Advantages of k-d Trees and Octrees (1999)
Christian A. Duncan, Michael T. Goodrich, Stephen Kobourov
Given a set S of n points in IR d , we show, for fixed d, how to construct in O(n log n) time a data structure we call the Balanced Aspect Ratio (BAR) tree. A BAR tree is a binary space partition...
Computing the Arrangement of Curve Segments: Divide-and-Conquer Algorithms via Sampling (1999)
Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos
Random sampling provides a natural approach for computing the arrangement of a set of geometric objects via divide-and-conquer. Unfortunately, in many cases it does not lead to an optimal algorithm....
Balanced Aspect Ratio Trees: Combining the Advantages of k-d Trees and Octrees (1999)
Christian A. Duncan, Michael T. Goodrich, Stephen Kobourov
Given a set S of n points in IR d , we show, for fixed d, how to construct in O(n log n) time a data structure we call the Balanced Aspect Ratio (BAR) tree. A BAR tree is a binary space partition...
Testers and visualizers for teaching data structures (1999)
Ryan S. Baker, Michael Boilen, Michael T. Goodrich, Roberto Tamassia
rtQcs.bronn.edn Abstract plication programmer interface (API). We present two tools to support the teaching of data struc-tures and algorithms: Visualizers, which provide interactive visualizations...
Ecient Perspective-Accurate Silhouette Computation (1999)
Gill Barequet Christian, Christian A. Duncan, Michael T. Goodrich, Wenjing Huang
Silhouettes are perceptually and geometrically salient features of geometric models. Hence a number of graphics and visualization applications need to nd them to aid further processing. The ecient...
Balanced aspect ratio trees: Combining the advantages of k-d trees and octrees (1999)
Christian A. Duncan, Michael T. Goodrich, Stephen Kobourov
Given a set S of n points on � d, we show, for fixed d, how to construct in Onlog Ž n. time a data structure we call the balanced aspect ratio Ž BAR. tree. A BAR tree is a binary space partition...
Planarity-preserving clustering and embedding for large planar graphs (1999)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
Abstract. In this paper we present a novel approach for cluster-based drawing of large planar graphs that maintains planarity. Our technique works for arbitrary planar graphs and produces a...
Applicable and Robust Geometric Computing (1998)
Preparata, Franco P., Agarwal, Pankaj K., Tamassia, Roberto, Vitter, Jeffrey S., Goodrich, Michael T.
This research project is aimed at aimed at facilitating an effective technology transfer from computational geometry to the various applied fields to which it is relevant. Our technical contributions...
A Framework for Drawing Planar Graphs with Curves and Polylines (1998)
Goodrich, Michael T., Wagner, Cristopher G.
We describe a unified framework of aesthetic criteria and complexity measures for drawing planar graphs with polylines and curves. This framework includes several visual properties of such drawings,...
Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (1998)
Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
We describe a new approach for cluster-based drawing of very large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called...
A Framework for Drawing Planar Graphs with Curves and Polylines (1998)
Goodrich, Michael T., Wagner, Cristopher G.
We describe a unified framework of aesthetic criteria and complexity measures for drawing planar graphs with polylines and curves. This framework includes several visual properties of such drawings,...
Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (1998)
Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
We describe a new approach for cluster-based drawing of very large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called...
A Framework for Drawing Planar Graphs with Curves and Polylines (1998)
Goodrich, Michael T., Wagner, Cristopher G.
We describe a unified framework of aesthetic criteria and complexity measures for drawing planar graphs with polylines and curves. This framework includes several visual properties of such drawings,...
Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (1998)
Duncan, Christian A., Goodrich, Michael T., Kobourov, Stephen G.
We describe a new approach for cluster-based drawing of very large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called...
Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (1998)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
We describe a new approach for cluster-based drawing of large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called the...
Teaching the Analysis of Algorithms with Visual Proofs (1998)
Michael T. Goodrich, Roberto Tamassia
We describe an approach for visually teaching important proofs in the Junior-Senior level course on the design and analysis of data structures and algorithms (CS7/DS&A). The main idea of this...
Teaching data structure design patterns (1998)
Natasha Gelfand, Michael T. Goodrich, Roberto Tamassia
Abstract In this paper we present an approach for teaching the Freshman-Sophomore introduction to data structures course (CS2) in a way that provides an introduction to object-oriented software...
Teaching the Analysis of Algorithms with Visual Proofs (1998)
Michael T. Goodrich, Roberto Tamassia
We describe an approach for visually teaching important proofs in the Junior-Senior level course on the design and analysis of data structures and algorithms (CS7/DS&A). The main idea of this...
Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (1998)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
Abstract. We describe a new approach for cluster-based drawing of very large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type...
Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (1998)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
We describe a new approach for cluster-based drawing of large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called the...
A Framework for Drawing Planar Graphs with Curves and Polylines (1998)
Michael T. Goodrich, Christopher G. Wagner
We describe a unified framework of aesthetic criteria and complexity measures for drawing planar graphs with polylines and curves. This framework includes several visual properties of such drawings,...
Efficiently Approximating Polygonal Paths in Three and Higher Dimensions (1998)
Gill Barequet, Danny Z. Chen, Ovidiu Daescu, Michael T. Goodrich, Jack Snoeyink
We present efficient algorithms for solving polygonal-path approximation problems in three and higher dimensions. Given an n-vertex polygonal curve P in IR d , d 3, we approximate P by another...
Teaching Data Structure Design Patterns (1998)
Natasha Gelfand, Michael T. Goodrich, Roberto Tamassia
In this paper we present an approach for teaching the Freshman-Sophomore introduction to data structures course #CS2# in a way that provides an introduction to object-oriented software engineering...
Balanced Aspect Ratio Trees and Their Use for Drawing Large Graphs (1998)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
We describe a new approach for cluster-based drawing of large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called the...
Efficiently Approximating Polygonal Paths in Three and Higher Dimensions (1998)
Gill Barequet, Danny Z. Chen, Ovidiu Daescu, Michael T. Goodrich, Jack Snoeyink
We present efficient algorithms for solving polygonal -path approximation problems in three and higher dimensions. Given an n-vertex polygonal curve P in IR d , d 3, we approximate P by another...
Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (1998)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
We describe a new approach for cluster-based drawing of very large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called...
Balanced Aspect Ratio Trees and Their Use for Drawing Very Large Graphs (1998)
Christian A. Duncan, Michael T. Goodrich, Stephen G. Kobourov
Abstract. We describe a new approach for cluster-based drawing of very large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type...
A framework for drawing planar graphs with curves and polylines (1998)
Michael T. Goodrich, Christopher G. Wagner
Abstract. We describe a unified framework of aesthetic criteria and complexity measures for drawing planar graphs with polylines and curves. This framework includes several visual properties of such...
Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings (1997)
Chan, Timothy, Goodrich, Michael T., Kosaraju, Rao, Tamassia, Roberto
We investigate the problem of drawing an arbitrary n-node binary tree orthogonally in an integer grid using straight-line edges. We show that one can simultaneously achieve good area bounds while...
Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings (1997)
Chan, Timothy, Goodrich, Michael T., Kosaraju, Rao, Tamassia, Roberto
We investigate the problem of drawing an arbitrary n-node binary tree orthogonally in an integer grid using straight-line edges. We show that one can simultaneously achieve good area bounds while...
Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings (1997)
Chan, Timothy, Goodrich, Michael T., Kosaraju, Rao, Tamassia, Roberto
We investigate the problem of drawing an arbitrary n-node binary tree orthogonally in an integer grid using straight-line edges. We show that one can simultaneously achieve good area bounds while...
Efficient approximation and optimization algorithms for computational metrology (1997)
Christian A. Duncan, Michael T. Goodrich, Edgar A. Ramos
We give efficient algorithms for solving several geometric problems in computational metrology, focusing on the fundamental issues of "flatness " and "roundness. "...
Methods for Achieving Fast Query Times in Point Location Data Structures (1997)
Michael T. Goodrich, Mark Orletsky
Given a collection S of n line segments in the plane, the planar point location problem is to construct a data structure that can efficiently determine for a given query point p the first segment(s)...
Optimizing Area and Aspect Ratio in Straight-Line Orthogonal Tree Drawings (1997)
Timothy Chan, Michael T. Goodrich, S. Rao Kosaraju, Roberto Tamassia
We investigate the problem of drawing an arbitrary n-node binary tree orthogonally in an integer grid using straight-line edges. We show that one can simultaneously achieve good area bounds while...
Classical Computational Geometry in GeomNet (1997)
Gill Barequet, Stina S. Bridgeman, Christian A. Duncan, Michael T. Goodrich, Roberto Tamassia
In this paper we present GeomNet, a system for performing distributed geometric computing over the Internet. We also provide several examples of actual geometric algorithms that our system already...
Efficient Approximation and Optimization Algorithms for Computational Metrology (1997)
Christian Duncan, Michael T. Goodrich, Edgar A. Ramos
We give efficient algorithms for solving several geometric problems in computational metrology, focusing on the fundamental issues of "flatness" and "roundness." Specifically, we...
Voronoi Diagrams for Polygon-Offset Distance Functions (1997)
Gill Barequet, Matthew T. Dickerson, Michael T. Goodrich
. In this paper we develop the concept of a polygon-offset distance function and show how to compute the respective nearest- and furthest-site Voronoi diagrams of point sites in the plane. We provide...
Offset-Polygon Annulus Placement Problems (1997)
Gill Barequet, Amy J. Briggs, Matthew T. Dickerson, Michael T. Goodrich, Michael T
. In this paper we address several variants of the polygon annulus placement problem: given an input polygon P and a set S of points, find an optimal placement of P that maximizes the number of...
Efficient Approximation and Optimization Algorithms for Computational Metrology (1997)
Christian A. Duncan, Michael T. Goodrich, Edgar A. Ramos
We give efficient algorithms for solving several geometric problems in computational metrology, focusing on the fundamental issues of "flatness" and "roundness." Specifically, we...
Randomized Fully-Scalable BSP Techniques for Multi-Searching and Convex Hull Construction (1997)
We study randomized techniques for designing efficient algorithms on a p-processor bulk-synchronous parallel (BSP) computer, which is a parallel multicomputer that allows for general...
Methods for Achieving Fast Query Times in Point Location Data Structures (1997)
Michael T. Goodrich, Mark Orletsky, Kumar Ramaiyer
Given a collection S of n line segments in the plane, the planar point location problem is to construct a data structure that can efficiently determine for a given query point p the first segment(s)...
Michael T. Goodrich, Roberto Tamassia
We give new methods for maintaining a data structure that supports ray shooting and shortest path queries in a dynamically-changing connected planar subdivision S. Our approach is based on a new...
Strategic Directions in Computational Geometry (1996)
Roberto Tamassia, Roberto Tamassia (editor, Pankaj K. Agarwal, Nancy Amato, Danny Z. Chen, David Dobkin, ...
ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission...
Michael T. Goodrich, Edgar A. Ramos
We give fast and efficient methods for constructing ffl-nets and ffl-approximations for range spaces with bounded VC-exponent. These combinatorial structures have wide applicability to geometric...
Blocking for External Graph Searching (1996)
Mark H. Nodine, Michael T. Goodrich, Jeffrey Scott Vitter
In this paper, we consider the problem of using disk blocks efficiently in searching graphs that are too large to fit in internal memory. Our model allows a vertex to be represented any number of...
Planar Upward Tree Drawings with Optimal Area (1996)
Ashim Garg, Michael T. Goodrich, Roberto Tamassia
Rooted trees are usually drawn planar and upward, i.e., without crossings and without any parent placed below its child. In this paper we investigate the area requirement of planar upward drawings of...
Convex Drawings of Graphs in Two and Three Dimensions (Preliminary Version) (1996)
Marek Chrobak, Michael T. Goodrich, Roberto Tamassia
In this paper, we investigate the area and volume requirement of convex drawings of planar graphs in two and three dimensions, under various resolution rules. Let G be a triconnected planar graph...
Characterization and Recognition of Point-Halfspace and Related Orders (Preliminary Version) (1995)
Tanenbaum, Paul J., Goodrich, Michael T., Scheinerman, Edward R.
We characterize four classes of geometric membership and containment orders-structurally and in terms of forbidden subposets-and present linear- or near linear-time recognition algorithms for each...
Characterization and Recognition of Point-Halfspace and Related Orders (Preliminary Version) (1995)
Tanenbaum, Paul J., Goodrich, Michael T., Scheinerman, Edward R.
We characterize four classes of geometric membership and containment orders-structurally and in terms of forbidden subposets-and present linear- or near linear-time recognition algorithms for each...
Characterization and Recognition of Point-Halfspace and Related Orders (Preliminary Version) (1995)
Tanenbaum, Paul J., Goodrich, Michael T., Scheinerman, Edward R.
We characterize four classes of geometric membership and containment orders-structurally and in terms of forbidden subposets-and present linear- or near linear-time recognition algorithms for each...
External-Memory Graph Algorithms (1995)
Michael T. Goodrich, Edward F. Grove, Roberto Tamassia, Darren Erik Vengroff, ...
We present a collection of new techniques for designing and analyzing efficient external-memory algorithms for graph problems and illustrate how these techniques can be applied to a wide variety of...
Almost Optimal Set Covers in Finite VC-Dimension (1995)
Hervé Brönnimann, Michael T. Goodrich
We give a deterministic polynomial time method for finding a set cover in a set system (X
Almost Optimal Set Covers in Finite VC-Dimension (1995)
Hervé Brönnimann, Michael T. Goodrich
We give a deterministic polynomial time method for finding a set cover in a set system (X, R) of VC-dimension d such that the size of our cover is at most a factor of O(d log(dc)) from the optimal...
Gautam Das, Michael T. Goodrich
We show that several well-known optimization problems involving 3-dimensional convex polyhedra and decision trees are NP-hard or NP-complete. One of the techniques we employ is a linear-time method...
External-Memory Graph Algorithms (1995)
Yi-Jen Chiang, Michael T. Goodrich, Edward F. Grove, Roberto Tamassia, Darren Erik Vengroff, ...
We present a collection of new techniques for designing and analyzing efficient external-memory algorithms for graph problems and illustrate how these techniques can be applied to a wide variety of...
External-Memory Graph Algorithms (1995)
Michael T. Goodrich, Edward F. Grove, Roberto Tamassia, Darren Erik Vengroff, ...
We present a collection of new techniques for designing and analyzing efficient external-memory algorithms for graph problems and illustrate how these techniques can be applied to a wide variety of...
Computing Faces in Segment and Simplex Arrangements (1995)
Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos
For a set S of n line segments in the plane, we give the first work-optimal deterministic parallel algorithm for constructing their arrangement. It runs in O(log 2 n) time using O(n log n + k) work...
Planar Upward Tree Drawings with Optimal Area (1995)
Ashim Garg, Michael T. Goodrich, Roberto Tamassia
Rooted trees are usually drawn planar and upward, i.e., without crossings and without any parent placed below its child. In this paper we investigate the area requirement of planar upward drawings of...
External-Memory Graph Algorithms (1995)
Yi-Jen Chiang, Michael T. Goodrich, Edward F. Grove, Roberto Tamassia, Darren Erik Vengroff, ...
We present a collection of new techniques for designing and analyzing efficient external-memory algorithms for graph problems and illustrate how these techniques can be applied to a wide variety of...
Decision Tree Construction in Fixed Dimensions: Being Global is Hard but Local Greed is Good (1995)
Michael T. Goodrich, Vincent Mirelli, Mark Orletsky, Jeffery Salowe
We study the problem of finding optimal linear decision trees for classifying a set of points in IR d partitioned into concept classes, where d is a fixed, but arbitrary, constant. We show that...
Computing Faces in Segment and Simplex Arrangements (1995)
Preliminary Version, Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos
For a set S of n line segments in the plane, we give the first work-optimal deterministic parallel algorithm for constructing their arrangement. It runs in O(log 2 n) time using O(n log n + k) work...
Michael T. Goodrich, Roberto Tamassia
Rooted trees are usually drawn planar and upward, i.e., without crossings and without any parent placed below its child. In this paper we investigate the area requirement of planar upward drawings of...
Efficient Piecewise-Linear Function Approximation Using the Uniform Metric (1994)
We give an O(n log n)-time method for finding a best k-link piecewise-linear function approximating an n-point planar data set using the well-known uniform metric to measure the error, ffl 0, of the...
Approximate Geometric Pattern Matching under Rigid Motions (1994)
Michael T. Goodrich, Mark W. Orletsky
We present techniques for matching point-sets in two and three dimensions under rigid-body transformations. We prove bounds on the worst-case performance of these algorithms to be within a small...
Parallel Algorithms for Higher-Dimensional Convex Hulls (1994)
Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos
We give fast randomized and deterministic parallel methods for constructing convex hulls in IR d , for any fixed d. Our methods are for the weakest shared-memory model, the EREW PRAM, and have...
Parallel Algorithms for Higher-Dimensional Convex Hulls (1994)
Preliminary Version, Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos
We give fast randomized and deterministic parallel methods for constructing convex hulls in IR d , for any fixed d. Our methods are for the weakest shared-memory model, the EREW PRAM, and have...
Characterization and Recognition of Point-Halfspace and Related Orders (1994)
Paul J. Tanenbaum, Michael T. Goodrich, Edward R. Scheinerman
. We characterize four classes of geometric membership and containment orders---structurally and in terms of forbidden subposets--- and present linear- or near linear-time recognition algorithms for...
Biased Finger Trees and Three-Dimensional Layers of Maxima (1994)
Mikhail J. Atallah, Michael T. Goodrich, Kumar Ramaiyer
We present a method for maintaining biased search trees so as to support fast finger updates (i.e., updates in which one is given a pointer to the part of the tree being changed). We illustrate the...
External-memory computational geometry, Proc. 34th Annu (1993)
Michael T. Goodrich, Jyh-Jong Tsay, Darren Erik Vengroff, Jeffrey Scott Vitters
In this paper we give new techniques for designing eficient algorithms for computational geometry prob-lems that are too large to be solved in internal mem-ory. We use these techniques lo develop...
External-memory computational geometry, Proc. 34th Annu (1993)
Michael T. Goodrich, Darren Erik Vengro, Jeffrey Scott Vitter
In this paper we give new techniques for designing efficiet algorithms for computatioal geometry problems that are too lawe to be solved i iteral memory. We use these techiques to develop optimal ad...
Geometric Pattern Matching under Euclidean Motion (1993)
Paul Chew, Michael T. Goodrich, Daniel P. Huttenlocher, Klara Kedem, Jon M. Kleinberg, Dina Kravets
Given two planar sets A and B, we examine the problem of determining the smallest " such that there is a Euclidean motion (rotation and translation) of A that brings each member of A within...
Geometric Pattern Matching under Euclidean Motion (1993)
L. Paul Chew, Michael T. Goodrich, Daniel P. Huttenlocher, Klara Kedem, Jon M. Kleinberg, Dina Kravets
Given two planar sets A and B, we examine the problem of determining the smallest " such that there is a Euclidean motion (rotation and translation) of A that brings each member of A within...
Point Probe Decision Trees for Geometric Concept Classes (1993)
Esther Arkin, Michael T. Goodrich, David Mount, Christine D. Piatko, Steven S. Skiena
A fundamental problem in model-based computer vision is that of identifying to which of a given set of concept classes of geometric models an observed model belongs. Considering a "probe"...
Approximate Parallel Prefix Computation and Its Applications (1993)
Michael T. Goodrich, Yossi Matias, Uzi Vishkin
In this paper we address two fundamental problems in parallel algorithm design---parallel prefix sums and integer sorting---and show that both of them can be approximately solved very quickly on a...
Point Probe Decision Trees for Geometric Concept Classes (1993)
Esther M. Arkin, Michael T. Goodrich, David Mount, Christine Piatko, Steven S. Skiena
A fundamental problem in model-based computer vision is that of identifying to which of a given set of concept classes of geometric models an observed model belongs. Considering a "probe"...
Michael T. Goodrich, Roberto Tamassia
We give new methods for maintaining a data structure that supports ray-shooting and shortest-path queries in a dynamically changing connected planar subdivision S. Our approach is based on a new...
Blocking for external graph searching (1993)
Mark H. Nodine, Michael T. Goodrich
In this paper, we consider the problem of using disk blocks e ciently in searching graphs that are too large to t in internal memory. Our model allows a vertex to be represented anynumber of times on...
Planar Separators and Parallel Polygon Triangulation (1992)
We show how to construct an O( p n)-separator decomposition of a planar graph G in O(n) time. Such a decomposition defines a binary tree where each node corresponds to a subgraph of G and stores an...
Fast Randomized Parallel Methods for Planar Convex Hull Construction (1991)
Mujtaba Ghouse, Michael T. Goodrich
We present a number of efficient parallel algorithms for constructing 2-dimensional convex hulls on a randomized CRCW PRAM. Specifically, we show how to build the convex hull of n pre-sorted points...
Dynamic Trees and Dynamic Point Location (1991)
Michael T. Goodrich, Roberto Tamassia
This paper describes new methods for maintaining a point-location data structure for a dynamically-changing monotone subdivision S. The main approach is based on the maintenance of two interlaced...
Dynamic trees and dynamic point location (1991)
Michael T. Goodrich, Roberto Tamassia
Abstract. This paper describes new methods for maintaining a point-location data structure for a dynamically changing monotone subdivision S. The main approach is based on the maintenance of two...
Dynamic trees and dynamic point location (1991)
Michael T. Goodrich, Roberto Tamassiat
We give new methods for maintaining a point-location data structure for a dynamically-changing monotone subdivision S. Our approa,ch is based on a new, optimal static point-location structure, where...
An Improved Ray Shooting Method for Constructive Solid Geometry Models via Tree Contraction (1990)
In the Constructive Solid Geometry (CSG) representation a geometric object is described as the hierarchical combination of a number of primitive shapes using the operations union, intersection,...
Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation (1989)
Michael T. Goodrich, S. Rao Kosaraju
We present optimal algorithms for sorting on parallel CREW and EREW versions of the pointer machine model. Intuitively, one can view our methods as being based on a parallel mergesort using linked...
Proceedings of the Eighth Annual Symposium on Computational Geometry, pages 102{ (1989)
Helmut Alt, Bernd Behrends, Helmut Alt, Michael Godau, Measuring In, Esther M. Arkin, ...
S. B. Mitchell. An e ciently computable metric for comparing polygonal shapes. In
Output-Sensitive Hidden Surface Elimination for Rectangles (1988)
Miwrail J. Atallah, Michael T. Goodrich, Mikhail J. Atallah, Xichael T. Goodrich
We present an algorithm for the well-known hidden-surface eIimination problem for rectangles, which is ab known as the window rendering problem. The time complexity of our algorithm is sensitive to...
Offset-Polygon Annulus Placement Problems
Gill Barequet, Amy J. Briggs, Matthew T. Dickerson, Michael T. Goodrich
An offset-polygon annulus region is defined in terms of a polygon P and a distance ffi ? 0 (offset of P ). In this paper we solve several containment problems for polygon annulus regions with respect...