On geodesic properties of polygons relevant to linear time triangulation

Triangulating a simple polygon ofn vertices inO(n) time is one of the main open problems in computational geometry. The fastest algorithm to date, due to Tarjan and van Wyk, runs inO(n log logn), but several classes of simple polygons have been shown to admit linear time traingulation. Famous examples of such classes are: star-shaped, monotone, spiral, edge visible, and weakly externally visible polygons. The notion of geodesic paths is used here to characterize all classes of polygons for which linear time triangulation algorithms are known. First we introduce a new class of polygons,palm polygons, which subsumes many known classes of polygons for which linear time triangulation algorithms exist, and present a linear time algorithm for triangulating polygons in this class. Then a class of polygons,crab polygons, is defined and shown to contain all classes of existing polygons for which linear time triangulation algorithms are known. As a byproduct of this characterization, a new, very simple linear time algorithm for triangulating star-shaped polygons is obtained.Research supported by Faculty of Graduate Studies and Research (McGill University) and NSERC under grant OGP0036737Research supported by FCAR grant EQ-1678 and NSERC grant A9293     

Analysis of the standard deletion algorithms in exact fit domain binary search trees

It is well known that the expected search time in anN node binary search tree generated by a random sequence of insertions isO(logN). Little has been published about the asymptotic cost when insertions and deletions are made following the usual algorithms with no attempt to retain balance. We show that after a sufficient number of updates, each consisting of choosing an element at random, removing it, and reinserting the same value, that the average search cost is (N ^1/2).This work was done in part while the first author was at the University of Waterloo. This work was supported by an NSERC '67 Science Scholarship and Grant A-8237 and the Information Technology Research Centre of Ontario.     

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.     

Parallel consistent labeling algorithms

Mackworth and Freuder have analyzed the time complexity of several constraint satisfaction algorithms.⁽¹⁾ Mohr and Henderson have given new algorithms, AC-4 and PC-3, for arc and path consistency, respectively, and have shown that the arc consistency algorithm is optimal in time complexity and of the same order space complexity as the earlier algorithms.⁽²⁾ In this paper, we give parallel algorithms for solving node and arc consistency. We show that any parallel algorithm for enforcing are consistency in the worst case must have O(na) sequential steps, wheren is number of nodes, anda is the number of labels per node. We give several parallel algorithms to do arc consistency. It is also shown that they all have optimal time complexity. The results of running the parallel algorithms on a BBN Butterfly multiprocessor are also presented.This work was partially supported by NSF Grants MCS-8221750, DCR-8506393, and DMC-8502115.     

Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems

We obtain faster algorithms for problems such as r-dimensional matching and r-set packing when the size k of the solution is considered a parameter. We first establish a general framework for finding and exploiting small problem kernels (of size polynomial in k). This technique lets us combine Alon, Yuster and Zwick’s color-coding technique with dynamic programming to obtain faster fixed-parameter algorithms for these problems. Our algorithms run in time O(n+2 ^O(k)), an improvement over previous algorithms for some of these problems running in time O(n+k ^O(k)). The flexibility of our approach allows tuning of algorithms to obtain smaller constants in the exponent. Research initiated at the International Workshop on Fixed Parameter Tractability in Computational Geometry and Games, Bellairs Research Institute of McGill University, Holetown, Barbados, Feb. 7–13, 2004, organized by S. Whitesides. D.M. Thilikos supported by the EU within the 6th Framework Programme under contract 001907 (DELIS) and by the Spanish CICYT project TIC-2002-04498-C05-03 (TRACER).     

An upper bound on the time complexity of iterative-deepening-A*

This paper establishes an upper bound on the time complexity of iterative-deepening-A^* (IDA^*) in terms of the number of states that are surely-expanded by A^* during a state space tree search. It is shown that given an admissible evaluation function, IDA^* surely-expands in the worst caseN(N+1)/2 states, whereN is the number of states that are surely-expanded by A^*. The conditions that give rise to the worst case performance of IDA^* on any state space tree are described. Worst case examples are also given for uniform and non-uniform state space trees.This work was supported in part by the Canadian Natural Sciences and Engineering Research Council Grant NSERC3599.     

The Compatibility of Binary Characters on Phylogenetic Networks: Complexity and Parameterized Algorithms

In a recent article, Nakhleh, Ringe and Warnow introduced perfect phylogenetic networks—a model of language evolution where languages do not evolve via clean speciation—and formulated a set of problems for their accurate reconstruction. Their new methodology assumes networks, rather than trees, as the correct model to capture the evolutionary history of natural languages. They proved the NP-hardness of the problem of testing whether a network is a perfect phylogenetic one for characters exhibiting at least three states, leaving open the case of binary characters, and gave a straightforward brute-force parameterized algorithm for the problem of running time O(3 ^k n), where k is the number of bidirectional edges in the network and n is its size. In this paper, we first establish the NP-hardness of the binary case of the problem. Then we provide a more efficient parameterized algorithm for this case running in time O(2 ^k n ²). The presented algorithm is very simple, and utilizes some structural results and elegant operations developed in this paper that can be useful on their own in the design of heuristic algorithms for the problem. The analysis phase of the algorithm is very elegant using amortized techniques to show that the upper bound on the running time of the algorithm is much tighter than the upper bound obtained under a conservative worst-case scenario assumption. Our results bear significant impact on reconstructing evolutionary histories of languages—particularly from phonological and morphological character data, most of which exhibit at most two states (i.e., are binary), as well as on the design and analysis of parameterized algorithms. Research of I.A. Kanj was supported in part by DePaul University Competitive Research Grant.     

Real Two Dimensional Scaled Matching

Scaled Matching refers to the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary real-sized scale, appears. Scaled matching is an important problem that was originally inspired by Computer Vision. Finding a combinatorial definition that captures the concept of real scaling in discrete images has been a challenge in the pattern matching field. No definition existed that captured the concept of real scaling in discrete images, without assuming an underlying continuous signal, as done in the image processing field. We present a combinatorial definition for real scaled matching that scales images in a pleasing natural manner. We also present efficient algorithms for real scaled matching. The running times of our algorithms are as follows. For T, a two-dimensional n×n text array, and P, an m×m pattern array, we find in T all occurrences of P scaled to any real value in time O(nm ³+n ² mlog m). Research of A. Amir partially supported by ISF grant 282/01 and NSF grant CCR-01-04494.     

Potential Function Analysis of Greedy Hot-Potato Routing

We study the problem of packet routing in synchronous networks. We put forward a notion of greedy hot-potato routing algorithms and devise tech- niques for analyzing such algorithms. A greedy hot-potato routing algorithm is one where: • The processors have no buffer space for storing delayed packets. Therefore, each packet must leave any intermediate processor at the step following its arrival. • Packets always advance toward their destination if they can. Namely, a packet must leave its current intermediate node via a link which takes it closer to its destination, unless all these links are taken by other packets. Moreover, in this case all these other packets must advance toward their destinations. We use potential function analysis to obtain an upper bound of O(n k ^1/2 ) on the running time of a wide class of algorithms in the two-dimensional n × n mesh, for routing problems with a total of k packets. The same techniques can be generalized to obtain an upper bound of O(exp(d) n ^d-1 k ^1/d ) on the running time of a wide class of algorithms in the d -dimensional n ^d mesh, for routing problems with a total of k packets. Received December 1993, and in final form March 1997.     

On the Parameterized Complexity of Layered Graph Drawing

We consider graph drawings in which vertices are assigned to layers and edges are drawn as straight line-segments between vertices on adjacent layers. We prove that graphs admitting crossing-free h-layer drawings (for fixed h) have bounded pathwidth. We then use a path decomposition as the basis for a linear-time algorithm to decide if a graph has a crossing-free h-layer drawing (for fixed h). This algorithm is extended to solve related problems, including allowing at most k crossings, or removing at most r edges to leave a crossing-free drawing (for fixed k or r). If the number of crossings or deleted edges is a non-fixed parameter then these problems are NP-complete. For each setting, we can also permit downward drawings of directed graphs and drawings in which edges may span multiple layers, in which case either the total span or the maximum span of edges can be minimized. In contrast to the Sugiyama method for layered graph drawing, our algorithms do not assume a preassignment of the vertices to layers. Research initiated at the International Workshop on Fixed Parameter Tractability in Graph Drawing, Bellairs Research Institute of McGill University, Holetown, Barbados, Feb. 9–16, 2001, organized by S. Whitesides. Research of Canada-based authors is supported by NSERC; research of Quebec-based authors is also supported by a grant from FCAR. Research of D.R. Wood completed while visiting McGill University. Research of G. Liotta supported by CNR and MURST.     

Dynamic multi-dimensional data structures based on quad- and k—d trees

Summary Quad-trees and k—d trees have been noted for their lack of dynamic properties as data structures for multi-dimensional point sets. We describe a method to insert points in a quad-tree while keeping the tree balanced that achieves an average time complexity of O(log² N) per insertion, where N is the number of updates performed on the quad-tree. We define a structure similar to a quad-tree, called a pseudo quad-tree, and show how it can be used to handle both insertions and deletions in O(log² N) average time. We also discuss how quad-trees and pseudo quadtrees can be extended for use in configurations of points in which more than one point may have a same value in some equal coordinate, without altering the earlier time bounds for insertions, deletions and queries. Similar algorithms are given for k—d trees and the same average time bounds for insertion and deletion are achieved.The work of this author was partially supported by the Netherlands Organization for the Advancement of Pure Research (ZWO).     

Parallel construction of binary trees with near optimal weighted path length

We present parallel algorithms to construct binary trees with almost optimal weighted path length. Specifically, assuming that weights are normalized (to sum up to one) and error refers to the (absolute) difference between the weighted path length of a given tree and the optimal tree with the same weights, we present anO (logn)-time andn(log lognl logn)-EREW-processor algorithm which constructs a tree with error less than 0.18, andO (k logn log^* n)-time andn-CREW-processor algorithm which produces a tree with error at most l/n ^k , and anO (k ² logn)-time andn ²-CREW-processor algorithm which produces a tree with error at most l/n ^k . As well, we describe two sequential algorithms, anO(kn)-time algorithm which produces a tree with error at most l/n ^k , and anO(kn)-time algorithm which produces a tree with error at most . The last two algorithms use different computation models.The first author's research was supported in part by NSERC Research Grant 3053. A part of this work was done while the second author was at the University of British Columbia.     

Recognizing polygons,or how to spy

A new class of so-called pseudo-starshaped polygons is introduced. A polygon is pseudo-star-shaped if there exists a point from which the whole interior of the polygon can be seen, provided it is possible to see through single edges. We show that the class of pseudo-star-shaped polygons unifies and generalizes the well-known classes of convex, monotone and pseudostar-sphaped polygons. We give algorithms for testing whether a polygon is pseudostar-shaped from a given point in linear time, and for constructing all regions from which the polygon is pseudo-star-shaped in quadratic time. We show the latter algorithm to be worst-case optimal. Also, we give efficient algorithms solving standard geometrical problems such as point-location and triangulation for pseudo-starshaped polygons.A preliminary version of this paper has been presented at the 24 th Allerton Conference on Communication, Control and Computing, Monticello, Ill, October 1986Research for this paper was done while the author was at Carleton UniversityResearch for this paper was done in part while the author was visiting Carleton UniversityThis research was supported in part by NSERC and by Carleton University     

Derandomization,witnesses for Boolean matrix multiplication and construction of perfect hash functions

Small sample spaces with almost independent random variables are applied to design efficient sequential deterministic algorithms for two problems. The first algorithm, motivated by the attempt to design efficient algorithms for the All Pairs Shortest Path problem using fast matrix multiplication, solves the problem of computingwitnesses for the Boolean product of two matrices. That is, ifA andB are twon byn matrices, andC=AB is their Boolean product, the algorithm finds for every entryC _ij =1 a witness: an indexk so thatA _ik =B _kj =1. Its running time exceeds that of computing the product of twon byn matrices with small integer entries by a polylogarithmic factor. The second algorithm is a nearly linear time deterministic procedure for constructing a perfect hash function for a givenn-subset of {1,...,m}.Part of this paper was presented at the IEEE 33rd Symposium on Foundations of Computer Science.Research supported in part by a USA-Israeli BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.Supported by an Alon Fellowship and by a grant from the Israel Science Foundation administered by the Israeli Academy of Sciences. Some of this work was done while the author was with the IBM Almaden Research Center.     

Maintaining bridge-connected and biconnected components on-line

We consider the twin problems of maintaining the bridge-connected components and the biconnected components of a dynamic undirected graph. The allowed changes to the graph are vertex and edge insertions. We give an algorithm for each problem. With simple data structures, each algorithm runs inO(n logn +m) time, wheren is the number of vertices andm is the number of operations. We develop a modified version of the dynamic trees of Sleator and Tarjan that is suitable for efficient recursive algorithms, and use it to reduce the running time of the algorithms for both problems toO(m(m,n)), where is a functional inverse of Ackermann's function. This time bound is optimal. All of the algorithms useO(n) space.Research at Princeton University supported in part by National Science Foundation Grant DCR-86-05962 and Office of Naval Research Contract N00014-91-J-1463.This work was partially done while the author was at the Department of Computer Science, Princeton University, Princeton, NJ 08544, USA.     

On the time and space complexity of computation using write-once memory or is pen really much worse than pencil?

We introduce a model of computation based on the use of write-once memory. Write-once memory has the property that bits may be set but not reset. Our model consists of a RAM with a small amount of regular memory (such as logarithmic orn ^α for α<1, wheren is the size of the problem) and a polynomial amount of write-once memory. Bounds are given on the time required to simulate on write-once memory algorithms which originally run on a RAM with a polynomial amount of regular memory. We attempt to characterize algorithms that can be simulated on our write-once memory model with very little slow-down. A persistent computation is one in which, at all times, the memory state of the computation at any previous point in time can be reconstructed. We show that any data structure or computation implemented on this write-once memory model can be made persistent without sacrificing much in the way of running time or space. The space requirements of algorithms running on the write-once model are studied. We show that general simulations of algorithms originally running on a RAM with regular memory by algorithms running on our write-once memory model require space proportional to the number of steps simulated. In order to study the space complexity further, we define an analogue of the pebbling game, called the pebble-sticker game. A sticker is different from a pebble in that it cannot be removed once placed on a node of the computation graph. As placing pebbles correspond to writes to regular memory, placing stickers correspond to writes to the write-once memory. Bounds are shown on pebble-sticker tradeoffs required to evaluate trees and planar graphs. Finally, we define the complexity class WO-PSPACE as the class of problems which can be solved with a polynomial amount of write-once memory, and show that it is equal toP. The research of S. Irani was supported by NSF Grant No. DCF-85-13926, and a Tandem Corporation Fellowship. R. Rubinfeld's research was supported by NSF Grant No. CCR 88-13632 and an IBM Graduate Fellowship.     

Computing the intersection-depth of polyhedra

Given two intersecting polyhedraP, Q and a directiond, find the smallest translation ofQ alongd that renders the interiors ofP andQ disjoint. The same problem can also be posed without specifying the direction, in which case the minimum translation over all directions is sought. These are fundamental problems that arise in robotics and computer vision. We develop techniques for implicitly building and searching convolutions and apply them to derive efficient algorithms for these problems.The work of this author was partially supported by National Science Foundation Grant CCR90-02352.The work of this author was partially supported by Grant A3583 from the Natural Sciences and Engineering Research Council of Canada.     

Approximation algorithms for shop scheduling problems with minsum objective: A correction

We present a correction to the paper, “Approximation algorithms for shop scheduling problems with minsum objective” (Journal of Scheduling 2002; 5:287–305) by Queyranne and Sviridenko. This correction provides a correct derivation of its 2eρ approximation result. Wenhua Li and Jinjiang Yuan: Project supported by NNSFC (Grant 10371112) and NSFHN (Grant 0411011200). Maurice Queyranne: Supported by research grants from NSERC, the Natural Sciences and Engineering Research Council of Canada.     

Decremental 2- and 3-connectivity on planar graphs

We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total ofO(n logn) time under any sequence of at mostO(n) deletions. This givesO(logn) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total ofO(n log² n) time. This givesO(log² n) amortized time per deletion. The space required by all our data structures isO(n). All our time bounds improve previous bounds.This work was partially supported by the ESPRIT II Basic Research Actions Program of the EC under Project ALCOM II (contract No. 7141) and Project ASMICS. A preliminary version of this paper appears in [12].Partially supported by a CNR Fellowship. Work done while the author was visiting Columbia University.On leave from IBM T. J. Watson Research Center, Yorktown Heights, NY 10598, USA.