Finding a closest visible vertex pair between two polygons

Given nonintersecting simple polygonsP andQ, two verticespP andq Q are said to be visible if does not properly intersectP orQ. We present a parallel algorithm for finding a closest pair among all visible pairs (p,q),pP andqQ. The algorithm runs in time O(logn) using O(n) processors on a CREW PRAM, wheren=¦P¦+¦Q¦. This algorithm can be implemented serially in (n) time, which gives a new optimal sequential solution for this problem.This paper appeared in preliminary form as [1]. This work was supported in part by an AT&T BellLaboratories Graduate Fellowship, the Joint Services Electronics Program (U.S. Army, U.S. Navy, U.S. Air Force) under Contract N00014-90-J-1270, and NSF Grant CCR-89-22008. This work was done while the author was with the Department of Computer Science at the University of Illinois at Urbana-Champaign.     

On computing Boolean connectives of characteristic functions

This paper is a study of the existence of polynomial time Boolean connective functions for languages. A languageL has an AND function if there is a polynomial timef such thatf(x,y) L x L andy L. L has an OR function if there is a polynomial timeg such thatg(x,y) xL oryL. While all NP complete sets have these functions, Graph Isomorphism, which is probably not complete, is also shown to have both AND and OR functions. The results in this paper characterize the complete sets for the classes D^p and p^SAT[O(logn)] in terms of AND and OR and relate these functions to the structure of the Boolean hierarchy and the query hierarchies. Also, this paper shows that the complete sets for the levels of the Boolean hierarchy above the second level cannot have AND or OR unless the polynomial hierarchy collapses. Finally, most of the structural properties of the Boolean hierarchy and query hierarchies are shown to depend only on the existence of AND and OR functions for the NP complete sets.The first author was supported in part by NSF Research Grants DCR-8520597 and CCR-88-23053, and by an IBM Graduate Fellowship.     

Connected component and simple polygon intersection searching

Efficient data structures are given for the following two query problems: (i) preprocess a setP of simple polygons with a total ofn edges, so that all polygons ofP intersected by a query segment can be reported efficiently, and (ii) preprocess a setS ofn segments, so that the connected components of the arrangement ofS intersected by a query segment can be reported quickly. In these problems we do not want to return the polygons or connected components explicitly (i.e., we do not wish to report the segments defining the polygon, or the segments lying in the connected components). Instead, we assume that the polygons (or connected components) are labeled and we just want to report their labels. We present data structures of sizeO(n ¹⁺) that can answer a query in timeO(n ¹⁺+k), wherek is the output size. If the edges ofP (or the segments inS) are orthogonal, the query time can be improved toO(logn+k) usingO(n logn) space. We also present data structures that can maintain the connected components as we insert new segments. For arbitrary segments the amortized update and query time areO(n ^1/2+) andO(n ^1/2++k), respectively, and the space used by the data structure isO(n ¹⁺. If we allowO(n ^4/3+ space, the amortized update and query time can be improved toO(n ^1/3+ andO(n ^1/3++k, respectively. For orthogonal segments the amortized update and query time areO(log² n) andO(log² n+klogn), and the space used by the data structure isO (n logn). Some other related results are also mentioned.Part of this work was done while the second author was visiting the first author on a grant by the Dutch Organization for Scientific Research (N.W.O.). The research of the second author was also supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). The research of the first author was supported by National Science Foundation Grant CCR-91-06514.     

Numerical stability of a convex hull algorithm for simple polygons

A numerically stable and optimalO(n)-time implementation of an algorithm for finding the convex hull of a simple polygon is presented. Stability is understood in the sense of a backward error analysis. A concept of the condition number of simple polygons and its impact on the performance of the algorithm is discussed. It is shown that if the condition number does not exceed (1+O())/(3), then, in floating-point arithmetic with the unit roundoff, the algorithm produces the vertices of a convex hull for slightly perturbed input points. The relative perturbation does not exceed 3(1+O()).J. W. Jaromczyk was partially supported by a grant from the Center for Robotics and Manufacturing Systems at the University of Kentucky and G. W. Wasilkowski was partially supported by the National Science Foundation under Grants CCR-89-05371 and CCR-91-14042.     

Instability Conditions for Nonlinear Nonautonomous Dynamic Systems. II. Sufficient Conditions of Instability

In Part I, using a special class of scalar functions V(x, t, ) dependent on a parameter , we have derived new necessary and sufficient conditions for the instability (in some domain) of the equilibrium states of nonlinear nonautonomous dynamic systems of arbitrary order. In Part II, we derive new sufficient conditions for the instability of a class of unstable systems in terms of functions admitting a simple geometric interpretation.     

A Hyperbase for Binary Lattice Hyperidentities

We define an identity to be hypersatisfied by a variety V if, whenever the operation symbols of V, are replaced by arbitrary terms (of appropriate arity) in the operations of V, the resulting identity is satisfied by V in the usual sense. Whenever the identity is hypersatisfied by a variety V, we shall say that is a V hyperidentity. For example, the identity x + x y = x (x + y) is hypersatisfied by the variety L of all lattices. A proof of this consists of a case-by-case examination of { + , } {x, y, x y, x y}, the set of all binary lattice terms. In an earlier work, we exhibited a hyperbase ^L for the set of all binary lattice (or, equivalently, quasilattice) hyperidentities of type 2, 2. In this paper we provide a greatly refined hyperbase _L . The proof that _L is a hyperbase was obtained by using the automated reasoning program Otter 3.0.4.     

On parallel integer sorting

We present an optimal algorithm for sortingn integers in the range [1,n ^c ] (for any constantc) for the EREW PRAM model where the word length isn , for any >0. Using this algorithm, the best known upper bound for integer sorting on the (O(logn) word length) EREW PRAM model is improved. In addition, a novel parallel range reduction algorithm which results in a near optimal randomized integer sorting algorthm is presented. For the case when the keys are uniformly distributed integers in an arbitrary range, we give an algorithm whose expected running time is optimal.Supported by NSF-DCR-85-03251 and ONR contract N00014-87-K-0310     

Clock synchronization and the power of broadcasting

Summary We investigate the power of a broadcast mechanism in a distributed network. We do so by considering the problem of synchronizing clocks in an errorfree network, under the assumption that there is no upper bound on message transmission time, but that broadcast messages are guaranteed to be received within an interval of size , for some fixed constant . This is intended to be an idealization of what happens in multiple access networks, such as the Ethernet. We then consider tradeoffs between the type and number of broadcasts, and the tightness of synchronization. Our results include (1) matching upper and lower bounds of (1+1/K) on the precision of clock synchronization attainable forn3 process usingK (n–1)-casts, 3Kn, (2) matching upper and lower bounds of (1+1/n) on the precision of clock synchronization attainable forn3 processes using an arbitrary number of (n–1)-casts, and (3) matching upper and lower bounds of (1+n–2/n) on the precision attainable using 2-casting. Joseph Y. Halpern received a B.Sc. in mathematics from the University of Toronto in 1975, and a Ph.D. in mathematics from Harvard University in 1981. In between, he spent two years as the head of the Mathematics Department at Bawku Secondary School in Ghara. After a year as a visiting scientist at MIT, he joined IBM in 1982, where he is currently a research staff member, as well as being a consulting professor at Stanford University. He was manager of the mathematics and related computer sience department at IBM from 1987–1989. He was program chairman and organizer of the first conference on Theoretical Aspects of Reasoning About Knowledge in 1986, program chairman of the 1986 ACM Symposium on Principles of Distributed Computing and of the 1991 ACM Symposium on Theory of Computing. He was recipent (together with Ron Fagin) of the MIT Publisher's Prize for best paper at the 1985 International Joint Conference on Artificial Intelligence and again winner of the Publisher's Prize at the 1989 International Joint Conference on Artificial Intelligence. Ichiro Suzuki is an Associate Professor of Computer Science at the University of Wisconsin-Milwaukee. He received a D.E. degree in information and computer sciences from Osaka University, Japan, in 1983. His major research interests are distributed systems and computational geometry.This author was supported in part by the National Science Foundation under grant CCR-9004346     

Undirecteds-t connectivity in polynomial time and sublinear space

Thes-t connectivity problem for undirected graphs is to decide whether two designated vertices,s andt, are in the same connected component. This paper presents the first known deterministic algorithms solving undirecteds-t connectivity using sublinear space and polynomial time. Our algorithms provide a nearly smooth time-space tradeoff between depth-first search and Savitch's algorithm. Forn vertex,m edge graphs, the simplest of our algorithms uses spaceO(s),n ^1/2log₂ nsnlog₂ n, and timeO(((m+n)n ² log² n)/s). We give a variant of this method that is faster at the higher end of the space spectrum. For example, with space (nlogn), its time bound isO((m+n)logn), close to the optimal time for the problem. Another generalization uses less space, but more time: spaceO(n ^1/logn), for 2log₂ n, and timen ^O(). For constant the time remains polynomial.     

Improving known solutions is hard

In this paper, we study the complexity of computing better solutions to optimization problems given other solutions. We use a model of computation suitable for this purpose, the counterexample computation model. We first prove that, if PH _P ³ , polynomial time transducers cannot compute optimal solutions for many problems, even givenn ^1– non-trivial solutions, for any >0. These results are then used to establish sharp lower bounds for several problems in the counterexample model. We extend the model by defining probabilistic counterexample computations and show that our results hold even in the presence of randomness.     

Range Estimation Is NP-Hard for ε2 Accuracy and Feasible for ε2−δ

The basic problem of interval computations is: given a function f(x ₁,..., x _n) and n intervals [x _i, x _i], find the (interval) range yof the given function on the given intervals. It is known that even for quadratic polynomials f(x ₁,..., x _n), this problem is NP-hard. In this paper, following the advice of A. Neumaier, we analyze the complexity of asymptotic range estimation, when the bound on the width of the input intervals tends to 0. We show that for small c > 0, if we want to compute the range with an accuracy c ₂, then the problem is still NP-hard; on the other hand, for every > 0, there exists a feasible algorithm which asymptotically, estimates the range with an accuracy c ^2–.     

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.     

Algorithms for dense graphs and networks on the random access computer

We improve upon the running time of several graph and network algorithms when applied to dense graphs. In particular, we show how to compute on a machine with word size = (logn) a maximal matching in ann-vertex bipartite graph in timeO(n ²+n ^2.5/)=O(n ^2.5/logn), how to compute the transitive closure of a digraph withn vertices andm edges in timeO(n ²+nm/), how to solve the uncapacitated transportation problem with integer costs in the range [O.C] and integer demands in the range [–U.U] in timeO ((n ³ (log log/logn)^1/2+n² logU) lognC), and how to solve the assignment problem with integer costs in the range [O.C] in timeO(n ^2.5 lognC/(logn/loglogn)^1/4).Assuming a suitably compressed input, we also show how to do depth-first and breadth-first search and how to compute strongly connected components and biconnected components in timeO(n+n ²/), and how to solve the single source shortest-path problem with integer costs in the range [O.C] in time0 (n ²(logC)/logn). For the transitive closure algorithm we also report on the experiences with an implementation.Most of this research was carried out while both authors worked at the Fachbereich Informatik, Universität des Saarlandes, Saarbrücken, Germany. The research was supported in part by ESPRIT Project No. 3075 ALCOM. The first author acknowledges support also from NSERC Grant No. OGPIN007.     

Expansion in Terms of Power of a Small Parameter of the Maximum Rank Distribution of a Random Boolean Matrix

The paper considers an N × n matrix (N n) over a field GF(2) that consists of random values with a distribution depending on a small parameter . The expansion is found in terms of the power of the parameter of the probability that the matrix rank is equal to n. Exact values of the first three coefficients are indicated.     

Parallel integer sorting using small operations

We consider the problem of sortingn integers in the range [0,n ^c -1], wherec is a constant. It has been shown by Rajasekaran and Sen [14] that this problem can be solved optimally inO(logn) steps on an EREW PRAM withO(n) n -bit operations, for any constant >O. Though the number of operations is optimal, each operation is very large. In this paper, we show thatn integers in the range [0,n ^c -1] can be sorted inO(logn) time withO(nlogn)O(1)-bit operations andO(n) O(logn)-bit operations. The model used is a non-standard variant of an EREW PRAMtthat permits processors to have word-sizes ofO(1)-bits and (logn)-bits. Clearly, the speed of the proposed algorithm is optimal. Considering that the input to the problem consists ofO (n logn) bits, the proposed algorithm performs an optimal amount of work, measured at the bit level.This work was partially supported by The Northeast Parallel Architectures Center (NPAC) at Syracuse University, Syracuse, NY 13244 and The Rome Air Development Center, under contract F30602-88-D-0027.     

Shape optimization of elasto-plastic bodies under plane strains: Sensitivity analysis and numerical implementation

Optimal shape design problems for an elastic body made from physically nonlinear material are presented. Sensitivity analysis is done by differentiating the discrete equations of equilibrium. Numerical examples are included.Notation U ^ad set of admissible continuous design parameters - U _h ^ad set of admissible discrete design parameters - function fromU _h ^ad defining shape of body - _h function fromU _h ^ad defining approximated shape of body - vector of nodal values of _h - { _n} sequence of functions tending to - () domain defined by - K bulk modulus - shear modulus - penalty parameter for contact condition - V() space of virtual displacements in() - V _h(_h) finite element approximation ofV() - J cost functional - J _h discretized cost functional - J algebraic form ofJ _h - (u) stress tensor - e(u) strain tensor - K stiffness matrix - f force vector - b(q) term arising from nonlinear boundary conditions - q vector of nodal degrees of freedom - p vector of adjoint state variables - J Jacobian of isoparametric mapping - |J| determinant ofJ - N vector of shape function values on parent element - L matrix of shape function derivatives on parent element - G matrix of Cartesian derivatives of shape functions - X matrix of nodal coordinates of element - D matrix of elastic coefficients - B strain-displacement matrix - _P part of boundary where tractions are prescribed - _u part of boundary where displacements are prescribed - variable part of boundary - strain invariant     

Comparative complexity of the representation of languages by probabilistic automata

We analyze the effect of the degree of isolation of a cut point on the number of states P(U, ) of a probabilistic automaton representing the language U. We give an example of a language Uⁿ consisting of words of length n such that there exist numbers < for which P(Uⁿ, )/P(Uⁿ, )0 as n.Translated from Kibernetika, No. 3, pp. 21–25, May–June, 1989.     

The expected additive weight of trees

Summary We consider a general additive weight of random trees which depends on the structure of the subtrees, on weight functions defined on the number of internal and external nodes and on the degrees of the nodes appearing in the tree and its subtrees. Choosing particular weight functions, the corresponding weight is an important parameter appearing in the analysis of sorting and searching algorithms. For a simply generated family of rooted planar trees , we shall derive a general approach to the computation of the average weight of a tree T with n nodes and m leaves for arbitrary weight functions. This general result implies exact and asymptotic expressions for many types of average weights of a tree T with n nodes if the weight functions are arbitrary polynomials in the number of nodes and leaves with coefficients depending on the node degrees.     

On the oracle complexity of factoring integers

The problem of factoring integers in polynomial time with the help of an infinitely powerful oracle who answers arbitrary questions with yes or no is considered. The goal is to minimize the number of oracle questions. LetN be a given compositen-bit integer to be factored, wheren = log₂ N. The trivial method of asking for the bits of the smallest prime factor ofN requiresn/2 questions in the worst case. A non-trivial algorithm of Rivest and Shamir requires onlyn/3 questions for the special case whereN is the product of twon/2-bit primes. In this paper, a polynomial-time oracle factoring algorithm for general integers is presented which, for any >0, asks at most n oracle questions for sufficiently largeN, thus solving an open problem posed by Rivest and Shamir. Based on a plausible conjecture related to Lenstra's conjecture on the running time of the elliptic curve factoring algorithm, it is shown that the algorithm fails with probability at mostN ^–/2 for all sufficiently largeN.     

On the Noninteger Polyhedron Vertices of the Three-index Axial Transportation Problem

For the three-index axial transportation polyhedron defined by the integer vector, existence of noninteger vertices was proved. In particular, the three-index n × m × k axial transportation polyhedron having vertices with r fractional components was shown to exist for and only for any number r {4,6,7,...,(n, m, k)}, where (n, m, k) = min{n, m + k - 2} + m + k - 2, n m k 3.