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".
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".
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.
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".
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.
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).
Any simply connected polyhedron with an even number of quadrilateral sides can be partitioned into O(n) topological cubes, meeting face to face.
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.
(SCG paper – Full paper)
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)
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".
We unfold any polyhedron with triangular faces into a planar layout in which the triangles are disjoint and are connected in a sequence from vertex to vertex
We consider the problem of finding a large color space that can be generated by all units in multi-projector tiled display systems. Viewing the problem geometrically as one of finding a large parallelepiped within the intersection of multiple parallelepipeds, and using colorimetric principles to define a volume-based objective function for comparing feasible solutions, we develop an algorithm for finding the optimal gamut in time O(n3), where n denotes the number of projectors in the system. We also discuss more efficient quasiconvex programming algorithms for alternative objective functions based on maximizing the quality of the color space extrema.
We describe an efficient streaming-model construction of epsilon-nets and epsilon-approximations, and use it to find deterministic streaming-model approximation algorithms for iceberg range queries and for various robust statistics problems.
We show that graphs with maximum degree four have geometric thickness at most two, by partitioning them into degree two subgraphs and applying simultaneous embedding techniques.
We describe a new algorithm, based on graph matching, for subdividing a triangle mesh (without boundary) so that it has a Hamiltonian cycle of triangles, and prove that this subdivision process increases the total number of triangles in the mesh by at most a factor of 3/2. We also prove lower bounds on the increase needed for meshes with and without boundary.
We show how to test the dilation of a star, embedded in a Euclidean space of bounded dimension, in time O(n log n), and how to find the star center that has the minimum dilation for a given set of leaf points in randomized expected time O(n log n). For two-dimensional points, we can find the minimum dilation center, constrained to be one of the input points, in time O(n 2α(n) log2n). The unconstrained center placement algorithm involves quasiconvex programming, and is used as a subroutine in the constrained center placement algorithm.
We describe a data structure consisting of a sequence of compressed quadtrees for successively sparser samples of an input point set, with connections between the same squares in successive members of the sequence. Using this structure, we can insert or delete points and answer approximate range queries and approximate nearest neighbor queries in O(log n) time per operation.
The problem is to place as few wedges as possible in the plane such that a desired polygon can be formed as some monotone Boolean combination of the wedges. The motivation is for wireless devices to prove that they are located within a target area by their ability to communicate with a subset of base stations (the wedges). We provide upper and lower bounds on the number of wedges needed for several classes of polygons.
We show that the triangulations of a finite point set form a flip graph that can be embedded isometrically into a hypercube, if and only if the point set has no empty convex pentagon. Point sets of this type include convex subsets of lattices, points on two lines, and several other infinite families. As a consequence, flip distance in such point sets can be computed efficiently.
A partition of a rectangle into smaller rectangles is "area-universal" if any vector of areas for the smaller rectangles can be realized by a combinatorially equivalent partition. These partitions may be applied, for instance, to cartograms, stylized maps in which the shapes of countries have been distorted so that their areas represent numeric data about the countries. We characterize area-universal layouts, describe algorithms for finding them, and discuss related problems. The algorithms for constructing area-universal layouts are based on the distributive lattice structure of the set of all layouts of a given dual graph.
Merged with "Orientation-constrained rectangular layouts" to form the journal version, "Area-universal and constrained rectangular layouts".
We investigate distance from a pair of sites defined as the sum of the distances to each site minus a parameter times the distance between the two sites. A given set of n sites defines n(n-1)/2 pairs and n(n-1)/2 distances in this way, from which we can determine a Voronoi diagram. As we show, for a wide range of parameters, the diagram has relatively few regions because the pairs that have nonempty Voronoi regions must be Delaunay edges.
We provide a graph-theoretic characterization of three classes of nonconvex polyhedra with axis-parallel sides, analogous to Steinitz's theorem characterizing the graphs of convex polyhedra.
The journal version has the slightly different title "Steinitz theorems for simple orthogonal polyhedra".
(Slides)
Suppose that P is the intersection of n halfspaces in D dimensions, but that the bounded faces of P are at most d-dimensional, for some d that is much smaller than D. Then in this case we show that the number of vertices of P is O(nd), independent of D. We also investigate related bounds on the number of bounded faces of all dimensions of P, and algorithms for efficiently listing the vertices and bounded faces of P.
We characterize the graphs of two-dimensional soap bubble clusters as being exactly the bridgeless 3-regular planar graphs. The proof uses the Möbius invariance of the properties characterizing these clusters together with our previous circle packing method for constructing Lombardi drawings of graphs.
For the journal version, see "A Möbius-invariant power diagram and its applications to soap bubbles and planar lombardi drawing.".
(Slides)
We give the first known near-linear algorithms for constructing Gomory–Hu trees of bounded-genus graphs, and we shave a log off the time for the same problem on planar graphs.
We study problems in which the input is a sequence of points in the plane and we wish to find, for each position in the sequence, the longest contiguous subsequence that begins at that position and has some geometric property. For many natural properties we can find all such maximal subsequences in linear or near-linear time.
(Slides)
We construct planar graphs whose straight drawings require a large number of lines (at least the cube root of the number of vertices) to cover all vertices. We also find series-parallel graphs and apex-trees that require a non-constant number of lines.
(Slides)
Given a polygon with holes, it is #P-complete to determine how many triangulations it has.
(UCLA seminar talk slides — SoCG slides)
Greedy spanners are graphs formed from sets of geometric points by considering the pairs of points in sorted order by distance and adding an edge whenever a pair cannot be connected by a short path through the previously-added edges. We show that for points in the Euclidean plane, these graphs have linearly many crossings, that the intersection graph of their edges has bounded degeneracy, and that they have separators of square-root size.
For any point set, the numbers of non-crossing paths, non-crossing Hamiltonian paths, non-crossing surrounding polygons, and non-crossing Hamiltonian cycles can be bounded above and below by functions of two simple parameters: the minimum number of points whose deletion leaves a collinear subset, and the number of points interior to the convex hull. Because their bounds have the same form, the numbers of the two types of paths are bounded by polynomials of each other, as are the numbers of the two types of polygons. We use these relations to list non-crossing Hamiltonian paths and polygonalizations in time polynomial in the number of outputs.
Conferences – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.