In this paper, an algorithm is introduced that computes an arbitrarily fine approximation of the smallest enclosing ball of a point set in any dimension. This operation is important in, for example, ...classification, clustering, and data mining. The algorithm is very simple to implement, gives reliable results, and gracefully handles large problem instances in low and high dimensions, as confirmed by both theoretical arguments and empirical evaluation. For example, using a CPU with eight cores, it takes less than two seconds to compute a 1.001‐approximation of the smallest enclosing ball of one million points uniformly distributed in a hypercube in dimension 200. Furthermore, the presented approach extends to a more general class of input objects, such as ball sets.
Let X = {f1, …, fn} be a set of scalar functions of the form fi : ℝ2 → ℝ which satisfy some natural properties. We describe a subdivision algorithm for computing a clustered ε‐isotopic approximation ...of the minimization diagram of X. By exploiting soft predicates and clustering of Voronoi vertices, our algorithm is the first that can handle arbitrary degeneracies in X, and allow scalar functions which are piecewise smooth, and not necessarily semi‐algebraic.
We apply these ideas to the computation of anisotropic Voronoi diagram of polygonal sets; this is a natural generalization of anisotropic Voronoi diagrams of point sites, which extends multiplicatively weighted Voronoi diagrams. We implement a prototype of our anisotropic algorithm and provide experimental results.
Comparing and computing distances between phylogenetic trees are important biological problems, especially for models where edge lengths play an important role. The geodesic distance measure between ...two phylogenetic trees with edge lengths is the length of the shortest path between them in the continuous tree space introduced by Billera, Holmes, and Vogtmann. This tree space provides a powerful tool for studying and comparing phylogenetic trees, both in exhibiting a natural distance measure and in providing a euclidean-like structure for solving optimization problems on trees. An important open problem is to find a polynomial time algorithm for finding geodesics in tree space. This paper gives such an algorithm, which starts with a simple initial path and moves through a series of successively shorter paths until the geodesic is attained.
We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges to make a given graph Eulerian, whereas our approach ...also allows for the removal of certain edges leading to a decreased cost. For the TSP on graphic metrics (graph-TSP), we show that the approach gives a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted either to half-integral solutions to the Held-Karp relaxation or to a class of graphs that contains subcubic and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4/3. The framework also allows for generalizations in a natural way and leads to analogous results for the s, t-path traveling salesman problem on graphic metrics where the start and end vertices are prespecified.
The theory of optimal size meshes gives a method for analyzing the output size (number of simplices) of a Delaunay refinement mesh in terms of the integral of a sizing function over the input domain. ...The input points define a maximal such sizing function called the feature size. This paper presents a way to bound the feature size integral in terms of an easy to compute property of a suitable ordering of the point set. The key idea is to consider the pacing of an ordered point set, a measure of the rate of change in the feature size as points are added one at a time. In previous work, Miller et al. showed that if an ordered point set has pacing ϕ, then the number of vertices in an optimal mesh will be O(ϕdn), where d is the input dimension. We give a new analysis of this integral showing that the output size is only θ(n+nlogϕ). The new analysis tightens bounds from several previous results and provides matching lower bounds. Moreover, it precisely characterizes inputs that yield outputs of size O(n).
Given two simplicial complexes in R
d
and start and end vertices in each complex, we show how to compute curves (in each complex) between these vertices, such that the weak Fréchet distance between ...these curves is minimized. As a polygonal curve is a complex, this generalizes the regular notion of weak Fréchet distance between curves. We also generalize the algorithm to handle an input of
k
simplicial complexes.
Using this new algorithm, we can solve a slew of new problems, from computing a mean curve for a given collection of curves to various motion planning problems. Additionally, we show that for the mean curve problem, when the
k
input curves are
c
-packed, one can (1+ε-approximate the mean curve in near-linear time, for fixed
k
and ε.
Additionally, we present an algorithm for computing the strong Fréchet distance between two curves, which is simpler than previous algorithms and avoids using parametric search.
Several design and animation techniques use a one‐dimensional proxy C (a spine curve in 3D) to control the deformation or behavior of a digital model of a 3D shape S. We propose a modification of ...these “skinning” techniques that ensures local volume preservation, which is important for the physical plausibility of digital simulations. In the proposed “fleshing” techniques, as input, we consider a smooth spine C0, a model S0 of a solid that lies “sufficiently close” to C0, and a deformed version C1 of C0 that is “not overly bent”. (We provide a precise characterization of these restrictions.) As output, we produce a bijective mapping M, that maps any point X of S onto a point M(X) of M(S). M satisfies two properties: (1) The closest projection of X on C0 and of M(X) on C1 have the same arc length parameter. (2) U and M(U) have the same volume, where U is any subset of S. We provide three different closed form expressions for radial, normal and binormal fleshing and discuss the details of their practical real‐time implementation.
We present a polynomial time approximation scheme for Euclidean TSP in fixed dimensions. For every fixed
c
> 1 and given any
n
nodes in ℛ
2
, a randomized version of the scheme finds a (1 + 1/
c
...)-approximation to the optimum traveling salesman tour in
O(n
(log
n
)
O(c)
)
time. When the nodes are in ℛ
d
, the running time increases to
O(n
(log
n
)
(O(√
c))
d-1
). For every fixed
c, d
the running time is
n
· poly(log
n
), that is
nearly linear
in
n
. The algorithmm can be derandomized, but this increases the running time by a factor
O(n
d
). The previous best approximation algorithm for the problem (due to Christofides) achieves a 3/2-aproximation in polynomial time.
We also give similar approximation schemes for some other NP-hard Euclidean problems: Minimum Steiner Tree,
k
-TSP, and
k
-MST. (The running times of the algorithm for
k
-TSP and
k
-MST involve an additional multiplicative factor
k
.) The previous best approximation algorithms for all these problems achieved a constant-factor approximation. We also give efficient approximation schemes for Euclidean Min-Cost Matching, a problem that can be solved exactly in polynomial time.
All our algorithms also work, with almost no modification, when distance is measured using any geometric norm (such as ℓ
p
for
p
≥ 1 or other Minkowski norms). They also have simple parallel (i.e., NC) implementations.
Within the rather chaotic atmosphere of scientific research the adoption of a software process, and the structured development of software, can be out of place. It is important to realize that the ...advancement of science is paramount, and so a balance must always be drawn between the cost and the benefit of the introduction of process into a research environment. This necessity presents a unique set of challenges to software development within the life sciences. These unique challenges are due to the cultural disconnect between life science research and software engineering. This paper outlines these challenges, and also discusses the software process used by the Institute for Systems Biology (ISB) to address them.
As part of the FLAME project, we have been dilligently developing new methodologies for analyzing, designing, and implementing linear algebra libraries. While we did not know it when we started, ...these techniques appear to solve many of the programmability problems that now face us with the advent of multicore and many-core architectures. These efforts have culminated in a new library, libflame, which strives to replace similar libraries that date back to the late 20th century. With this paper, we introduce the scientific computing community to this library.
PDF
