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)
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)
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)
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)
Includes results from "Speeding up dynamic programming", "Sequence comparison with mixed convex and concave costs", and "Sparse dynamic programming".
(BibTeX)
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)
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))
(BibTeX)
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))
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.
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))
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. One consequence is a parallel algorithm to list all subgraphs isomorphic to K3 or K4. More recently this paper has been cited for its applications to scheduling update operations in parallel finite element methods.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
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)
We later discovered that the same results were published in a SPAA paper by Greg Shannon.
(BibTeX)
I used genetic algorithms to search for small configurations of points bisected by lines in many combinatorially distinct ways.
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)
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)
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)
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)
Characterizes two-terminal series graphs in terms of a tree-like structure in their ear decompositions. Uses this characterization to construct parallel algorithms that recognize these graphs and construct their series-parallel decompositions.
(BibTeX -- Citations -- MIT hypertext bibliography -- CiteSeer -- ACM DL)
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))
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.
First half of the journal version of Sparse dynamic programming.
(Citations -- MIT hypertext bibliography)
Second half of the journal version of Sparse dynamic programming.
(Citations -- MIT hypertext bibliography)
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)
Surveys results on speeding up certain dynamic programs used for sequence comparison and RNA structure prediction.
(BibTeX -- Citations -- CiteSeer)
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)
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)
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)
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.
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.
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))
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)
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)
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)
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.
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)
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)
"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.
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)
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)
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))
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)
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.
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)
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.
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)
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)
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)
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)
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)
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)
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)
First half of journal version of Separator based sparsification for dynamic planar graph algorithms.
Second half of journal version of Separator based sparsification for dynamic planar graph algorithms.
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)
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)
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".
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)
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.
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)
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)
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)
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.
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 -- Graehl implementation -- Jiménez-Marzal implementations -- Shibuya implementation -- Martins implementation -- CiteSeer: TR '94, SJC '98 -- ACM DL)
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)
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))
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)
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)
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)
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)
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)
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.
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)
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)
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. 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. Also discusses similar equivalent graph constructions for shortest paths, minimum cost flows, and bipartite matching.
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))
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)
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)
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)
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)
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))
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).
(BibTeX -- SODA paper -- Citations -- DREI and SODA talk slides -- CiteSeer)
Any algorithm that maintains the connected components of a bitmap image must take Omega(log n / log log n) time per change to the image. The problem can be solved in O(log n) time per change using dynamic planar graph techniques. We discuss applications to computer Go and other games.
(BibTeX -- Citations -- MIT hypertext bibliography -- CiteSeer -- ACM DL)
Any bipartite Eulerian graph, any Eulerian graph with evenly many vertices, and any bipartite graph with evenly many vertices and edges, has an even number of spanning trees. More generally, a graph has evenly many spanning trees if and only if it has an Eulerian edge cut.
(BibTeX -- Citations -- CiteSeer)
Beta-skeletons are geometric graphs used among other purposes for empirical network analysis and minimum weight triangulation. A fractal construction shows that, for any beta>0, the beta-skeleton of a point set can have arbitrarily large dilation: Omega(nc), where c is a constant depending on beta and going to zero in the limit as beta goes to zero. In particular this applies to the Gabriel graph. We also show upper bounds on dilation of the same form.
(BibTeX -- Citations -- ACM DL)
Surveys results in geometric network design theory, including algorithms for constructing minimum spanning trees and low-dilation graphs.
(BibTeX -- Citations -- CiteSeer)
We study finite element mesh smoothing problems in which we move vertex locations to optimize the shapes of nearby triangles. Many such problems can be solved in linear time using generalized linear programming; we also give efficient algorithms for some non-LP-type mesh smoothing problems. One lemma may be of independent interest: the locus of points in Rd from which a d-1 dimensional convex set subtends a given solid angle is convex.
(BibTeX -- SODA paper -- Citations -- CiteSeer -- ACM DL)
It was known that planar graphs have the diameter-treewidth property: there is a function f(D) such that any planar graph with diameter D has treewidth at most f(D). (Actually, f(D)=O(D).) We characterize the other minor-closed families with this property: F has the diameter-treewidth property if and only if there is a graph G, formed by adding a vertex to a planar graph, that is not in F. Families with the diameter-treewidth property include bounded-genus graphs (for which again f(D)=O(D)) and K3,a-free graphs. As a consequence, various efficient planar subgraph isomorphism and approximation algorithms can be extended to these families. Some of these results were announced in the conference version of "subgraph isomorphism for planar graphs and related problems" but not included in the journal version.
(BibTeX -- Citations -- CiteSeer)
We show how to find shortest paths along the segments of an arrangement of n vertical and horizontal line segments in the plane, in time O(n3/2).
(BibTeX -- Citations -- CiteSeer -- ACM DL)
(BibTeX)
We consider the problem of "connect the dots": if we have an unknown smooth curve from which sample points have been selected, we would like to find a curve through the sample points that approximates the unknown curve. We show that if the local sample density is sufficiently high, a simple algorithm suffices: form the Delaunay triangulation of the sample points together with their Voronoi vertices, and keep only those Delaunay edges connecting original sample points.
(Tech. report version -- BibTeX -- Citations -- CiteSeer -- ACM DL)
This talk surveys some connections from computational geometry to parametric matroids: the results of my paper "Geometric lower bounds", new upper bounds from a paper by Tamal Dey, and a problem from constructive solid geometry with the potential to lead to stronger lower bounds.
We use circle-packing methods to generate quadrilateral meshes for polygonal domains, with guaranteed bounds both on the quality and the number of elements. We show that these methods can generate meshes of several types:
(BibTeX -- Citations -- CiteSeer)
This paper shows how to use my dynamic closest pair data structure from "Dynamic Euclidean minimum spanning trees" for some non-geometric problems including hierarchical clustering, greedy matching, and TSP heuristics. Experiments show variants of my data structures to be faster than previously used heuristics.
(Source code and experimental data -- BibTeX -- SODA paper -- Citations -- CiteSeer -- ACM DL -- JEA home page)
We use my dynamic closest pair data structure from "Dynamic Euclidean minimum spanning trees" to detect collisions among a collection of moving objects in sublinear time per collision. As one application, we can construct the "straight skeleton" of Aichholzer et al (and the mitered offset curves from which it is defined) in subquadratic time.
(Jeff's publications page and copy of the journal version -- BibTeX -- Citations -- CiteSeer)
We define a notion of geometric thickness, intermediate between the previously studied concepts of graph thickness and book thickness: a graph has geometric thickness T if its vertices can be embedded in the plane, and its edges partitioned into T subsets, so that each subset forms a planar straight line graph. We then give upper and lower bounds on the geometric thickness of complete graphs.
(Springer abstract -- BibTeX -- CiteSeer -- Citations -- ACM DL -- GDEA)
We show how to find shortest paths between two points on the lines of an arrangement of n lines with k distinct orientations, in time O(n + k2).
(BibTeX -- SODA paper -- Citations -- CiteSeer)
We apply techniques from "Quadrilateral meshing by circle packing" to a magic trick of Houdini: fold a piece of paper so that with one straight cut, you can form your favorite polygon.
(preprint at Erik's web site -- BibTeX -- CiteSeer)
We describe algorithms for maintaining the minimum spanning tree in a graph in which the edge weights are piecewise linear functions of time that may change unpredictably. We solve the problem in time O(n2/3 polylog n) per combinatorial change to the tree for general graphs, and in time O(n1/4 polylog n) per combinatorial change to the tree for planar graphs.
(BibTeX -- FOCS '98 talk slides -- Citations -- CiteSeer -- ACM DL)
We consider several variations of the problem of coloring the squares of a quadtree so that no two adjacent squares are colored alike. We give simple linear time algorithms for 3-coloring balanced quadtrees with edge adjacency, 4-coloring unbalanced quadtrees with edge adjacency, and 6-coloring balanced or unbalanced quadtrees with corner adjacency. The number of colors used by the first two algorithms is optimal; for the third algorithm, 5 colors may sometimes be needed.
We show how to maintain the width of a planar point set, subject to insertions or deletions (but not both) in time O(nc) per update for any c > 0. The idea is to apply our dynamic closest pair data structure to an appropriate measure of distance between pairs of convex hull features.
(BibTeX -- Citations -- SODA talk slides -- ACM DL)
We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least ceiling(n/(d+1)). as had been conjectured by Rousseeuw and Hubert. Dually, for any arrangement of n hyperplanes in d dimensions there exists a point that cannot escape to infinity without crossing at least ceiling(n/(d+1)) hyperplanes. We also apply our approach to related questions on the existence of partitions of the data into subsets such that a common plane has nonzero regression depth in each subset, and to the computational complexity of regression depth problems.
(BibTeX -- Citations -- CiteSeer)
We introduce a class of "inverse parametric optimization" problems, in which one is given both a parametric optimization problem and a desired optimal solution; the task is to determine parameter values that lead to the given solution. We use low-dimensional linear programming and geometric sampling techniques to solve such problems for minimum spanning trees, shortest paths, and other optimal subgraph problems, and discuss applications in multicast routing, vehicle path planning, resource allocation, and board game programming.
(BibTeX -- Citations -- ACM DL (FOCS) -- ACM DL (SJC))
We compute the expected numbers of short cycles of each length in certain classes of random graphs used for turbocodes, estimate the probability that there are no such short cycles involving a given vertex, and experimentally verify our estimates. The scarcity of short cycles may help explain the empirically observed accuracy of belief-propagation based error-correction algorithms. Note, the TR, conference, and journal versions of this paper have slightly different titles.
(BibTeX -- Citations: TR/ISIT -- CiteSeer)
We prove the existence of polyhedra in which all faces are convex, but which can not be cut along edges and folded flat.
Note variations in different versions: the CCCG one was only Bern, Demain, Eppstein, and Kuo, and the WCG one had the title "Ununfoldable polyhedra with triangular faces". The journal version uses the title "Ununfoldable polyhedra with convex faces" and the combined results from both conference versions.
(BibTeX -- Erik's publication page -- CiteSeer -- ACM DL)
We show that, for any n, there exists a mechanism formed by connecting polygons with hinges that can be folded into all possible n-ominos. Similar results hold as well for n-iamonds, n-hexes, and n-abolos.
(BibTeX -- Erik's CCCG publication page -- Erik's CGTA publication page -- Citations)
This is the report from the ACM Workshop on Computational Topology run by Marshall and myself in Miami Beach, June 1999. It details goals, current research, and recommendations in this emerging area of collaboration between computer science and mathematics.
(BibTeX -- Citations -- CiteSeer)
Any four mutually tangent spheres determine three coincident lines through opposite pairs of tangencies. As a consequence, we define two new triangle centers. These centers arose as part of a compass-and-straightedge construction of Soddy circles; also available are some Mathematica calculations of trilinear coordinates for the new triangle centers.
(BibTeX -- Citations -- CiteSeer)
We generalize regression depth to k-flats. The k=0 case gives the classical notion of center points. We prove that for any set of n points in Rd there always exists a k-flat with depth at least a constant fraction of n. As a consequence, we derive a linear-time (1+epsilon)-approximation algorithm for the deepest flat. The full version of this paper also includes results from "Computing the Depth of a Flat".
(BibTeX -- SCG paper -- Citations -- CiteSeer)
We describe software that searches for spaceships in Conway's Game of Life and related two-dimensional cellular automata. Our program searches through a state space related to the de Bruijn graph of the automaton, using a method that combines features of breadth first and iterative deepening search, and includes fast bit-parallel graph reachability and path enumeration algorithms for finding the successors of each state. Successful results include a new 2c/7 spaceship in Life, found by searching a space with 2^126 states.
(BibTeX -- MSRI talk on streaming video and talk slides -- Citations -- CiteSeer)
This talk surveys work on computational geometry algorithms that use dynamic graph data structures, and the different kinds of geometric graph arising in this work.
Journal paper combining 3-coloring algorithms from our FOCS '95 paper with improved bounds from our SODA '01 paper.
We describe by a regular expression the one-dimensional peg-solitaire positions reducible to a single peg, and provide a linear-time algorithm (based on finding shortest paths in an associated DAG) for reducing any such position to the minimum number of pegs. We then investigate impartial games in which players alternate peg solitaire moves in an attempt to be the one to move last.
(BibTeX -- Citations -- Cris' MSRI talk on streaming video -- Cris' publications page -- CiteSeer)
We show that, in John Conway's board game Phutball (or Philosopher's Football), it is NP-complete to determine whether the current player has a move that immediately wins the game. In contrast, the similar problems of determining whether there is an immediately winning move in checkers, or a move that kings a man, are both solvable in polynomial time.
(BibTeX -- Citations -- Erik's publications page -- CiteSeer)
We use random sampling to quickly estimate, for each vertex in a graph, the average distance to all other vertices.
(BibTeX -- SODA paper -- Citations -- CiteSeer)
Summarizes recent improvements to "3-Coloring in time O(1.3446n): a no-MIS algorithm". Merged with that paper for the journal version.
(SODA talk slides -- BibTeX -- SODA paper -- CiteSeer)
We compute the regression depth of a k-flat in a set of n d-dimensional points, in time O(nd-2), an order of magnitude faster than the best known algorithms for computing the depth of a point or of a hyperplane. The results from this conference paper have been merged into the full version of "Multivariate Regression Depth".
(SODA talk slides -- SODA paper -- BibTeX -- Citations -- CiteSeer)
Rule sets for internet routers and firewalls can be represented as sets of prioritized rectangles; the rule to use for a packet is the maximum priority rectangle containing its (source,destination) address pair. We develop efficient data structures for performing these queries, and find an O(n3/2) time algorithm for testing whether a rule set contains any ambiguities.