14297439
Geometric permutations of high dimensional spheres
We prove the maximum number of geometric permutations, induced by line transversals to a set of <i>n</i> pairwise disjoint congruent spheres in <i>R<sup>d</sup></i> with <i>d</i> ⪈ 3, is no more than 4 when <i>n</i> is sufficiently large, achieving the best known upper bound for this problem. We also prove the maximum number of geometric permutations of a set of <i>n</i> noncongruent spheres of bounded radius ratio in R<sup>d</sup>, <i>d</i> ⪈ 3, is at most 2<sup>[√2<i>M</i>]+1</sup>, where <i>M</i> is the ratio or the largest radius and the smallest radius. Our result settles a conjecture in combinatorial geometry.
6260724
Finding an optimal path without growing the tree
For problems on computing an optimal path as well as its length in a certain setting, the "standard" approach for finding an actual optimal path is by building (or "growing") a single-source optimal path tree. In this paper, we study a class of optimal path problems with the following phenomenon: The space complexity of the algorithms for reporting the lengths of single-source optimal paths for these problems is asymptotically smaller than the space complexity of the "standard" tree-growing algorithms for finding actual optimal paths. We present a general and efficient algorithmic paradigm for finding an actual optimal path for such problems without having to grow a single-source optimal path tree. Our paradigm is based on the "marriage-before-conquer" strategy, the prune-and-search technique, and a new data structure called clipped trees. The paradigm enables us to compute an actual path for a number of optimal path problems and dynamic programming problems in computational geometry, graph theory, and combinatorial optimization. Our algorithmic solutions improve the space bounds (in certain cases, the time bounds as well) of the previously best known algorithms, and settle some open problems. Our techniques are likely to be applicable to other problems.
19187096
Traveling salesman problem of segments
In this paper, we present a polynomial time approximation scheme (PTAS) for a variant of the traveling salesman problem (called segment TSP) in which a traveling salesman tour is sought to traverse a set of n ∊-separated segments in two dimensional space. Our results are based on an interesting combinatorial result which bounds the total number of entry points in an optimal TSP tour and a generalization of Arora's technique5 for Euclidean TSP (of a set of points). The randomized version of our algorithm takes O(n2(log n)O(1/∊2)) time to compute a (1+∊)-approximation with probability ≥l/2, and can be derandomized with an additional factor of O(n2).
33666708
Topological Peeling and Applications
We present a new approach, called topological peeling, for traversing a portion AR of the arrangement formed by n lines within a convex region R on the plane. Topological peeling visits the cells of AR in a fashion of propagating a "wave" of a special shape (called a double-wriggle curve) starting at a single source point. This special traversal fashion enables us to solve several problems (e.g., computing shortest paths) on planar arrangements to which previously best known arrangement traversal techniques such as topological sweep and topological walk may not be directly applicable. Our topological peeling algorithm takes O(K + n log(n + r)) time and O(n + r) space, where K is the number of cells in AR and r is the number of boundary vertices of R. Comparing with topological walk, topological peeling uses a simpler and more efficient way to sweep different types of lines, and relies heavily on exploring small local structures, rather than a much larger global structure. Experiments show that, on average, topological peeling outperforms topological walk by 10–25% in execution time.
17909513
Determining an optimal penetration among weighted regions in two and three dimensions
We present efficient algorithms for solving the problem of computing an optimal penetration (a ray or a semi-ray) among weighted regions in 2-D and 3-D spaces. This problem finds applications in several areas, such as radiation therapy, geological exploration, and environmental engineering. Our algorithms are based on a combination of geometric techniques and optimization methods. Our geometric analysis shows that the d-D (d = 2, 3) optimal penetration problem can be reduced to solving O(n2(d−1)) instances of certain special types of non-linear optimization problems, where n is the total number of vertices of the regions. We also give implementation results of our 2-D algorithms.
27008432
Traveling Salesman Problem of Segments
In this paper, we present a polynomial time approximation scheme (PTAS) for a variant of the traveling salesman problem (called segment TSP) in which a traveling salesman tour is sought to traverse a set of n Ɛ-separated segments in two dimensional space. Our results are based on a number of geometric observations and an interesting generalization of Arora's technique [5] for Euclidean TSP (of a set of points). The randomized version of our algorithm takes O(n2(log n)O(1/Ɛ4)) time to compute a (1 + Ɛ)-approximation with probability ≥ 1/2, and can be derandomized with an additional factor of O(n2). Our technique is likely applicable to TSP problems of certain Jordan arcs and related problems.
2775894
Rigorous development of a safety-critical system based on coordinated atomic actions
This paper describes our experience using coordinated atomic (CA) actions as a system structuring tool to design and validate a sophisticated control system for a complex industrial application that has high reliability and safety requirements. Our study is based on the "Fault-Tolerant Production Cell", which represents a manufacturing process involving redundant mechanical devices (provided in order to enable continued production in the presence of machine faults). The challenge posed by the model specification is to design a control system that maintains specified safety and liveness properties even in the presence of a large number and variety of device and sensor failures. We discuss in this paper: i) a design for a control program that uses CA actions to deal with both safety-related and fault tolerance concerns, and ii) the formal verification of this design based on the use of model-checking. We found that CA action structuring facilitated both the design and verification tasks by enabling the various safety problems (e.g. clashes of moving machinery) to be treated independently. The formal verification activity was performed in parallel with the design activity the interaction between them resulted in a combined exercise in "design for validation".
15417765
The proof of a conjecture of Bouabdallah and Sotteau
Let G be a connected graph of order n. A routing in G is a set of n(n 1) fixed paths for all ordered pairs of vertices of G. The edge-forwarding index of G, (G), is the minimum of the maximum number of paths specified by a routing passing through any edge of G taken over all routings in G, and ,n is the minimum of (G) taken over all graphs of order n with maximum degree at most . To determine n 2p 1,n for 4p 2p/3 1 ≤ n ≤ 6p, A. Bouabdallah and D. Sotteau proposed the following conjecture in [On the edge forwarding index problem for small graphs, Networks 23 (1993), 249–255]. The set 3 {1, 2, . . . , (4p)/3} can be partitioned into 2p pairs plus singletons such that the set of differences of the pairs is the set 2 {1, 2, . . . , p}. This article gives a proof of this conjecture and determines that n 2p 1,n is equal to 5 if 4p 2p/3 1 ≤ n ≤ 6p and to 8 if 3p p/3 1 ≤ n ≤ 3p (3p)/5 for any p ≥ 2. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 292–296 2004
26138426
2-diameter of de Bruijn graphs
Binary strings are used as vertex labels or components of vertex labels. We will abbreviate “the vertex with label X” as “vertex x.” The binarji direcred de Briiijn graph of dimension n , denoted B ( n ) , has 2 ” vertices which are labeled with the binary strings of length n . There is an arc from any vertex x, x2 xn to the vertices x2x3 x,O and x2x3 x,, 1. We say that the ith coordinate of ,Y is x, . Any .u, is equal toOor l , andZ, = 1 x i . The undirected binary de Bruijn graph UB( n ) is obtained from B( n) by deleting the orientation of the arcs and omitting multiple edges and loops. It is well known that UB( n ) is 2-connected and that its diameter (maximum of the distances between all pairs of vertices) is equal to n . Due to their bounded maximum degree equal to 4 and their low diameter, de Bruijn graphs have been proposed as a possible good interconnection network for a parallel architecture [ 11. They have also been shown to solve a wide class of problems [ 21. For a k-connected graph, Hsu [ 4 ] introduced the notion of the kdiameter as follows: Given any two vertices x and y , a k-container between x and y is a set of k vertex disjoint paths between xand y . The length ofa k-container is the length of the longest of the k paths. The kdistance d k ( x , y ) between x and y is the minimum of the lengths of all the k-containers. Then, the k-diameter of a graph G is the maximum of d k ( x , y) for all pairs of vertices x and y . General results on the k-diameters of k-regular kconnected graphs can be found in [ 41 or [ 51. Results for some particular classes ofgraphs and many open problems can also be found in [ 41. It was shown by Pradhan and Reddy [ 7 ] that the 2diameter of U B ( n ) is less than or equal to 2n. The 2diameter is also obviously at least n. The aim of this paper was to prove that it is exactly n. In other words, between any two vertices of UB( n ) , there exist two internally vertex disjoint paths of length at most n. This gives a good measure of the fault tolerance of the graph [ 61. Let us first introduce some notation and recall some properties of the de Bruijn digraph B( n ) : Given two vertices x and y , we will denote f i x , y ] as a shortest path P from x to y . The length of this path, denoted by I PIX, y ] 1, is the number of edges in the path and is also the distance d ( x , y ) from x to y . P [ x , y ] also represents the set of vertices of the path, including its extremities.
5963621
Concurrent Exception Handling and Resolution in Distributed Object Systems
We address the problem of how to handle exceptions in distributed object systems. In a distributed computing environment, exceptions may be raised simultaneously in different processing nodes and thus need to be treated in a coordinated manner. Mishandling concurrent exceptions can lead to catastrophic consequences. We take two kinds of concurrency into account: 1) Several objects are designed collectively and invoked concurrently to achieve a global goal and 2) multiple objects (or object groups) that are designed independently compete for the same system resources. We propose a new distributed algorithm for resolving concurrent exceptions and show that the algorithm works correctly even in complex nested situations, and is an improvement over previous proposals in that it requires only O(n/sub max/N/sup 2/) messages, thereby permitting quicker response to exceptions.
195710562
On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms
In this work, we clarify, extend and solve an open problem concerning the computational complexity for packet scheduling algorithms to achieve tight end-to-end delay bounds. We first focus on the difference between the time a packet finishes service in a scheduling algorithm and its virtual finish time under a GPS (General Processor Sharing) scheduler, called GPS-relative delay. We prove that, under a slightly restrictive but reasonable computational model, the lower bound computational complexity of any scheduling algorithm that guarantees O(1) GPS-relative delay bound is Ω (log 2 n) (widely believed as a "folklore theorem" but never proved). We also discover that, surprisingly, the complexity lower bound remains the same even if the delay bound is relaxed to O(na) for 0‹a⋵1. This implies that the delay-complexity tradeoff curve is "flat" in the "interval" [O(1), O(n)). We later extend both complexity results (for O(1) or O(na) delay) to a much stronger computational model. Finally, we show that the same complexity lower bounds are conditionally applicable to guaranteeing tight end-to-end delay bounds. This is done by untangling the relationship between the GPS-relative delay bound and the end-to-end delay bound.