Area-preserving approximations of polygonal paths

Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P let W_A(Q) be the area above P and below Q, and let W_B(Q) be the area above Q and below P. Given P and an integer k, we show how to compute a path Q with at most k edges that minimizes W_A(Q)+W_B(Q). Given P and a cost C, we show how to find a path Q with the smallest possible number of edges such that W_A(Q)+W_B(Q)C. However, given P, an integer k, and a cost C, it is NP-hard to determine if a path Q with at most k edges exists such that max{W_A(Q),W_B(Q)}C. We describe an approximation algorithm for this setting. Finally, it is also NP-hard to decide whether a path Q exists such that |W_A(Q)−W_B(Q)|=0. Nevertheless, in this error measure we provide an algorithm for computing an optimal approximation up to an additive error.     

The minimum Manhattan network problem: Approximations and exact solutions

Given a set of points in the plane and a constant t1, a Euclidean t-spanner is a network in which, for any pair of points, the ratio of the network distance and the Euclidean distance of the two points is at most t. Such networks have applications in transportation or communication network design and have been studied extensively.

In this paper we study 1-spanners under the Manhattan (or L₁-) metric. Such networks are called Manhattan networks. A Manhattan network for a set of points is a set of axis-parallel line segments whose union contains an x- and y-monotone path for each pair of points. It is not known whether it is NP-hard to compute minimum Manhattan networks (MMN), i.e., Manhattan networks of minimum total length. In this paper we present an approximation algorithm for this problem. Given a set P of n points, our algorithm computes in O(nlogn) time and linear space a Manhattan network for P whose length is at most 3 times the length of an MMN of P.

We also establish a mixed-integer programming formulation for the MMN problem. With its help we extensively investigate the performance of our factor-3 approximation algorithm on random point sets.     

A loop-free two-close Gray-code algorithm for listing k-ary Dyck words

P. Chase and F. Ruskey each published a Gray code for length n binary strings with m occurrences of 1, coding m-combinations of n objects, which is two-close—that is, in passing from one binary string to its successor a single 1 exchanges positions with a 0 which is either adjacent to the 1 or separated from it by a single 0. If we impose the restriction that any suffix of a string contains at least k−1 times as many 0's as 1's, we obtain k-suffixes: suffixes of k-ary Dyck words. Combinations are retrieved as special case by setting k=1 and k-ary Dyck words are retrieved as a special case by imposing the additional condition that the entire string has exactly k−1 times as many 0's as 1's. We generalize Ruskey's Gray code to the first two-close Gray code for k-suffixes and we provide a loop-free implementation for k2. For k=1 we use a simplified version of Chase's loop-free algorithm for generating his two-close Gray code for combinations. These results are optimal in the sense that there does not always exist a Gray code, either for combinations or Dyck words, in which the 1 and the 0 that exchange positions are adjacent.     

Line-segment intersection made in-place

We present a space-efficient algorithm for reporting all k intersections induced by a set of n line segments in the plane. Our algorithm is an in-place variant of Balaban's algorithm and, in the worst case, runs in time using extra words of memory in addition to the space used for the input to the algorithm.     

The minimum weight triangulation problem with few inner points

We look at the computational complexity of 2-dimensional geometric optimization problems on a finite point set with respect to the number of inner points (that is, points in the interior of the convex hull). As a case study, we consider the minimum weight triangulation problem. Finding a minimum weight triangulation for a set of n points in the plane is not known to be NP-hard nor solvable in polynomial time, but when the points are in convex position, the problem can be solved in O(n³) time by dynamic programming. We extend the dynamic programming approach to the general problem and describe an exact algorithm which runs in O(6^kn⁵logn) time where n is the total number of input points and k is the number of inner points. If k is taken as a parameter, this is a fixed-parameter algorithm. It also shows that the problem can be solved in polynomial time if k=O(logn). In fact, the algorithm works not only for convex polygons, but also for simple polygons with k inner points.     

Bit-parallel approximate string matching algorithms with transposition

Using bit-parallelism has resulted in fast and practical algorithms for approximate string matching under Levenshtein edit distance, which permits a single edit operation to insert, delete or substitute a character. Depending on the parameters of the search, currently the fastest non-filtering algorithms in practice are the O(km/wn) algorithm of Wu and Manber, the O((k+2)(m−k)/wn) algorithm of Baeza-Yates and Navarro, and the O(m/wn) algorithm of Myers, where m is the pattern length, n is the text length, k is the error threshold and w is the computer word size. In this paper we discuss a uniform way of modifying each of these algorithms to permit also a fourth type of edit operation: transposing two adjacent characters in the pattern. This type of edit distance is also known as Damerau edit distance. In the end we also present an experimental comparison of the resulting algorithms.     

An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality

We consider the asymmetric traveling salesperson problem with γ-parameterized triangle inequality for γ[1/2,1). That means, the edge weights fulfill w(u,v)γ(w(u,x)+w(x,v)) for all nodes u,v,x. Chandran and Ram [L.S. Chandran, L.S. Ram, Approximations for ATSP with parametrized triangle inequality, in: Proc. 19th Int. Symp. on Theoret. Aspects of Comput. Sci. (STACS), in: Lecture Notes in Comput. Sci., vol. 2285, Springer, Berlin, 2002, pp. 227–237] gave the first constant factor approximation algorithm with polynomial running time for this problem. They achieve performance ratio γ/(1−γ). We devise an approximation algorithm with performance ratio (1+γ)/(2−γ−γ³), which is better for γ[0.5437,1), that is, for the particularly interesting large values of γ.     

Minimum weight pseudo-triangulations

We consider the problem of computing a minimum weight pseudo-triangulation of a set of n points in the plane. We first present an -time algorithm that produces a pseudo-triangulation of weight which is shown to be asymptotically worst-case optimal, i.e., there exists a point set for which every pseudo-triangulation has weight , where is the weight of a minimum weight spanning tree of . We also present a constant factor approximation algorithm running in cubic time. In the process we give an algorithm that produces a minimum weight pseudo-triangulation of a simple polygon.     

Computing homotopic shortest paths efficiently

We give deterministic and randomized algorithms to find shortest paths homotopic to a given collection Π of disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time , and the randomized algorithm runs in expected time O(k_out+k_inlogn+n(logn)^1+ε). Here k_in is the number of edges in all the paths of Π, and k_out is the number of edges in the output paths.     

A note on approximation of a ball by polytopes

We study properties of polytopes circumscribed by a unit sphere in Rⁿ with either m extreme points or m facets. We show that if one measures the quality of approximation using the radius of an inscribing sphere then asymptotically the best-possible results are the same for both cases. Somewhat surprisingly, however, the volume can grow substantially faster in m for the case where the polytope has m facets.     

Error analysis of a Collocation method for numerically inverting a Laplace transform in case of real samples

In [S. Cuomo, L. D’Amore, A. Murli, M.R. Rizzardi, Computation of the inverse Laplace transform based on a collocation method which uses only real values, J. Comput. Appl. Math., 198 (1) (2007) 98–115] the authors proposed a Collocation method (C-method) for real inversion of Laplace transforms (Lt), based on the truncated Laguerre expansion of the inverse function:

where σ, b are parameters and c_k, kN, are the MacLaurin coefficients of a function depending on the Lt. The computational kernel of a C-method is the solution of a Vandermonde linear system, where the right hand side is obtained evaluating the Lt on the real axis. The Bjorck Pereira algorithm has been used for solving the Vandermonde linear system, providing a computable componentwise error bound on the solution.

For an inversion problem on discrete data F is known on a pre-assigned set of points (we refer to these points as samples of F) only and the major challenge is to deal with a significative loss of information. A natural approach to overcome this intrinsic difficulty is to construct a suitable fitting model that approximates the given data. In this case, we show that such approach leads to a C-method with perturbed right hand side, and then we use again the Bjorck Pereira algorithm.

Starting from the error introduced by the fitting model, we study its propagation in order to determine the maximum attainable accuracy on f_N. Moreover we derive a computable error bound that allows to get the suitable value of the parameter N that gives the maximum attainable accuracy.     

Space-efficient geometric divide-and-conquer algorithms

We develop a number of space-efficient tools including an approach to simulate divide-and-conquer space-efficiently, stably selecting and unselecting a subset from a sorted set, and computing the kth smallest element in one dimension from a multi-dimensional set that is sorted in another dimension. We then apply these tools to solve several geometric problems that have solutions using some form of divide-and-conquer. Specifically, we present a deterministic algorithm running in time using extra memory given inputs of size n for the closest pair problem and a randomized solution running in expected time and using extra space for the bichromatic closest pair problem. For the orthogonal line segment intersection problem, we solve the problem in time using extra space where n is the number of horizontal and vertical line segments and k is the number of intersections.     

An atlas for tridiagonal isospectral manifolds

Let be the compact manifold of real symmetric tridiagonal matrices conjugate to a given diagonal matrix Λ with simple spectrum. We introduce bidiagonal coordinates, charts defined on open dense domains forming an explicit atlas for . In contrast to the standard inverse variables, consisting of eigenvalues and norming constants, every matrix in now lies in the interior of some chart domain. We provide examples of the convenience of these new coordinates for the study of asymptotics of isospectral dynamics, both for continuous and discrete time.     

On the Fermat–Weber center of a convex object

We show that for any convex object Q in the plane, the average distance from the Fermat–Weber center of Q to the points in Q is at least Δ(Q)/7, where Δ(Q) is the diameter of Q, and that there exists a convex object P for which this distance is Δ(P)/6. We use this result to obtain a linear-time approximation scheme for finding an approximate Fermat–Weber center of a convex polygon Q.     

Exact algorithms and applications for Tree-like Weighted Set Cover

We introduce an NP-complete special case of the Weighted Set Cover problem and show its fixed-parameter tractability with respect to the maximum subset size, a parameter that appears to be small in relevant applications. More precisely, in this practically relevant variant we require that the given collection C of subsets of a base set S should be “tree-like”. That is, the subsets in C can be organized in a tree T such that every subset one-to-one corresponds to a tree node and, for each element s of S, the nodes corresponding to the subsets containing s induce a subtree of T. This is equivalent to the problem of finding a minimum edge cover in an edge-weighted acyclic hypergraph. Our main result is an algorithm running in O(3^kmn) time where k denotes the maximum subset size, n:=|S|, and m:=|C|. The algorithm also implies a fixed-parameter tractability result for the NP-complete Multicut in Trees problem, complementing previous approximation results. Our results find applications in computational biology in phylogenomics and for saving memory in tree decomposition based graph algorithms.     

On finding widest empty curved corridors

An -siphon of width w is the locus of points in the plane that are at the same distance w from a 1-corner polygonal chain C such that is the interior angle of C. Given a set P of n points in the plane and a fixed angle , we want to compute the widest empty -siphon that splits P into two non-empty sets. We present an efficient O(nlog³n)-time algorithm for computing the widest oriented -siphon through P such that the orientation of a half-line of C is known. We also propose an O(n³log²n)-time algorithm for the widest arbitrarily-oriented version and an Θ(nlogn)-time algorithm for the widest arbitrarily-oriented -siphon anchored at a given point.     

A combinatorial approach to doubly transitive permutation groups

Let G be a doubly but not triply transitive group on a set X. We give an algorithm to construct the orbits of G acting on X×X×X by combining those of its stabilizer H of a point of X If the group H is given first, we compute the orbits of its transitive extension G, if it exists. We apply our algorithm to G=PSL(m,q) and Sp(2m,2), m3, successfully. We go forward to compute the transitive extension of G itself. In our construction we use a superscheme defined by the orbits of H on X×X×X and do not use group elements.     

Nonlinear maps preserving Lie products on factor von Neumann algebras

In this paper, we prove that every bijective map preserving Lie products from a factor von Neumann algebra into another factor von Neumann algebra is of the form A→ψ(A)+ξ(A), where is an additive isomorphism or the negative of an additive anti-isomorphism and is a map with ξ(AB-BA)=0 for all .     

Optimal domain decomposition via -median methodology using ACO and hybrid ACGA

In this paper an efficient method is developed for decomposing large-scale finite element meshes. A weighted incidence graph is used to transform the connectivity properties of finite element models into those of graphs. A graph G_c of manageable size is obtained from the main graph model by a coarsening algorithm. The p-medians of this graph are selected using two approaches. The first algorithm uses an ant colony optimization and the second algorithm employs a hybrid ant colony together with genetic algorithm. Here, p is the number of subdomains which the finite element meshes is intended to be decomposed. Once the medians are obtained, the nodes in G_c associated with each median are selected. In an expansion process, the nodes of the subdomains in G are obtained. The capabilities of both ant colony optimization, and hybrid ant colony and genetic algorithm are evaluated using many examples of different topology.     

Uniform asymptotic expansions of the Pollaczek polynomials

Two uniform asymptotic expansions are obtained for the Pollaczek polynomials P_n(cosθ;a,b). One is for , , in terms of elementary functions and in descending powers of . The other is for , in terms of a special function closely related to the modified parabolic cylinder functions, in descending powers of n. This interval contains a turning point and all possible zeros of P_n(cosθ) in θ(0,π/2].