Constructing strongly convex hulls using exact or rounded arithmetic

One useful generalization of the convex hull of a setS ofn points is the -strongly convex -hull. It is defined to be a convex polygon with vertices taken fromS such that no point inS lies farther than outside and such that even if the vertices of are perturbed by as much as , remains convex. It was an open question as to whether an -strongly convexO()-hull existed for all positive . We give here anO(n logn) algorithm for constructing it (which thus proves its existence). This algorithm uses exact rational arithmetic. We also show how to construct an -strongly convexO( + )-hull inO(n logn) time using rounded arithmetic with rounding unit . This is the first rounded-arithmetic convex-hull algorithm which guarantees a convex output and which has error independent ofn.     

Classical and Quantum Complexity of the Sturm–Liouville Eigenvalue Problem

We study the approximation of the smallest eigenvalue of a Sturm–Liouville problem in the classical and quantum settings. We consider a univariate Sturm–Liouville eigenvalue problem with a nonnegative function q from the class C² ([0,1]) and study the minimal number n() of function evaluations or queries that are necessary to compute an -approximation of the smallest eigenvalue. We prove that n()=(^–1/2) in the (deterministic) worst case setting, and n()=(^–2/5) in the randomized setting. The quantum setting offers a polynomial speedup with bit queries and an exponential speedup with power queries. Bit queries are similar to the oracle calls used in Grovers algorithm appropriately extended to real valued functions. Power queries are used for a number of problems including phase estimation. They are obtained by considering the propagator of the discretized system at a number of different time moments. They allow us to use powers of the unitary matrix exp((1/2) iM), where M is an n× n matrix obtained from the standard discretization of the Sturm–Liouville differential operator. The quantum implementation of power queries by a number of elementary quantum gates that is polylog in n is an open issue. In particular, we show how to compute an -approximation with probability (3/4) using n()=(^–1/3) bit queries. For power queries, we use the phase estimation algorithm as a basic tool and present the algorithm that solves the problem using n()=(log ^–1) power queries, log ^2–1 quantum operations, and (3/2) log ^–1 quantum bits. We also prove that the minimal number of qubits needed for this problem (regardless of the kind of queries used) is at least roughly (1/2) log ^–1. The lower bound on the number of quantum queries is proven in Bessen (in preparation). We derive a formula that relates the Sturm–Liouville eigenvalue problem to a weighted integration problem. Many computational problems may be recast as this weighted integration problem, which allows us to solve them with a polylog number of power queries. Examples include Grovers search, the approximation of the Boolean mean, NP-complete problems, and many multivariate integration problems. In this paper we only provide the relationship formula. The implications are covered in a forthcoming paper (in preparation).PACS: 03.67.Lx, 02.60.-x.     

A sublinear algorithm for approximate keyword searching

Given a relatively short query stringW of lengthP, a long subject stringA of lengthN, and a thresholdD, theapproximate keyword search problem is to find all substrings ofA that align withW with not more than D insertions, deletions, and mismatches. In typical applications, such as searching a DNA sequence database, the size of the databaseA is much larger than that of the queryW, e.g.,N is on the order of millions or billions andP is a hundred to a thousand. In this paper we present an algorithm that given a precomputedindex of the databaseA, finds rare matches in time that issublinear inN, i.e.,N ^c for somec<1. The sequenceA must be overa. finite alphabet . More precisely, our algorithm requires 0(DN ^pow() logN) expected-time where =D/P is the maximum number of differences as a percentage of query length, and pow() is an increasing and concave function that is 0 when =0. Thus the algorithm is superior to current O(DN) algorithms when is small enough to guarantee that pow() < 1. As seen in the paper, this is true for a wide range of , e.g., . up to 33% for DNA sequences (¦¦=4) and 56% for proteins sequences (¦¦=20). In preliminary practical experiments, the approach gives a 50-to 500-fold improvement over previous algorithms for prolems of interest in molecular biology.This work was supported in part by the National Institutes of Health under Grant R01 LM04960-01 and the Aspen Center for Physics.     

Dynamic half-space range reporting and its applications

We consider the half-space range-reporting problem: Given a setS ofn points in ^d, preprocess it into a data structure, so that, given a query half-space , allk points ofS can be reported efficiently. We extend previously known static solutions to dynamic ones, supporting insertions and deletions of points ofS. For a given parameterm,n m n ^d/2 and an arbitrarily small positive constant , we achieveO(m ¹⁺) space and preprocessing time, O((n/m ^d/2 logn+k) query time, and O(m¹⁺n) amortized update time (d 3). We present, among others, the following applications: an O(n¹⁺)-time algorithm for computing convex layers in ³, and an output sensitive algorithm for computing a level in an arrangements of planes in ³, whose time complexity is O((b+n) n, whereb is the size of the level.Work by the first author has been supported by National Science Foundation Grant CCR-91-06514. A preliminary version of this paper appeared in Agarwalet al. [2], which also contains the results of [20] on dynamic bichromatic closest pair and minimum spanning trees.     

How to find Steiner minimal trees in euclideand-space

This paper has two purposes. The first is to present a new way to find a Steiner minimum tree (SMT) connectingN sites ind-space,d >- 2. We present (in Appendix 1) a computer code for this purpose. This is the only procedure known to the author for finding Steiner minimal trees ind-space ford > 2, and also the first one which fits naturally into the framework of backtracking and branch-and-bound. Finding SMTs of up toN = 12 general sites ind-space (for anyd) now appears feasible.We tabulate Steiner minimal trees for many point sets, including the vertices of most of the regular and Archimedeand-polytopes with <- 16 vertices. As a consequence of these tables, the Gilbert-Pollak conjecture is shown to be false in dimensions 3–9. (The conjecture remains open in other dimensions; it is probably false in all dimensionsd withd 3, but it is probably true whend = 2.)The second purpose is to present some new theoretical results regarding the asymptotic computational complexity of finding SMTs to precision .We show that in two-dimensions, Steiner minimum trees may be found exactly in exponential time O(C ^N ) on a real RAM. (All previous provable time bounds were superexponential.) If the tree is only wanted to precision , then there is an (N/)^O(N)-time algorithm, which is subexponential if 1/ grows only polynomially withN. Also, therectilinear Steiner minimal tree ofN points in the plane may be found inN ^O(N) time.J. S. Provan devised an O(N ⁶/⁴)-time algorithm for finding the SMT of a convexN-point set in the plane. (Also the rectilinear SMT of such a set may be found in O(N ⁶) time.) One therefore suspects that this problem may be solved exactly in polynomial time. We show that this suspicion is in fact true—if a certain conjecture about the size of Steiner sensitivity diagrams is correct.All of these algorithms are for a real RAM model of computation allowing infinite precision arithmetic. They make no probabilistic or other assumptions about the input; the time bounds are valid in the worst case; and all our algorithms may be implemented with a polynomial amount of space. Only algorithms yielding theexact optimum SMT, or trees with lengths (1 + ) × optimum, where is arbitrarily small, are considered here.     

Constructing strongly convex approximate hulls with inaccurate primitives

The first half of this paper introducesEpsilon Geometry, a framework for the development of robust geometric algorithms using inaccurate primitives. Epsilon Geometry is based on a very general model of imprecise computations, which includes floating-point and rounded-integer arithmetic as special cases. The second half of the paper introduces the notion of a (–)-convex polygon, a polygon that remains convex even if its vertices are all arbitrarily displaced by a distance of of less, and proves some interesting properties of such polygons. In particular, we prove that for every point set there exists a (–)-convex polygonH such that every point is at most 4 away fromH. Using the tools of Epsilon Geometry, we develop robust algorithms for testing whether a polygon is (–)-convex, for testing whether a point is inside a (–)-convex polygon, and for computing a (–)-convex approximate hull for a set of points.     

On control of two-scale stochastic systems with linear dynamics in the fast variables

We consider a problem of optimal control for a stochastic two-scale system that depends on a small positive parameter and where the stochastic differential equations, describing the evolution of the fast variables, degenerate to algebraic equations in the limit when=0. The model is nonlinear, but with the fast components entering linearly. Our main result is to show that, when tends to zero, the optimal value of the cost functional, that also includes the fast variables in the terminal pay-off, converges to the optimal value of a suitable reduced stochastic control problem. As a consequence we also have that a nearly optimal control for the limit problem can be modified to become nearly optimal also for the prelimit problems when. is sufficiently small.The work by Yuri M. Kabanov was performed during a stay in Padova supported by GNAFA/CNR.     

Existence and Computation of Low Kronecker-Rank Approximations for Large Linear Systems of Tensor Product Structure

In this paper we construct an approximation to the solution x of a linear system of equations Ax=b of tensor product structure as it typically arises for finite element and finite difference discretisations of partial differential operators on tensor grids. For a right-hand side b of tensor product structure we can prove that the solution x can be approximated by a sum of (log()²) tensor product vectors where is the relative approximation error. Numerical examples for systems of size 1024²⁵⁶ indicate that this method is suitable for high-dimensional problems.     

ɛ-productions in context-free grammars

Summary The effect of -productions on the space complexity of various context-free language problems is investigated. It is shown that the removal of -productions from a context-free grammar can probably not be achieved with small storage space. This explains the apparent discrepancy between two different results in the literature on the membership problem. By way of contrast, it is shown that the space complexity of the emptiness and the finiteness problems are independent of the presence of -productions.     

Provably good approximation algorithms for optimal kinodynamic planning: Robots with decoupled dynamics bounds

We consider the following problem: given a robot system, find a minimal-time trajectory that goes from a start state to a goal state while avoiding obstacles by a speed-dependent safety margin and respecting dynamics bounds. In [1] we developed a provably good approximation algorithm for the minimum-time trajectory problem for a robot system with decoupled dynamics bounds (e.g., a point robot in ³). This algorithm differs from previous work in three ways. It is possible (1) to bound the goodness of the approximation by an error term; (2) to bound the computational complexity of our algorithm polynomially; and (3) to express the complexity as a polynomial function of the error term. Hence, given the geometric obstacles, dynamics bounds, and the error term, the algorithm returns a solution that is-close to optimal and requires only a polynomial (in (1/)) amount of time.We extend the results of [1] in two ways. First, we modify it to halve the exponent in the polynomial bounds from 6d to 3d, so that the new algorithm isO(c ^d N 1/)^3d ), whereN is the geometric complexity of the obstacles andc is a robot-dependent constant. Second, the new algorithm finds a trajectory that matches the optimal in time with an factor sacrificed in the obstacle-avoidance safety margin. Similar results hold for polyhedral Cartesian manipulators in polyhedral environments.The new results indicate that an implementation of the algorithm could be reasonable, and a preliminary implementation has been done for the planar case.This paper describes research done at the Computer Science Robotics Laboratory at Cornell University. Support for our robotics research there is provided in part by the National Science Foundation under Grant Nos. IRI-8802390 and IRI-9000532, by a Presidential Young Investigator award, and in part by the Mathematical Sciences Institute, Intel Corporation, and AT&T Bell Laboratories.     

Efficient ray shooting and hidden surface removal

In this paper we study the ray-shooting problem for three special classes of polyhedral objects in space: axis-parallel polyhedra, curtains (unbounded polygons with three edges, two of which are parallel to thez-axis and extend downward to minus infinity), and fat horizontal triangles (triangles parallel to thexy-plane whose angles are greater than some given constant). For all three problems structures are presented usingO(n ²⁺) preprocessing, for any fixed > 0, withO(logn) query time. We also study the general ray-shooting problem in an arbitrary set of triangles. Here we present a structure that usesOn ⁴⁺) preprocessing and has a query time ofO(logn).We use the ray-shooting structure for curtains to obtain an algorithm for computing the view of a set of nonintersecting prolyhedra. For any > 0, we can obtain an algorithm with running time , wheren is the total number of vertices of the polyhedra andk is the size of the output. This is the first output-sensitive algorithm for this problem that does not need a depth order on the faces of the polyhedra.This research was supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). The first and third authors were also supported by the Dutch Organization for Scientific Research (N.W.O.).     

Axiomatising finite delay operators

Summary In a simple language for finite automata based on SCCS we introduce three different delay operators , , . The operators , are two different versions of an unbounded but finite delay operator. It is argued that the usual notion of bisimulation is inadequate and two generalisations are proposed. In both cases we give a complete axiomatisation for finite terms of the language and prove that certain forms of induction are sound. In one case we give a complete axiomatisation.     

The network complexity and the Turing machine complexity of finite functions

Summary Let L(f) be the network complexity of a Boolean function L(f). For any n-ary Boolean function L(f) let . Hereby p ranges over all relative Turing programs and ranges over all oracles such that given the oracle , the restriction of p to inputs of length n is a program for L(f). p is the number of instructions of p. T _p (n) is the time bound and S _p of the program p relative to the oracle on inputs of length n. Our main results are (1) L(f) O(TC(L(f))), (2) TC(f) O(L(f) ^{2 2+}) for every O.The results of this paper have been reported in a main lecture at the 1975 annual meeting of GAMM, April 2–5, Göttingen     

An improved parallel algorithm for integer GCD

We present a simple parallel algorithm for computing the greatest common divisor (gcd) of twon-bit integers in the Common version of the CRCW model of computation. The run-time of the algorithm in terms of bit operations isO(n/logn), usingn ¹⁺ processors, where is any positive constant. This improves on the algorithm of Kannan, Miller, and Rudolph, the only sublinear algorithm known previously, both in run time and in number of processors; they requireO(n log logn/logn),n ² log² n, respectively, in the same CRCW model.We give an alternative implementation of our algorithm in the CREW model. Its run-time isO(n log logn/logn), usingn ¹⁺ processors. Both implementations can be modified to yield the extended gcd, within the same complexity bounds.Supported in part by an IBM Graduate Fellowship and a Bantrell Postdoctoral Fellowship.Supported in part by a Weizmann Postdoctoral Fellowship.4 All logarithms are to base 2.     

On problem transformability in VLSI

The two basic performance parameters that capture the complexity of any VLSI chip are the area of the chip,A, and the computation time,T. A systematic approach for establishing lower bounds onA is presented. This approach relatesA to the bisection flow, . A theory of problem transformation based on , which captures bothAT ² andA complexity, is developed. A fundamental problem, namely, element uniqueness, is chosen as a computational prototype. It is shown under general input/output protocol assumptions that any chip that decides ifn elements (each with (1+)lognbits) are unique must have =(nlogn), and thus, AT²=(n ²log² n), andA= (nlogn). A theory of VLSI transformability reveals the inherentAT ² andA complexity of a large class of related problems.This work was supported in part by the Semiconductor Research Corporation under contract RSCH 84-06-049-6.     

Parallel construction of a suffix tree with applications

Many string manipulations can be performed efficiently on suffix trees. In this paper a CRCW parallel RAM algorithm is presented that constructs the suffix tree associated with a string ofn symbols inO(logn) time withn processors. The algorithm requires (n ²) space. However, the space needed can be reduced toO(n ¹⁺) for any 0< 1, with a corresponding slow-down proportional to 1/. Efficient parallel procedures are also given for some string problems that can be solved with suffix trees.The results of this paper have been achieved independently and simultaneously in [AI-86] and [LSV-86]. The research of U. Vishkin was supported by NSF Grant NSF-CCR-8615337, ONR Grant N00014-85-K-0046, and Foundation for Research in Electronics, Computers, and Communication, administered by the Israeli Academy of Sciences and Humanities. The research of A. Apostolico was carried out in part while visiting at the Istituto di Analisi dei Sistemi e Informatica, Rome, with support from the Italian National Research Council. The research of G. M. Landau, B. Schieber, and U. Vishkin was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under Contract DE-AC02-76ER03077.     

On characterizations of recursively enumerable languages

Summary Geffert has shown that earch recursively enumerable languageL over can be expressed in the formL{h(x) ^–1 g(x)x in ⁺} ^* where is an alphabet andg, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert's result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations ofL. For instance,L =(L ₀) ^* whereL ₀ is a minimal linear language and is the Dyck reductiona, A.     

The renormalization group,the ɛ-expansion and derivation of turbulence models

We reformulate the renormalization group (RNG) and the-expansion for derivation of turbulence models. The procedure is developed for the Navier-Stokes equations and the transport equations for the kinetic energyK and energy dissipation rate . The derivation draws on the works of Yakhot and Orszag (1986) and Smith and Reynolds (1992), and all results are found at low order in the underlying perturbation expansion in powers of. The sum of the source terms in the -equation is known to beO(1) due to the balance at leading order ofO(R _T ^1/2 ) terms. Smith and Reynolds (1992) showed the cancellation of some of theO(R _T ^1/2 ) terms generated by the RNG procedure. Here we show that including the random-force contribution to -production results in the cancellation ofall theO(R _T ^1/2 ) terms. We find that two of theO(1) terms in the RNG equation for the mean dissipation rate have the same form as those in the widely used model-equation. The values of the coefficients of the familiar terms are close to those used in practice. An extra production term is predicted which is small for slow distortions, but important for rapid distortions. Hence, it may be a term that should be added to the model equation. We believe that the present derivation places the model equation on a more solid theoretical basis.     

L1 shortest paths among polygonal obstacles in the plane

We present an algorithm for computingL ₁ shortest paths among polygonal obstacles in the plane. Our algorithm employs the continuous Dijkstra technique of propagating a wavefront and runs in timeO(E logn) and spaceO(E), wheren is the number of vertices of the obstacles andE is the number of events. By using bounds on the density of certain sparse binary matrices, we show thatE =O(n logn), implying that our algorithm is nearly optimal. We conjecture thatE =O(n), which would imply our algorithm to be optimal. Previous bounds for our problem were quadratic in time and space.Our algorithm generalizes to the case of fixed orientation metrics, yielding anO(n^–1/2 log² n) time andO(n^–1/2) space approximation algorithm for finding Euclidean shortest paths among obstacles. The algorithm further generalizes to the case of many sources, allowing us to compute anL ₁ Voronoi diagram for source points that lie among a collection of polygonal obstacles.Partially supported by a grant from Hughes Research Laboratories, Malibu, California and by NSF Grant ECSE-8857642. Much of this work was done while the author was a Ph.D. student at Stanford University, under the support of a Howard Hughes Doctoral Fellowship, and an employee of Hughes Research Laboratories.     

Complexity classes and theories of finite models

LetL ^* be accepted in timef(n) by a nondeterministic Turing machine. Then there is a monadic existential second-order sentence in the language of + such that for everyx^*,xL if and only if a certain structureU _x ^f of cardinalityf(|x|) satisfies . It follows that ifL is accepted in nondeterministic timen ^d, d a natural number, then there is a sentence whose relational symbols ared-ary or less, whose finite spectrum isL. This research was partially supported by NSF Grants MCS78-01832 and MCS-8002695.