\- \################################################################# \# topic headings \################################################################# \+
\- \!c:scg I was on the program committee for the 11th Symposium, 1995, and the 15th Symposium, 1999. I am the program chair for the theory track of the 17th Symposium, 2001.
\- \!c:focs I was on the program committee for the 34th Symposium, 1993.
\- \!c:stoc I was on the program committee for the 26th Symposium, 1994, the 32nd Symposium, 2000, and the 35th Symposium, 2003.
\- \!c:soda I was on the program committee for the 7th Symposium, 1996, and the 11th Symposium, 2000. I was also program chair for the 13th Symposium, 2002.
\- \!c:wads I was on the program committee for the 5th Workshop, 1997.
\- \!j:algs I have been on the editorial board since 1994.
\- \!j:sjc \!j:jga I have been on the editorial board since 1995.
\- \!top A listing of my publications in BibTeX format is also available, and is indexed from the entries in this file. Many of my recent papers can be found at the ACM Computing Research Repository and/or the arXiv.org math preprint server. I also maintain a database of citations to my own papers by other authors.
Caveat: Most of the papers here are subject to some sort of copyright restriction.
\- \!c:stoc The Hypertext Bibliography Project at MIT also includes listings of my STOC papers.
\- \!c:soda The Hypertext Bibliography Project at MIT also includes listings of my SODA papers.
\- \!c:focs The Hypertext Bibliography Project at MIT also includes listings of my FOCS papers.
\- \!j:ic The Hypertext Bibliography Project at MIT also includes listings of my Inf.&Comput. papers.
\- \!j:acm The Hypertext Bibliography Project at MIT also includes listings of my J. ACM papers.
\- \!kbest See also my bibliography of algorithms for k shortest paths, which also includes related work on other "kth best solution" problems, especially the k smallest spanning trees. Victor Jiménez and Andrés Marzal maintain a web page on algorithms for k shortest paths.
\- \!param These papers concern problems in which some parameter or parameters is free, and one must explore the space of different solutions obtained for different values of these parameters. The k-set problem can be viewed in this framework as a form of parametric median-finding, in which the set of elements have values that are linear functions of a single time parameter; I have also looked at other similar parametric matroid problems as well as some parametric geometry problems.
\- \!pure Most of my research is in the design and analysis of algorithms, but some of my papers are completely non-algorithmic, instead consisting of theorems about graphs or combinatorial geometry. Some other papers, while primarily about algorithms, also contain non-algorithmic content of independent interest.
\- \!rec These papers are mainly for fun, although there is also some serious research content to some of them. See also my recreational mathematics web pages.
\- \!graph:sgi Subgraph isomorphism is a very general form of pattern matching in which one attempts to find a target graph as a subgraph of a larger input graph. It is NP-complete, but it has many applications and algorithms are known for many special cases. See also my bibliography of subgraph isomorphism algorithms and applications, which I collected for my SODA 95 paper.
\- \!a:cgitf The Computational Geometry Impact Task Force was organized by Bernard Chazelle, and consisted of N. Amenta, T. Asano, G. Barequet, M. Bern, J.-D. Boissonnat, J. Canny, B. Chazelle, K. Clarkson, D. Dobkin, B. Donald, R. S. Drysdale, H. Edelsbrunner, D. Eppstein, A. R. Forrest, S. Fortune, K. Goldberg, M. Goodrich, L. J. Guibas, P. Hanrahan, C. M. Hoffman, D. Huttenlocher, H. Imai, D. Kirkpatrick, D. T. Lee, K. Mehlhorn, V. Milenkovic, J. Mitchell, M. Overmars, R. Pollack, R. Seidel, M. Sharir, J. Snoeyink, G. Toussaint, S. Teller, H. Voelcker, E. Welzl, and C. Yap. (I am not listing this under my co-author publication lists for each individual member of the task force.)
\- \################################################################# \# the papers themselves \################################################################# \# start unnumbered list of papers \# roughly sorted by date of final version \+ \!top \!geom \!graph \!auth \!subj \!year \!conf \!jour
This note in the TeX user's group newsletter described a set of macros for drawing trees, using TeX's boxes-and-glue mechanisms to line up the nodes at each level of the tree.
(BibTeX -- TeX source code -- Citations -- Nelson Beebe's TeX tree drawing bibliography)
\- \!all \!misc \!a:solo \!c:other \!j:no \!p:proginv \!y:1985
Program transformation. Given a (lisp) program for an invertible function, how do we automatically find a program for the inverse function? Considers more general simultaneous inverses of multiple functions. The heuristic part involves type inference for finding conditionals to use in certain if statements.
(BibTeX -- MacLISP source code -- Kawabe's Common Lisp port -- Citations -- CiteSeer)
\- \!all \!rec \!a:solo \!c:no \!j:other \!p:cryptarithm \!y:1987
A cryptarithm (also known as an alphametic) is a puzzle in which the digits of a mathematical formula (typically addition of two large numbers) are replaced by letters; the goal is to determine which letter stands for which digits. If arithmetic is done in a polynomially large radix, the problem becomes NP-complete.
(BibTeX -- Full paper -- Citations)
\- \!all \!molbio \!a:galil \!a:giancarlo \!p:speeding \!c:focs \!c:other \!j:book \!y:1988 \!y:1990
The FOCS and Positano versions of this paper merged my results on a dynamic program used for RNA secondary structure prediction, with Raffaele's on sequence comparison. The Bethesda talk and the TR version both used the longer title "Speeding up dynamic programming with application to the computation of RNA structure", and included only the RNA result, which used a mild convexity assumption on certain costs to save two orders of magnitude in total time. This work incited a boom in computational biology within the theory community that is still going strong. But the RNA results were quickly improved by a log factor [Aggarwal et al. at the same FOCS] and never made it into a journal paper.
(Bibtex: Positano, FOCS -- Citations -- Citations of "Efficient algorithms..." -- MIT hypertext bibliography -- CiteSeer)
\- \!all \!molbio \!a:solo \!y:1989
Includes results from "Speeding up dynamic programming", "Sequence comparison with mixed convex and concave costs", and "Sparse dynamic programming".
(BibTeX)
\- \!all \!molbio \!a:solo \!c:no \!j:algs \!p:mixed \!y:1988 \!y:1990
Gives an algorithm for finding the minimum number of mutations needed to transform one input string into another, in a general model in which substrings may be inserted or deleted at a cost depending nonlinearly on the substring length. The time bound depends on the number of times the second derivative of the cost function changes sign.
(BibTeX -- Citations -- ACM DL)
\- \!all \!misc \!par \!a:solo \!c:icalp \!j:sjc \!y:1988 \!y:1990
Automata theory. A reset sequence for a DFA is an input such that, no matter which state the DFA starts in, it ends up after the input in a known state. These have been used by Natarajan and Goldberg for certain robot motion planning problems (in fact the conference version of this paper used the title "Reset sequences for finite automata with application to design of parts orienters"), and also in coding theory where they arise in the design of self-synchronizing codes. This paper considers DFAs in which the transition functions respect a given cyclic ordering of the states, and shows that their shortest reset sequences can be found quickly. It also considers parallel algorithms for the problem. There remains open a gap between n2 and n3 in the maximum length of reset sequences for general automata.
(BibTeX -- Citations -- CiteSeer -- ACM DL (ICALP) -- ACM DL (SJC))
\- \!all \!misc \!par \!a:solo \!y:1989
(BibTeX)
\- \!all \!par \!graph:all \!graph:misc \!survey \!a:galil \!c:icalp \!j:other \!y:1988 \!y:1989
This survey on parallel algorithms emphasized the use of basic subroutines such as prefix sums, Euler tours, ear decomposition, and matrix multiplication for solving more complicated graph problems.
(BibTeX -- Citations -- CiteSeer -- ACM DL (ARCS) -- ACM DL (ICALP))
\- \!all \!geom:all \!geom:misc \!pure \!a:bern \!a:plassman \!a:yao \!c:no \!j:book \!y:1991
The total complexity of the cells in a line arrangement that are cut by another line is at most 15n/2. The complexity of cells cut by a convex k-gon is O(n α(n,k)). The first bound is tight, but it remains open whether the second is, or whether only linear complexity is possible.
\- \!all \!pure \!geom:all \!geom:tri \!a:bern \!a:yao \!c:icalp \!j:ijcga \!y:1991
Discusses the expected behavior of Delaunay triangulations for points chosen uniformly at random (without edge effects). The main result is that within a region containing n points, the expected maximum degree is bounded to within a constant factor of log n / log log n.
(BibTeX -- Citations -- CiteSeer -- ACM DL -- ACM DL (2))
\- \!all \!graph:all \!graph:sgi \!graph:planar \!par \!a:chrobak \!c:no \!j:tcs \!p:outdegree \!y:1991
Describes efficient sequential and parallel algorithms for orienting the edges of an undirected planar graph so that each vertex has few outgoing edges. From such an orientation one can test in constant time whether a given edge exists. \!par One consequence is a parallel algorithm to list all subgraphs isomorphic to K3 or K4. \!par \!graph:sgi More recently this paper has been cited for its applications to scheduling update operations in parallel finite element methods. \!graph:sgi
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!pure \!graph:all \!graph:random \!a:feigenbaum \!a:li \!c:no \!j:dm \!y:1991
Considers partitions of the vertices of a graph into equal subsets, with few pairs of subsets connected by edges. (Equivalently we view the graph as a subgraph of a product in which one factor is sparse.) A random graph construction shows that such a factorization does not always exist.
(BibTeX -- Full paper -- CiteSeer -- ACM DL)
\- \!all \!par \!graph:all \!graph:match \!a:asuri \!a:dillencourt \!a:lueker \!a:molodowitch \!c:no \!j:no \!y:1992
We later discovered that the same results were published in a SPAA paper by Greg Shannon.
(BibTeX)
\- \!all \!pure \!geom:all \!geom:kset \!a:sol \!c:no \!j:no \!y:1992
I used genetic algorithms to search for small configurations of points bisected by lines in many combinatorially distinct ways.
\- \!all \!geom:all \!geom:cluster \!a:overmars \!a:rote \!a:woeginger \!c:no \!j:dcg \!y:1992
Uses dynamic programming to choose sets of k points optimizing various criteria on the quality of their convex hull (in particular area). The time complexity (cubic in n) was later improved to quadratic in my paper "New algorithms for minimum area k-gons", which however continues to use the same dynamic program as a subroutine.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!misc \!a:hemachandra \!a:tisdall \!a:yener \!c:other \!j:mst \!y:1989 \!y:1990 \!y:1992
Structural complexity theory. Constructs oracles in which BPP (a probabilistic complexity class) and UP (the class of problems with a unique "witness") contain languages that in a very strong sense are not contained in the other class. The conference version used the title "Probabilistic and unambiguous computation are incomparable".
(BibTeX: ICCI, MST -- Citations: ICCI, MST -- CiteSeer)
\- \!all \!graph:all \!mst \!graph:dyn \!graph:planar \!a:italiano \!a:tamassia \!a:tarjan \!a:westbrook \!a:yung \!c:soda \!j:algs \!p:eittwy \!y:1990 \!y:1992 \!y:1993
The complement of a minimum spanning tree is a maximum spanning tree in the dual graph. By applying this fact we can use a modified form of Sleator and Tarjan's dynamic tree data structure to update the MST in logarithmic time per update.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!pure \!geom:all \!geom:tri \!a:solo \!c:no \!j:cgta \!y:1990 \!y:1992
Given a collection of points in convex position, the sharpest angle determined by any triple can be found as a corner of a triangle in the farthest point Delaunay triangulation.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!par \!pure \!graph:all \!graph:misc \!a:solo \!c:no \!p:serpar \!j:ic \!y:1992
Characterizes two-terminal series graphs in terms of a tree-like structure in their ear decompositions. \!pure Uses this characterization to construct parallel algorithms that recognize these graphs and construct their series-parallel decompositions. \!pure
(BibTeX -- Citations -- MIT hypertext bibliography -- CiteSeer -- ACM DL)
\- \!all \!kbest \!graph:all \!mst \!geom:all \!mst \!a:solo \!c:swat \!j:bit \!p:kmst \!y:1990 \!y:1992
By removing edges not involved in some solution, and contracting edges involved in all solutions, we reduce the problem to one in a graph with O(k) edges and vertices. This simplification step transforms any time bound involving m or n to one involving min(m, k) or min(n, k) respectively. This paper also introduces the geometric version of the k smallest spanning trees problem (the graph version was long known) which it solves using order (k+1) Voronoi diagrams.
(BibTeX -- Citations -- ACM DL (SWAT) -- ACM DL (BIT))
\- \!all \!molbio \!usesgeom \!a:galil \!a:giancarlo \!a:italiano \!c:soda \!p:sparsedp \!y:1990
Considers sequence alignment and RNA structure problems in which the solution is constructed by piecing together some initial set of fragments (e.g. short sequences that match exactly). The method is to consider a planar point set formed by the fragment positions in the two input sequences, and use plane sweep to construct a cellular decomposition of the plane similar to the rectilinear Voronoi diagram.
\- \!all \!molbio \!usesgeom \!a:galil \!a:giancarlo \!a:italiano \!j:acm \!p:sparsedp \!y:1989 \!y:1992
First half of the journal version of Sparse dynamic programming.
(Citations -- MIT hypertext bibliography)
\- \!all \!molbio \!usesgeom \!a:galil \!a:giancarlo \!a:italiano \!j:acm \!p:sparsedp \!y:1989 \!y:1992
Second half of the journal version of Sparse dynamic programming.
(Citations -- MIT hypertext bibliography)
\- \!all \!geom:all \!geom:tri \!a:bern \!c:scg \!j:ijcga \!p:nonobtuse \!y:1991 \!y:1992
Any simple polygon can be triangulated with quadratically many nonobtuse triangles. Mostly subsumed by recent results of Bern et al described in "Faster circle packing".
(BibTeX -- Citations -- CiteSeer)
\- \!all \!molbio \!a:galil \!a:giancarlo \!a:italiano \!c:other \!j:book \!y:1991 \!y:1993 \!survey
Surveys results on speeding up certain dynamic programs used for sequence comparison and RNA structure prediction.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!pure \!geom:all \!geom:kset \!a:solo \!c:no \!j:jct \!y:1991 \!y:1993
Reduces the polylogarithmic term in an upper bound for the three-dimensional k-set problem.
A bug in the proof was corrected by Nivasch and Sharir.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!graph:all \!graph:sgi \!graph:planar \!ramsey \!pure \!a:solo \!c:no \!j:jgt \!p:conmin \!y:1992 \!y:1993
It was known that planar graphs have O(n) subgraphs isomorphic to K3 or K4. This paper characterizes the subgraphs for which such a linear bound holds: they are exactly the 3-connected planar graphs. Please note that the Tech. Rep. version had a bug (in a supposed generalization of the result to nonplanar graph families) which was corrected in the journal version.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!geom:all \!geom:tri \!a:bern \!a:edelsbrunner \!a:smitchell \!a:tan \!c:other \!j:dcg \!y:1992 \!y:1993
One standard way of constructing Delaunay triangulations is by iterated local improvement, in which each step flips the diagonal of some quadrilateral. For many other optimal triangulation problems, flipping is insufficient, but the problems can instead be solved by a more general local improvement step in which a new edge is added to the triangulation, cutting through several triangles, and the region it cuts through is retriangulated on both sides.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!geom:all \!geom:misc \!param \!a:bern \!a:dobkin \!a:grossman \!c:soda \!j:algo \!y:1990 \!y:1994
An investigation of 3d visibility problems in which the viewing position moves along a straight flight path, with various assumptions on the complexity of the viewed scene.
\- \!all \!par \!graph:all \!graph:misc \!a:chrobak \!a:italiano \!a:yung \!c:soda \!j:no \!y:1991
Described slightly superlinear algorithms for partitioning a tree into a given number of subtrees, making them all as short as possible. Frederickson at the same conference further improved the sequential time to linear. There may still be something worth publishing in the parallel algorithms.
\- \!all \!geom:all \!geom:tri \!geom:qt \!a:bern \!a:gilbert \!c:focs \!j:jcss \!p:pgood \!y:1990 \!y:1994
Uses quadtrees to construct triangulations with extra Steiner vertices added to the original input. Triangulates planar point sets and polygons, with all angles bounded away from zero, using a number of triangles within a constant of optimal. Triangulates planar point sets with all angles non-obtuse, using linearly many triangles. Triangulates higher dimensional point sets with no small solid angles and a number of simplices within a constant of optimal. Augments any higher dimensional point set so the Delaunay triangulation has linear complexity.
(BibTeX -- Citations -- Preliminary copy of journal version -- MIT hypertext bibliography -- CiteSeer -- ACM DL (JCSS))
\- \!all \!geom:all \!geom:dyn \!geom:cluster \!geom:lp \!a:solo \!c:focs \!j:ojc \!p:3lp \!y:1991 \!y:1992
Uses Dobkin-Kirkpatrick hierarchies to perform linear programming queries in the intersection of several convex polyhedra. By maintaining a collection of halfspaces as several subsets, represented by polyhedra, this leads to algorithms for a dynamic linear program in which updates change the set of constraints. The fully dynamic results have largely been subsumed by Agarwal and Matoušek, but this paper also includes polylog time results for semi-online problems, and uses them to give a fast randomized algorithm for the planar 2-center problem (later improved by various authors, most recently in "Faster Construction of Planar Two-Centers", which re-uses the data structures described here).
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!misc \!a:solo \!c:no \!j:no \!y:1991
Considers persistence for a naive form of dynamic algorithm in which each update rebuilds a static solution. The space bounds for this can often be reduced by maintaining an offline solution over a sequence of updates constructed from an Euler tour of the persistent update history tree.
(BibTeX)
\- \!all \!pure \!geom:all \!geom:tri \!geom:qt \!geom:approx \!mst \!a:solo \!c:soda \!j:dcg \!p:mwst \!y:1991 \!y:1992 \!y:1994
Quadtree based triangulation gives a large but constant factor approximation to the minimum weight triangulation of a point set or convex polygon, allowing extra Steiner points to be added as vertices. Includes proofs of several bounds on triangulation weight relative to the minimum spanning tree or non-Steiner triangulation, and a conjecture that for convex polygons the only points that need to be added are on the polygon boundary.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!geom:all \!geom:cluster \!ramsey \!a:solo \!c:soda \!p:kgon \!y:1991 \!y:1992
Shows that the minimum area polygon containing k of n points must be near a line determined by two points, and uses this observation to find the polygon quickly. Merged with "Iterated nearest neighbors and finding minimal polytopes" in the journal version.
\- \!all \!geom:all \!geom:cluster \!a:erickson \!c:no \!j:no \!y:1992
Looks at space complexity of finding minimum simplices -- solves the problem in O(n2) space and O(nd) time (matching the best known time bounds) or in linear space at the expense of an additional log in time. Also finds one-dimensional multiplicatively weighted Voronoi diagrams in linear time for sorted inputs (O(n log n) was known).
(BibTeX -- Citations -- Jeff's pub list entry)
\- \!all \!geom:all \!geom:nn \!geom:cluster \!geom:deep \!a:erickson \!c:soda \!j:dcg \!p:inn \!y:1992 \!y:1993 \!y:1994 \!kbest
Showed that for various optimization criteria, the optimal polygon containing k of n points must be near one of the points, hence one can transform time bounds involving several factors of n to bounds linear in n but polynomial in k. Used as a subroutine are data structures for finding several nearest neighbors in rectilinear metric spaces, and algorithms for finding the deepest point in an arrangement of cubes or spheres.
(BibTeX -- Citations -- Jeff's pub list entry -- CiteSeer)
\- \!all \!kbest \!geom:all \!mst \!a:solo \!c:no \!j:ijcga \!y:1992 \!y:1994
"Finding the k smallest spanning trees" used higher order Voronoi diagrams to reduce the geometric k smallest spanning tree problem to the graph problem. Here I instead use nearest neighbors for a modified distance function where the bottleneck shortest path length is subtracted from the true distance between points. The result improves the planar time bounds and extends more easily to higher dimensions.
\- \!all \!param \!pure \!geom:all \!mst \!a:aronov \!a:bern \!c:no \!j:dcg \!y:1994
Given a d-dimensional set of n points, the number of combinatorially different minimum spanning trees that can be formed by adding one more point is within a polylogarithmic factor of nd.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!pure \!graph:all \!graph:sgi \!a:solo \!c:no \!j:ipl \!p:asgi \!y:1994
For any sparse family of graphs, one can list in linear time all complete bipartite subgraphs of a graph in the family. There are O(n) complete bipartite subgraphs of a graph in the family, and the sum of the numbers of vertices in these subgraphs is also O(n).
Nowadays these results can also be interpreted as a form of formal concept analysis. If a set of objects and attributes is sparse (e.g., if it is generated by adding objects and attributes one at a time, where each newly-added object is given O(1) attributes and each newly-added attribute is held by O(1) objects) then the total size of all concepts in its concept lattice is linear, and this lattice may be generated in linear time.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!graph:all \!graph:dyn \!mst \!geom:all \!geom:dyn \!mst \!a:solo \!c:wads \!j:algs \!y:1991 \!y:1992 \!y:1994
Given a sequence of edge insertions and deletions in a graph, finds the corresponding sequence of minimum spanning tree changes, in logarithmic time per update. Similarly solves the planar geometric version of the problem (using a novel "mixed MST" formulation in which part of the input is a graph and part is a point set) in time O(log2 n) for the Euclidean metric and O(log n log log n) for the rectilinear metric.
(BibTeX -- Citations -- CiteSeer -- ACM DL (JA))
\- \!all \!geom:all \!geom:dyn \!mst \!geom:nn \!a:solo \!j:dcg \!y:1992 \!y:1995 \!p:dynmst
Shows that bichromatic nearest neighbors can be maintained under point insertion and deletion essentially as quickly as known solutions to the post office problem, and that the minimum spanning tree can be maintained in the same time except for an additive O(sqrt n) needed for solving the corresponding graph problem. TR 92-88's title was actually "Fully dynamic maintenance of Euclidean minimum spanning trees and maxima of decomposable functions". TR 92-05's title left out the part about maxima; that version gave a slower algorithm superseded by the result in 92-88.
(BibTeX -- Citations -- Closest pair project page -- CiteSeer)
\- \!all \!geom:all \!geom:dyn \!mst \!geom:nn \!a:agarwal \!a:matousek \!c:focs \!p:dynhalf \!y:1992
This conference paper merged my results from "Dynamic Euclidean minimum spanning trees" with results of my co-authors on nearest neighbors and halfspace range searching.
\- \!all \!graph:path \!kbest \!rec \!survey \!a:solo \!c:no \!j:other \!p:egypt \!y:1995
Number theory. I survey and implement in Mathematica several methods for representing rational numbers as sums of distinct unit fractions. One of the methods involves searching for paths in a certain graph using a k shortest paths heuristic.
(BibTeX -- Citations -- Also available in HTML and Mathematica notebook formats)
\- \!all \!geom:all \!geom:misc \!graph:dyn \!a:solo \!c:no \!j:algo \!p:csg \!y:1992 \!y:1995
Finds boundary representations of CSG objects. Uses techniques from dynamic graph algorithms, including a tree partitioning technique of Frederickson and a new data structure for maintaining the value of a Boolean expression with changing variables in time O(log n / log log n) per update.
\- \!all \!geom:all \!geom:tri \!a:solo \!y:1991
This was merged into "triangulating polygons without large angles". We find a grid-like structure in the input polygon, which is then thinned out using a complicated divide-and-conquer scheme. The results are largely subsumed by the method of Bern et al. described in "Faster circle packing".
(BibTeX)
\- \!all \!geom:all \!geom:tri \!a:bern \!a:dobkin \!c:scg \!j:ijcga \!p:nolarge \!y:1992 \!y:1995
Follows up "Polynomial size non-obtuse triangulation of polygons"; improves the number of triangles by relaxing the requirements on their angles. Again mostly subsumed by results of Bern et al described in "Faster circle packing".
(BibTeX -- Citations -- CiteSeer)
\- \!all \!survey \!geom:all \!geom:tri \!a:bern \!c:no \!j:book \!p:meshgen \!y:1992 \!y:1995
Considers both heuristics and theoretical algorithms for finding good triangulations and tetrahedralizations for surface interpolation and unstructured finite element meshes. Note that the online copy here omits the figures; also online is this paper's bibliography.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!geom:all \!geom:deep \!geom:circle \!a:miller \!a:teng \!c:scg \!j:other \!y:1993 \!y:1995
Teng and others previously showed that certain geometric graphs had small separators that could be found by lifting the graph to a sphere one dimension up and choosing a random great circle. Here we show that epsilon-cuttings and the method of conditional expectations can be used to guide a deterministic prune-and-search method for the same problem. Applications include finding the intersection graph of a collection of spheres and computing or approximating the maximum number of spheres having a common intersection.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!graph:all \!graph:dyn \!mst \!kbest \!a:galil \!a:italiano \!a:nissenzweig \!c:focs \!j:acm \# submitted to Leighton for JACM, 18 Jan 1993 \# revised May 1996 \!p:sparsification \!y:1992 \!y:1993 \!y:1997
Uses a divide and conquer on the edge set of a graph, together with the idea of replacing subgraphs by sparser certificates, to make various dynamic algorithms as fast on dense graphs as they are on sparse graphs. Applications include random generation of spanning trees as well as finding the k minimum weight spanning trees for a given parameter k.
(BibTeX -- Citations -- MIT hypertext bibliography -- ACM DL)
\- \!all \!graph:all \!graph:dyn \!mst \!kbest \!a:galil \!a:italiano \!c:no \!y:1993
Saves a log factor over dynamic graph algorithms in "Sparsification" and their applications, by dividing vertices instead of edges. Merged into the journal version of "Sparsification".
(BibTeX -- Citations -- CiteSeer)
\- \!all \!graph:all \!graph:dyn \!mst \!graph:planar \!kbest \!a:galil \!a:italiano \!a:spencer \!c:stoc \!p:egis \!y:1993
Replaces portions of a hierarchical separator decomposition with smaller certificates to achieve fast update times for various dynamic planar graph problems. Applications include finding the k best spanning trees of a planar graph.
(BibTeX -- Citations -- MIT hypertext bibliography)
\- \!all \!graph:all \!graph:dyn \!mst \!graph:planar \!kbest \!a:galil \!a:italiano \!a:spencer \!j:jcss \!p:egis \!y:1996
First half of journal version of Separator based sparsification for dynamic planar graph algorithms.
\- \!all \!graph:all \!graph:dyn \!graph:planar \!a:galil \!a:italiano \!a:spencer \!j:sjc \!p:egis \!y:1996 \!y:1999
Second half of journal version of Separator based sparsification for dynamic planar graph algorithms.
\- \!all \!geom:all \!geom:qt \!geom:tri \!geom:nn \!kbest \!a:dickerson \!c:no \!j:cgta \!p:k-neighbors \!y:1996
Combines a method from "Provably good mesh generation" for finding sparse high-dimensional Delaunay triangulations, a method of Dickerson, Drysdale, and Sack ["Simple algorithms for enumerating interpoint distances", IJCGA 1992] for using Delaunay triangulations to search for nearest neighbors, and a method of Frederickson for speeding up tree-based searches. The results are fast algorithms for several proximity problems such as finding the k nearest neighbors to each point in a given point set.
(BibTeX -- Full paper -- Citations -- CiteSeer -- ACM DL)
\- \!all \!geom:all \!geom:dyn \!mst \!a:solo \!c:soda \!j:cgta \!p:avgdynopt \!y:1993 \!y:1994 \!y:1996
The Tech. Report used the more informative title "Updating widths and maximum spanning trees using the rotating caliper graph", which I also used for the journal submission, but the referees made me change it back. Dynamic geometry in a model of Mulmuley and Schwarzkopf in which insertions and deletions are chosen randomly among a worst-case pool of points. This paper introduces several fundamental techniques including the rotating caliper graph of a point set and a method for performing decomposible range queries in the average case setting. It has also since inspired the use of a similar model in dynamic graph algorithms.
(BibTeX -- SODA paper -- Full paper -- Citations -- CiteSeer -- ACM DL)
\- \!all \!geom:all \!geom:dyn \!a:solo \!c:wcg \!y:1993
\- \!all \!geom:all \!geom:dyn \!geom:deep \!a:dobkin \!c:scg \!p:disc \!y:1993
Measures how well a sample of points from a set works as a discrete approximation to the continuous measure of shapes in the set, using algorithms based on Overmars and van Leeuwen's dynamic convex hull data structure. Some versions of the problem also involve subroutines for finding the deepest point in an arrangement of quadrants or orthants.
This paper was merged with results of Mitchell to form the journal version, "Computing the discrepancy with applications to supersampling patterns".
\- \!all \!geom:all \!geom:dyn \!geom:deep \!a:dobkin \!a:dmitchell \!j:other \!p:supersample \!y:1996
Combines "Computing the discrepancy" with experimental results of Mitchell on the discrepancies of various point sets, emphasizing the application of low-discrepancy sets to anti-aliasing in raytraced graphics.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!geom:all \!geom:circle \!geom:tri \!mst \!graph:dyn \!a:solo \!c:no \!j:ijcga \!p:cpack \!y:1994 \!y:1997 \# submitted to D.T.Lee for IJCGA, 31 Oct 1994 \# accepted subject to revision by Goodrich 15 Jun 1995 \# sent final version 29 Jun 1995 \# recd & returned offprint request listing as V7 N5 (Oct 1997), 28 Jul 1997
Speeds up a triangulation algorithm of Bern et al. ["Linear-Size Nonobtuse Triangulation of Polygons"] by finding a collection of disjoint circles which connect up the holes in a non-simple polygon. The method is to use a minimum spanning tree to find a collection of overlapping circles, then shrink them one by one to reduce the number of overlaps, using Sleator and Tarjan's dynamic tree data structure to keep track of the connectivity of the shrunken circles.
\- \!all \!geom:all \!geom:approx \!geom:deep \!geom:lp \!stat \!a:clarkson \!a:miller \!a:sturtivant \!a:teng \!c:scg \!j:ijcga \!y:1993 \!y:1996
Given a collection of n sites, a center point is a point (not necessarily a site) such that no hyperplane through the centerpoint partitions the collection into a very small and a very large subset. Center points have been used by Teng and others as a key step in the construction of geometric separators. One can find a point with this property by choosing a random sample of the collection and applying linear programming, but the complexity of that method grows exponentially with the dimension. This paper proposes an alternate method that produces lower quality approximations (in terms of the size of the worst hyperplane partition) but takes time polynomial in both n and d.
(BibTeX -- Citations -- Full paper and source code -- CiteSeer)
\- \!all \!geom:all \!mst \!geom:path \!graph:all \!graph:match \!tsp \!pure \!a:bern \!c:scg \!p:subadditive \!j:no \!y:1993
For many geometric graph problems for points in the unit square, such as minimum spanning trees, matching, and traveling salesmen, the sum of edge lengths is O(sqrt n) and the sum of dth powers of edge lengths is O(log n). We provide a "gap theorem" showing that if these bounds do not hold for a class of graphs, both sums will instead be Omega(n). For traveling salesmen the O(log n) bound is tight but for some other graphs the sum of dth powers of edge lengths is O(1).
(BibTeX -- Citations -- Preprint of SCG version -- CiteSeer)
\- \!all \!geom:all \!geom:tri \!geom:cluster \!geom:nn \!geom:qt \!par \!a:bern \!a:teng \!c:wads \!j:ijcga \# sent to DT Lee for IJCGA, 26 Jul 1996 \# accepted subject to revisions 18 Feb 1997 \# returned final version 25 May 1999 \!p:parallel-qt \!y:1993 \!y:1994 \!y:1999
A parallelization of the quadtree constructions in "Provably good mesh generation", in an integer model of computation, based on a technique of sorting the input points using values formed by shuffling the binary representations of the coordinates. A side-effect is an efficient construction for the "fair split tree" hierarchical clustering method used by Callahan and Kosaraju for various nearest neighbor problems.
(BibTeX -- CiteSeer -- Citations -- ACM DL)
\- \!all \!usesgeom \!graph:all \!graph:dyn \!graph:misc \!a:solo \!c:soda \!j:other \!y:2000 \# sent to Networks 16 Nov 1994 \# recd referee reports May 1998 \# returned revision 23 Jul 1998 \# accepted 11 Oct 1999 \# returned galleys 29 Dec 1999 \!y:1993 \!y:1994
Speeds up the worst case time per pivot for various versions of the network simplex algorithm for minimum cost flow problems. Uses techniques from dynamic graph algorithms as well as some simple geometric data structures.
\- \!all \!kbest \!graph:all \!graph:path \!a:solo \!c:focs \!j:sjc \# sent to SICOMP 14 Aug 1995 \# attempted to return revision 31 Mar 1997 but email refused (too big). \# trying again with uuencoded compressed postscript... \# still didn't work, put it on the web page \# accepted 22 Apr 1997 \!p:kpath \!y:1994 \!y:1998
Finds multiple short paths connecting two terminals in a graph (allowing repeated vertices and edges in the paths) in constant time per path after a preprocessing stage dominated by a single-source shortest path computation. Applications include dynamic programs for the knapsack problem, biological sequence alignment, and maximum inscribed polygons.
(BibTeX -- Full paper -- Citations -- \# http://www-scf.usc.edu/~graehl/kbest.zip no longer there? 31 Oct 1998 Graehl implementation -- Jiménez-Marzal implementations -- Shibuya implementation -- Martins implementation -- CiteSeer: TR '94, SJC '98 -- ACM DL)
\- \!all \!pure \!geom:all \!geom:tri \!a:bern \!a:chew \!a:ruppert \!c:other \!c:soda \!j:no \!p:dihedral \!y:1994 \!y:1995
Any d-dimensional point set can be triangulated with O(nceil(d/2)) simplices, none of which has an obtuse dihedral angle. No bound depending only on n is possible if we require the maximum dihedral angle to measure at most 90-epsilon degrees or the minimum dihedral to measure at least epsilon. Includes a classification of simplices in terms of their bad angles.
(BibTeX -- SODA paper -- Citations -- CiteSeer)
\- \!all \!graph:all \!graph:sgi \!graph:planar \!a:solo \!c:soda \!j:jga \# sent to Tamassia for JGAA, 19 Dec 1995 \# accepted 7 Jan 1997 \!p:psgi \!y:1994 \!y:1995 \!y:1999
Uses an idea of Baker to cover a planar graph with subgraphs of low treewidth. As a consequence, any fixed pattern can be found as a subgraph in linear time; the same methods can be used to solve other planar graph problems including vertex connectivity, diameter, girth, induced subgraph isomorphism, and shortest paths. A companion paper presents a result announced in the conference version of this paper, that exactly characterizes the minor-closed graph families for which the same techniques apply.
(BibTeX -- Citations -- Citations from MIT hypertext bibliography -- CiteSeer (SODA) -- CiteSeer (JGAA))
\- \!all \!pure \!param \!usesgeom \!geom:all \!geom:kset \!graph:all \!mst \!a:solo \!c:stoc \!p:geomlb \!j:dcg \# sent to R.Pollack for DCG 8 Nov 1996 \# accepted subject to (extremely minor) revisions 18 Feb 1997 \# returned galleys 29 Jul 1997 \!y:1995 \!y:1998
Considers graphs in which edge weights are linear functions of time. Shows nonlinear lower bounds on the number of different minimum spanning trees appearing over time by translation from geometric problem of lower envelopes of line segments. A matroid generalization has a better lower bound coming from many faces in line arrangements, and the uniform matroid problem is equivalent to the geometric k-set problem.
(BibTeX -- Citations -- CiteSeer -- MIT hypertext bibliography)
\- \!all \!param \!pure \!geom:all \!geom:lp \!geom:zono \!a:bern \!a:guibas \!a:hershberger \!a:suri \!a:wolter \!c:esa \!j:no \!p:centroid \!y:1995
Given a set of points with weights that are not known precisely, but are known to fall within some range, considers the possible weighted centroids arising from different choices of weights in each range. The combinatorics of this problem are closely connected with those of zonotopes.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!graph:all \!graph:color \!exponential \!a:beigel \!c:focs \!p:3color \!y:1995
Speeds up 3-coloring by solving a harder problem: constraint satisfaction in which each variable can take on one of three values and each constraint forbids a pair of variable assignments. The detailed solution involves several long hairy case analyses. Similar methods apply also to 3-list-coloring, 3-edge-coloring, and 3-SAT. The 3-SAT algorithm is fixed-parameter tractible in that it is polynomial time when the number of 3-variable clauses is O(log n). Merged into 3-coloring in time O(1.3289^n) for the journal version.
(BibTeX -- Citations -- DIMACS abstract and slides -- CiteSeer)
\- \!all \!survey \!geom:all \!geom:tri \!geom:approx \!tsp \!a:bern \!c:no \!j:book \!y:1996
Considers problems for which no polynomial-time exact algorithms are known, and concentrates on bounds for worst-case approximation ratios, especially those depending intrinsically on geometry rather than on more general graph theoretic or metric space formulations. Includes sections on the traveling salesman problem, Steiner trees, minimum weight triangulation, clustering, and separation problems.
(BibTeX -- Citations -- ACM DL)
\- \!all \!pure \!geom:all \!geom:nn \!a:solo \!c:no \!y:1992
Any connected nearest neighbor forest with diameter D has O(D6) vertices. This was later further improved to O(D5) and merged with results of Paterson and Yao into "On nearest neighbor graphs".
(BibTeX -- Citations -- CiteSeer)
\- \!all \!graph:all \!graph:misc \!misc \!a:solo \!c:no \!j:algs \!y:1995 \!y:1997 \# sent to Zvi for J. Alg. 17 Aug 1995 \# accepted subject to revision 3 Jan 1996 \# returned revision 6 Aug 1996 \# returned galleys 17 Feb 1997
Describes data structures for maintaining the solution of a dynamically changing subset sum problem, and uses them to find a cut in a graph minimizing the difference between the heaviest and lightest cut edge.
\- \!all \!misc \!param \!usesgeom \!geom:all \!geom:kset \!geom:lp \!stat \!a:hirschberg \!c:wcg \!j:algs \!p:maxwtavg \!y:1995 \!y:1997 \# sent to Zvi for J. Alg. 22 Mar 1995, sent revision 4 Mar 1996 \# accepted 7 Oct 1996; queue is 10 months long
Uses geometric optimization techniques to find, among n weighted values, the k to drop so as to maximize the weighted average of the remaining values. The feasibility test for the corresponding decision problem involves k-sets in a dual line arrangement.
(BibTeX -- Full paper -- CiteSeer -- ACM DL)
\- \!all \!geom:all \!mst \!geom:approx \!geom:cluster \!geom:qt \!a:solo \!c:no \!j:cgta \!p:k-point \!y:1995 \!y:1997
Various authors have looked at a variant of geometric clustering in which one must select k points that can be connected by a small spanning tree. The problem is NP-complete (for variable k); good approximations are known based on dynamic programming techniques but the time dependence on n is high. This paper describes a faster approximation algorithm based on dynamic programming in quadtrees, and a general technique based on that in "Iterated nearest neighbors" for reducing the dependence on n in any approximation algorithm.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!pure \!graph:all \!mst \!graph:path \!graph:match \!kbest \!a:solo \!c:no \!j:no \!y:1995
Shows how to find for any edge weighted graph G an equivalent graph EG such that the minimum spanning trees of G correspond one-for-one with the spanning trees of EG. \!pure The equivalent graph can be constructed in time O(m+n log n) given a single minimum spanning tree of G. As a consequence one can find fast algorithms for counting, listing, and randomly generating MSTs. \!pure Also discusses similar equivalent graph constructions for shortest paths, minimum cost flows, and bipartite matching.
\- \!all \!pure \!geom:all \!geom:tri \!a:solo \!c:scg \!j:cgta \!p:hexmesh \!y:1995 \!y:1996 \!y:1999 \# emailed to Goodrich for CGTA special on SCG 96 appl. papers, 27 Sep 1996 \# accepted subject to revn 30 Jan 1998; returned revn 28 Aug 1998 \# returned galleys 1 Dec 1998
Any simply connected polyhedron with an even number of quadrilateral sides can be partitioned into O(n) topological cubes, meeting face to face.
(BibTeX -- Citations -- SCG paper -- SCG talk slides -- CiteSeer -- ACM DL (CGTA))
\- \!all \!kbest \!graph:all \!graph:path \!a:solo \!c:no \!p:ancestors \!y:1995
This paper describes algorithms for finding pairs of vertex-disjoint paths in a DAG, either connecting two given nodes to a common ancestor, or connecting two given pairs of terminals. The main results were merged into the journal version of "Finding the k shortest paths".
(BibTeX)
\- \!all \!rec \!geom:all \!geom:zono \!a:solo \!c:no \!j:other \!p:zono \!y:1995 \!y:1996
I use Mathematica to construct zonotopes and display zonohedra. Many examples are shown, including one used for a lower bound in "The centroid of points with approximate weights". This paper is also available in HTML and Mathematica notebook formats.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!geom:all \!geom:nn \!pure \!a:paterson \!a:yao \!j:dcg \!p:nn \!y:1997
Paterson and Yao presented a paper at ICALP showing among other things that any connected nearest neighbor forest with diameter D has O(D9) vertices. This paper is the journal version; my contribution consists of improving that bound to O(D5), which is tight.
(BibTeX -- CiteSeer -- Citations)
\- \!all \!geom:all \!geom:tri \!a:barequet \!a:dickerson \!c:scg \!j:cgta \!p:3poly \!y:1996 \!y:1998 \# Gill submitted it to CGTA ca summer 1996 \# favorable referee reports received by Gil 30 Jul 1997 \# revision accepted 23 Oct 1997 \# Gill returned proofs 31 Mar 1998 \# scheduled for CGTA v10 n3 Jun 1998
It is NP-complete, given a simple polygon in 3-space, to find a triangulated simply-connected surface (without extra vertices) spanning that polygon. If extra vertices are allowed, or the surface may be curved, such a surface exists if and only if the polygon is unknotted; the complexity of testing knottedness remains open. Snoeyink has shown that exponentially many extra vertices may be required for a triangulated spanning disk.
(BibTeX -- SCG paper -- Full paper -- Citations -- CiteSeer -- ACM DL)
\- \!all \!param \!usesgeom \!graph:all \!mst \!a:fernandez-baca \!a:slutzki \!c:swat \!j:bit \!p:parammst \!y:1996
Given a graph with edge weights that are linear functions of a parameter, finds the sequence of minimum spanning trees produced as the parameter varies, in total time O(mn log n), by combining ideas from "Sparsification" and "Geometric lower bounds". Also solves various problems of optimizing the parameter value, including one closely related to that in "Choosing subsets with maximum weighted average".
(BibTeX -- Citations -- MIT hypertext bibliography -- ACM DL (SWAT) -- ACM DL (NJC))
\- \!all \!geom:all \!geom:cluster \!geom:circle \!a:solo \!c:soda \!j:no \!p:2c \!y:1996 \!y:1997
Improving on a recent breakthrough of Sharir, we use data structures from "Dynamic three-dimensional linear programming" to find two circular disks of minimum radius covering a set of points in the Euclidean plane, in randomized expected time O(n log2 n).
(