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.     

Optimal multilayer channel routing with overlap

This paper presents algorithms for multiterminal net channel routing where multiple interconnect layers are available. Major improvements are possible if wires are able to overlap, and our generalized main algorithm allows overlap, but only on everyKth (K 2) layer. Our algorithm will, for a problem with densityd onL layers,L K + 3,provably use at most three tracks more than optimal: (d + 1)/L/K + 2 tracks, compared with the lower bound of d/L/K. Our algorithm is simple, has few vias, tends to minimize wire length, and could be used if different layers have different grid sizes. Finally, we extend our algorithm in order to obtain improved results for adjacent (K = 1) overlap: (d + 2)/2L/3 + 5 forL 7.This work was supported by the Semiconductor Research Corporation under Contract 83-01-035, by a grant from the General Electric Corporation, and by a grant at the University of the Saarland.     

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.     

On Bounding Solutions of Underdetermined Systems

Sufficient conditions for the existence and uniqueness of a solution x* D (R ⁿ ) of Y(x) = 0 where : R ⁿ R ^m (m n) with C ²(D) where D R ⁿ is an open convex set and Y = (x)⁺ are given, and are compared with similar results due to Zhang, Li and Shen (Reliable Computing 5(1) (1999)). An algorithm for bounding zeros of f (·) is described, and numerical results for several examples are given.     

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.     

A semidynamic construction of higher-order voronoi diagrams and its randomized analysis

Thek-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite set ofn points in any dimension. In this paper we prove that a randomized construction of thek-Delaunay tree, and thus of all the orderk Voronoi diagrams, can be done inO(n logn+k ³n) expected time and O(k²n) expected storage in the plane, which is asymptotically optimal for fixedk. Our algorithm extends tod-dimensional space with expected time complexityO(k ^(d+1)/2+1 n ^(d+1)/2) and space complexityO(k ^(d+1)/2 n ^(d+1)/2). The algorithm is simple and experimental results are given.This work has been supported in part by the ESPRIT Basic Research Action No. 3075 (ALCOM).     

The input/output complexity of transitive closure

Suppose a directed graph has its arcs stored in secondary memory, and we wish to compute its transitive closure, also storing the result in secondary memory. We assume that an amount of main memory capable of holdings values is available, and thats lies betweenn, the number of nodes of the graph, ande, the number of arcs. The cost measure we use for algorithms is theI/O complexity of Kung and Hong, where we count 1 every time a value is moved into main memory from secondary memory, or vice versa.In the dense case, wheree is close ton ², we show that I/O equal toO(n ³/s) is sufficient to compute the transitive closure of ann-node graph, using main memory of sizes. Moreover, it is necessary for any algorithm that is standard, in a sense to be defined precisely in the paper. Roughly, standard means that paths are constructed only by concatenating arcs and previously discovered paths. For the sparse case, we show that I/O equal toO(n ²e/s) is sufficient, although the algorithm we propose meets our definition of standard only if the underlying graph is acyclic. We also show that(n ²e/s) is necessary for any standard algorithm in the sparse case. That settles the I/O complexity of the sparse/acyclic case, for standard algorithms. It is unknown whether this complexity can be achieved in the sparse, cyclic case, by a standard algorithm, and it is unknown whether the bound can be beaten by nonstandard algorithms.We then consider a special kind of standard algorithm, in which paths are constructed only by concatenating arcs and old paths, never by concatenating two old paths. This restriction seems essential if we are to take advantage of sparseness. Unfortunately, we show that almost another factor ofn I/O is necessary. That is, there is an algorithm in this class using I/OO(n ³e/s) for arbitrary sparse graphs, including cyclic ones. Moreover, every algorithm in the restricted class must use(n ³e/s/log³ n) I/O, on some cyclic graphs.The work of this author was partially supported by NSF grant IRI-87-22886, IBM contract 476816, Air Force grant AFOSR-88-0266 and a Guggenheim fellowship.     

Parallel complexity of logical query programs

We consider the parallel time complexity of logic programs without function symbols, called logical query programs, or Datalog programs. We give a PRAM algorithm for computing the minimum model of a logical query program, and show that for programs with the polynomial fringe property, this algorithm runs in time that is logarithmic in the input size, assuming that concurrent writes are allowed if they are consistent. As a result, the linear and piecewise linear classes of logic programs are inN C. Then we examine several nonlinear classes in which the program has a single recursive rule that is an elementary chain. We show that certain nonlinear programs are related to GSM mappings of a balanced parentheses language, and that this relationship implies the polynomial fringe property; hence such programs are inN C Finally, we describe an approach for demonstrating that certain logical query programs are log space complete forP, and apply it to both elementary single rule programs and nonelementary programs.Supported by NSF Grant IST-84-12791, a grant of IBM Corporation, and ONR contract N00014-85-C-0731.     

Mesh Selection for a Nearly Singular Boundary Value Problem

In this paper, we investigate the numerical solution of a model equation u _xx = exp(– ) (and several slightly more general problems) when 1 using the standard central difference scheme on nonuniform grids. In particular, we are interested in the error behaviour in two limiting cases: (i) the total mesh point number N is fixed when the regularization parameter 0, and (ii) is fixed when N. Using a formal analysis, we show that a generalized version of a special piecewise uniform mesh 12 and an adaptive grid based on the equidistribution principle share some common features. And the optimal meshes give rates of convergence bounded by |log()| as 0 and N is given, which are shown to be sharp by numerical tests.     

The existence of solutions,stability, and linearization of volterra systems

LetB be a Banach space ofR _n valued continuous functions on [0, ) withfB. Consider the nonlinear Volterra integral equation (^*)x(t)+ _o ^t K(t,s,x(s))ds. We use the implicit function theorem to give sufficient conditions onB andK (t,s,x) for the existence of a unique solutionxB to (^*) for eachf B with f ^B sufficiently small. Moreover, there is a constantM>0 independent off with Mf^B.Part of this work was done while the author was visiting at Wright State University.     

A faster divide-and-conquer algorithm for constructing delaunay triangulations

An easily implemented modification to the divide-and-conquer algorithm for computing the Delaunay triangulation ofn sites in the plane is presented. The change reduces its (n logn) expected running time toO(n log logn) for a large class of distributions that includes the uniform distribution in the unit square. Experimental evidence presented demonstrates that the modified algorithm performs very well forn2¹⁶, the range of the experiments. It is conjectured that the average number of edges it creates—a good measure of its efficiency—is no more than twice optimal forn less than seven trillion. The improvement is shown to extend to the computation of the Delaunay triangulation in theL _p metric for 1<p.This research was supported by National Science Foundation Grants DCR-8352081 and DCR-8416190.     

Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity

We investigate three-dimensional visibility problems for scenes that consist ofn non-intersecting spheres. The viewing point moves on a flightpath that is part of a circle at infinity given by a planeP and a range of angles {(t)¦t[01]} [02]. At timet, the lines of sight are parallel to the ray inP, which starts in the origin ofP and represents the angle(t) (orthographic views of the scene). We give an algorithm that computes the visibility graph at the start of the flight, all time parameters at which the topology of the scene changes, and the corresponding topology changes. The algorithm has running time0(n + k + p) logn), wheren is the number of spheres in the scene;p is the number of transparent topology changes (the number of different scene topologies visible along the flight path, assuming that all spheres are transparent); andk denotes the number of vertices (conflicts) which are in the (transparent) visibility graph at the start and do not disappear during the flight.The second author was supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM).     

Using geometry to solve the transportation problem in the plane

LetU andV be two sets of points in the plane, where ¦U¦=k,¦V¦=, andn=k+. These two sets of points induce a directed complete bipartite graph in which the points represent nodes and an edge is directed from each node inU to each node in K Each edge is given a cost equal to the distance between the corresponding nodes measured by some metricd on the plane. We consider thetransportation problem on such a graph. We present an 0(n^2,5 logn logN) algorithm, whereN is the magnitude of the largest supply or demand. The algorithm uses some fundamental results of computational geometry and scaling of supplies and demands. The algorithm is valid for the ₁ metric, the ₂ metric, and the metric. The running time for the ₁ and metrics can be improved to 0(n²(logn)³ logN).D. S. Atkinson was supported by the National Science Foundation under Grant CCR90-57481PYI. P. M. Vaidya was supported by the National Science Foundation under Grants CCR-9057481 and CCR-9007195.     

Enumeration of Optimal Ternary Constant-Composition Codes

The problem of classification of optimal ternary constant-composition codes is considered. Using a combinatorial-computer method, the number of inequivalent codes is determined for 3 d n 10.     

MAAN: A Multi-Attribute Addressable Network for Grid Information Services

Recent structured Peer-to-Peer (P2P) systems such as Distributed Hash Tables (DHTs) offer scalable key-based lookup for distributed resources. However, they cannot be simply applied to grid information services because grid resources need to be registered and searched using multiple attributes. This paper proposes a Multi-Attribute Addressable Network (MAAN) that extends Chord to support multi-attribute and range queries. MAAN addresses range queries by mapping attribute values to the Chord identifier space via uniform locality preserving hashing. It uses an iterative or single attribute dominated query routing algorithm to resolve multi-attribute based queries. Each node in MAAN only has O(logN) neighbors for N nodes. The number of routing hops to resolve a multi-attribute range query is O(logN+N×s_min), where s_min is the minimum range selectivity on all attributes. When s_min=, it is logarithmic to the number of nodes, which is scalable to a large number of nodes and attributes. We also measured the performance of our MAAN implementation and the experimental results are consistent with our theoretical analysis.     

Tight bounds for oblivious routing in the hypercube

We prove that in anyN-node communication network with maximum degreed, any deterministic oblivious algorithm for routing an arbitrary permutation requires (N/d) parallel communication steps in the worst case. This is an improvement upon the (N/d ^3/2) bound obtained by Borodin and Hopcroft. For theN-node hypercube, in particular, we show a matching upper bound by exhibiting a deterministic oblivious algorithm that routes any permutation in (N/logN) steps. The best previously known upper bound was (N). Our algorithm may be practical for smallN (up to about 2¹⁴ nodes).C. Kaklamanis was supported in part by NSF Grant NSF-CCR-87-04513. T. Tsantilas was supported in part by NSF Grants NSF-DCR-86-00379 and NSF-CCR-89-02500.     

Randomized vs. deterministic decision tree complexity for read-once Boolean functions

We consider the deterministic and the randomized decision tree complexities for Boolean functions, denotedDC(f) andRC(f), respectively. A major open problem is how smallRC(f) can be with respect toDC(f). It is well known thatRC(f)DC(f) ^0.5 for every Boolean functionf (called 0.5-exponent). On the other hand, some Boolean functionf is known to haveRC(f) = (DC(f))^0.753...) (or 0.753...-exponent). It is not known whether there is a Boolean function with exponent smaller than 0.753... Likewise, no lower bound for arbitrary Boolean functions with exponent greater than 0.5 is known.Our result is a 0.51 lower bound on the exponent for everyread-once function. Read-once means that each input variable appears exactly once in the Boolean formula representing the function. To obtain this result we generalize an existing lower bound technique and combine it with restriction arguments. This result provides a lower bound ofn ^0.51 on the number of positions that have to be evaluated by any randomized - pruning algorithm computing the value of any two-person zero-sum game tree withn final positions.     

From Conditional Events to Conditional Measures: A New Axiomatic Approach

Our starting point is a definition of conditional event EH which differs from many seemingly similar ones adopted in the relevant literature since 1935, starting with de Finetti. In fact, if we do not assign the same third value u (undetermined) to all conditional events, but make it depend on EH, it turns out that this function t(EH) can be taken as a general conditional uncertainty measure, and we get (through a suitable – in a sense, compulsory – choice of the relevant operations among conditional events) the natural axioms for many different (besides probability) conditional measures.     

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.     

Type inference with non-structural subtyping

We present an O(n³) time type inference algorithm for a type system with a largest type, a smallest type , and the usual ordering between function types. The algorithm infers type annotations of least shape, and it works equally well for recursive types. For the problem of typability, our algorithm is simpler than the one of Kozen, Palsberg, and Schwartzbach for type inferencewithout . This may be surprising, especially because the system with is strictly more powerful.