Constructing the visibility graph for n-line segments in O(n2) time

Given a set S of line segments in the plane, its visibility graph G_S is the undirected graph which has the endpoints of the line segments in S as nodes and in which two nodes (points) are adjacent whenever they ‘see’ each other (the line segments in S are regarded as nontransparent obstacles). It is shown that G_S can be constructed in O(n²) time and space for a set S of n nonintersecting line segments. As an immediate implication, the shortest path between two points in the plane avoiding a set of n nonintersecting line segments can be computed in O(n²) time and space     

External watchman routes

We consider the problem of finding a shortest watchman route from which the exterior of a polygon is visible (external watchman route). We present an O (n ⁴ log logn) algorithm to find shortest external watchman routes for simple polygons by transforming the external watchman route problem to a set of internal watchman route problems. Also, we present faster external watchman route algorithms for special cases. These include optimal O (n) algorithms for convex, monotone, star and spiral polygons and an O (n log logn) algorithm for rectilinear polygons.This work was supported in part by a grant from Texas Instruments, Inc. to S. Ntafos     

Shortest path between two simple polygons

Consider a collection of mutually disjoint simple polygons in the plane containing a total of n edges. Two of them are specified as a source polygon S and a target polygon T. We present an efficient algorithm for finding a shortest path between S and T avoiding the other polygons. We show that it runs in O(n²) time, using a linear-time algorithm for computing the visibility polygon of a point. This problem is related to a wire routing design of a certain type of LSI for which terminals are of polygonal shape and larger than a wire segment.     

Finding maximum cliques on circular-arc graphs

An algorithm is presented that, given the intersection model S of a circular-arc graph G with n vertices and m edges, finds a maximum-sized clique of G in O(n² log log n) time. The previous best time bound for this problem was O(n²) log n + mn).     

A time-optimal parallel algorithm for three-dimensional convex hulls

In this paper we present an O(1/ logn)-time parallel algorithm for computing the convex hull ofn points in ³. This algorithm usesO(@#@ n^1+a) processors on a CREW PRAM, for any constant 0 < 1. So far, all adequately documented parallel algorithms proposed for this problem use time at least O(log² n). In addition, the algorithm presented here is the first parallel algorithm for the three-dimensional convex hull problem that is not based on the serial divide-and-conquer algorithm of Preparata and Hong, whose crucial operation is the merging of the convex hulls of two linearly separated point sets. The contributions of this paper are therefore (i) an O(logn)-time parallel algorithm for the three-dimensional convex hull problem, and (ii) a parallel algorithm for this problem that does not follow the traditional paradigm.This paper was presented in preliminary form at the 9th Annual ACM Symposium on Computational Geometry, San Diego, CA, May 1993 [32]. The work of N. M. Amato was supported in part by an AT&T Bell Laboratories 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 N. M. Amato was with the Department of Computer Science at the University of Illinois. The work of F. P. Preparata was supported in part by NSF Grants CCR-91-96152, CCR-91-96176, and ONR Contract N00014-91-J-4052, ARPA order 8225.     

Note on covering monotone orthogonal polygons with star-shaped polygons

In 1986, Keil provided an O(n²) time algorithm for the problem of covering monotone orthogonal polygons with the minimum number of r-star-shaped orthogonal polygons. This was later improved to O(n) time and space by Gewali et al. in [L. Gewali, M. Keil, S.C. Ntafos, On covering orthogonal polygons with star-shaped polygons, Information Sciences 65 (1992) 45-63]. In this paper we simplify the latter algorithm—we show that with a little modification, the first step Sweep1 of the discussed algorithm—which computes the top ceilings of horizontal grid segments—can be omitted.In addition, for the minimum orthogonal guard problem in the considered class of polygons, our approach provides a linear time algorithm which uses O(k) additional space, where k is the size of the optimal solution—the algorithm in [L. Gewali, M. Keil, S.C. Ntafos, On covering orthogonal polygons with star-shaped polygons, Information Sciences 65 (1992) 45-63] uses both O(n) time and O(n) additional space.     

Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors

We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n ² log n) toO(n log² n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.The results in this paper are a part of Y. C. Yee's Ph.D. thesis done at SUNY at Albany. He was supported in part by NSF Grants IRI-8703430 and CCR-8805782. S. S. Ravi was supported in part by NSF Grants DCI-86-03318 and CCR-89-05296.     

A Simple and Fast Min-Cut Algorithm

We present an algorithm which calculates a minimum cut and its weight in an undirected graph with nonnegative real edge weights, n vertices and m edges, in time O(max(log n, min(m/n,δ_G/ε)) n²), where ε is the minimal edge weight, and δ_G is the minimal weighted degree. For integer edge weights this time is further improved to O(δ_G n²) and O(λ_G n²). In both cases these bounds are improvements of the previously known best bounds of deterministic algorithms. These were O(nm + n² log n) for real edge weights and O(nM + n²) and O(M + λ_G n²) for integer weights, where M is the sum of all edge weights.     

Halfplanar range search in linear space and O(n0.695) query time

Let S denote a set of n points in the Euclidean plane. A halfplanar range query specifies a halfplane h and requires the determination of the number of points in S which are contained in h. A new data structure is described which stores S in O(n) space and allows us to answer a halfplanar range query in O(n^log₂(1+√5)−1) time in the worst case, thus improving the best result known before. The structure can be built in O(n log n) time.     

Selecting distances in the plane

We present a randomized algorithm for computing the kth smallest distance in a set ofn points in the plane, based on the parametric search technique of Megiddo [Mel]. The expected running time of our algorithm is O(n^4/3 log^8/3 n). The algorithm can also be made deterministic, using a more complicated technique, with only a slight increase in its running time. A much simpler deterministic version of our procedure runs in time O(n^3/2 log^5/2 n). All versions improve the previously best-known upper bound ofO(@#@ n^9/5 log^4/5 n) by Chazelle [Ch]. A simpleO(n logn)-time algorithm for computing an approximation of the median distance is also presented.Part of this work was done while the first two authors were visting DIMACS, Rutgers University, New Brunswick, NJ. Work by the first three authors has been partly supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC88-09648. Work by the second author has also been supported by National Security Agency Grant MDA 904-89-H-2030. Work by the third author has also been supported by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

Improved algorithm for all pairs shortest paths

We present an improved algorithm for all pairs shortest paths. For a graph of n vertices our algorithm runs in O(n³(loglogn/logn)^5/7) time. This improves the best previous result which runs in O(n³(loglogn/logn)^1/2) time.     

Reducing communication costs in robust peer-to-peer networks

Several recent research results describe how to design Distributed Hash Tables (DHTs) that are robust to adversarial attack via Byzantine faults. Unfortunately, all of these results require a significant blowup in communication costs over standard DHTs. For example, to perform a lookup operation, all such robust DHTs of which we are aware require sending O(log³n) messages while standard DHTs require sending only O(logn), where n is the number of nodes in the network. In this paper, we describe protocols to reduce the communication costs of all such robust DHTs. In particular, we give a protocol to reduce the number of messages sent to perform a lookup operation from O(log³n) to O(log²n) in expectation. Moreover, we also give a protocol for sending a large (i.e. containing Ω(log⁴n) bits) message securely through a robust DHT that requires, in expectation, only a constant blowup in the total number of bits sent compared with performing the same operation in a standard DHT. This is an improvement over the O(log²n) bit blowup that is required to perform such an operation in all current robust DHTs. Both of our protocols are robust against an adaptive adversary.     

An algorithm with linear expected running time for string editing with substitutions and substring reversals

The edit distance between given two strings X and Y is the minimum number of edit operations that transform X into Y without performing multiple operations that involve the same position. Ordinarily, string editing is based on character insert, delete, and substitute operations. Motivated from the facts that substring reversals are observed in genomic sequences, and it is not always possible to transform a given sequence X into a given sequence Y by reversals alone (e.g., X is all 0's, and Y is all 1's), Muthukrishnan and Sahinalp [S. Muthukrishnan, S.C. Sahinalp, Approximate nearest neighbors and sequence comparison with block operations, in: Proc. ACM Symposium on Theory of Computing (STOC), 2000, pp. 416-424; S. Muthukrishnan, S.C. Sahinalp, An improved algorithm for sequence comparison with block reversals, Theoretical Computer Science 321 (1) (2004) 95-101] considered a “simple” well-defined edit distance model in which the edit operations are: replace a character, and reverse and replace a substring. A substring of X can only be reversed if the reversal results in a match in the same position in Y. The cost of each character replacement and substring reversal is 1. The distance in this case is defined only when |X|=|Y|=n. There is an algorithm for computing the distance in this model with worst-case time complexity O(nlog²n) [S. Muthukrishnan, S.C. Sahinalp, An improved algorithm for sequence comparison with block reversals, Theoretical Computer Science 321 (1) (2004) 95-101]. We present a dynamic programming algorithm with worst-case time complexity O(n²) but its expected running-time is O(n). In our dynamic programming solution the weights of edit operations can vary for different substitutions, and the costs of reversals can be a function of the reversal-length.     

An optimal speed-up parallel algorithm for triangulating simplicial point sets in space

Previous research on developing parallel triangulation algorithms concentrated on triangulating planar point sets.O(log³ n) running time algorithms usingO(n) processors have been developed in Refs. 1 and 2. Atallah and Goodrich⁽³⁾ presented a data structure that can be viewed as a parallel analogue of the sequential plane-sweeping paradigm, which can be used to triangulate a planar point set inO(logn loglogn) time usingO(n) processors. Recently Merks⁽⁴⁾ described an algorithm for triangulating point sets which runs inO(logn) time usingO(n) processors, and is thus optimal. In this paper we develop a parallel algorithm for triangulating simplicial point sets in arbitrary dimensions based on the idea of the sequential algorithm presented in Ref. 5. The algorithm runs inO(log² n) time usingO(n/logn) processors. The algorithm hasO(n logn) as the product of the running time and the number of processors; i.e., an optimal speed-up.     

Multi-mesh of trees with its parallel algorithms

In recent years the multi-mesh network [Proceedings of the Ninth International Parallel Processing Symposium, Santa Barbara, CA, April 25–28, 1995, 17; IEEE Trans. on Comput. 68 (5) (1999) 536] has created a lot of interests among the researchers for its efficient topological properties. Several parallel algorithms for various trivial and nontrivial problems have been mapped on this network. However, because of its O(n) diameter, a large class of algorithms that involves frequent data broadcast in a row or in a column or between the diametrically opposite processors, requires O(n) time on an n×n multi-mesh. In search of faster algorithms, we introduce, in this paper, a new network topology, called multi-mesh of trees. This network is built around the multi-mesh network and the mesh of trees. As a result it can perform as efficiently as a multi-mesh network and also as efficiently as a mesh of trees. Several topological properties, including number of links, diameter, bisection width and decomposition are discussed. We present the parallel algorithms for finding sum of n⁴ elements and the n²-point Lagrange interpolation both in O(logn)¹ time. The solution of n²-degree polynomial equation, n²-point DFT computation and sorting of n² elements are all shown to run in O(logn) time too. The communication algorithms one-to-all, row broadcast and column broadcast are also described in O(logn) time. This can be compared with O(n) time algorithms on multi-mesh network for all these problems.     

Randomized Algorithms for 3-SAT

Schoning proposed a simple yet efficient randomized algorithm for solving the k-SAT problem. In the case of 3-SAT, the algorithm has an expected running time of poly(n)·(4/3)ⁿ = O(1.334ⁿ). In this paper we present randomized algorithms and show that one of them has O(1.3302ⁿ) expected running time, improving Schoning's algorithm. (Note. At this point, the fastest randomized algorithm for 3-SAT is the one given by Iwama and Tamaki that runs in O(1.324ⁿ).)     

Total domination in interval graphs

A total dominating set of a graph G is a subset S of nodes such that each node of G is adjacent to some node of S. We present an O(n²) time algorithm for finding a minimum cardinality total dominating set in an interval graph (one which represents intersecting intervals on the line) by reducing it to a shortest path problem on an appropriate acyclic directed network.     

A note on maximum independent sets in rectangle intersection graphs

Finding the maximum independent set in the intersection graph of n axis-parallel rectangles is NP-hard. We re-examine two known approximation results for this problem. For the case of rectangles of unit height, Agarwal, van Kreveld and Suri [Comput. Geom. Theory Appl. 11 (1998) 209-218] gave a (1+1/k)-factor algorithm with an O(nlogn+n^2k−1) time bound for any integer constant k?1; we describe a similar algorithm running in only O(nlogn+nΔ^k−1) time, where Δ?n denotes the maximum number of rectangles a point can be in. For the general case, Berman, DasGupta, Muthukrishnan and Ramaswami [J. Algorithms 41 (2001) 443-470] gave a ⌈log_kn⌉-factor algorithm with an O(n^k+1) time bound for any integer constant k?2; we describe similar algorithms running in O(nlogn+nΔ^k−2) and n^O(k/logk) time.     

A note on the computation of the k-closure of a graph

Bondy and Chvátal (1976) introduced the k-closure of a graph and described an algorithm which constructs it in O(n⁴) steps. In this note, a method having complexity O(n³) is presented.     

Algorithms for solving the symmetry number problem on trees

The symmetry number of a tree is defined as the number of nodes of the maximum subtree of the tree that exhibits axial symmetry. Chin and Yen have presented an algorithm for solving the problem of finding the symmetry number of unrooted unordered trees in time O(n⁴). In this paper we present an improved algorithm for solving the symmetry number problem on trees that runs in time O(n³). We also show that our algorithm needs O(n²logn) time for trees with bounded degrees.