The Fermat star of binary trees

A Fermat point P is one that minimizes the sum δ of the distances between P and the points of a given set. The resulting arrangement, called here a Fermat star, is a particular Steiner tree with only one intermediate point. We extend these concepts to rooted binary trees under the known rotation distance that measures the difference in shape of such trees. Minimizing δ is hard, due to the intrinsic difficulty of computing the rotation distance. Then we limit our study to establishing significant upper bounds for δ. In particular, for m binary trees of n vertices, we show how to construct efficiently a Fermat star with δ?mn−3m, with a technique inherited from the studies on rotation distance.     

Planar tree transformation: Results and counterexample

We consider the problem of planar spanning tree transformation in a two-dimensional plane. Given two planar trees T₁ and T₂ drawn on a set S of n points in general position in the plane, the problem is to transform T₁ into T₂ by a sequence of simple changes called edge-flips or just flips. A flip is an operation by which one edge e of a geometric object is removed and an edge f (f≠e) is inserted such that the resulting object belongs to the same class as the original object. We present two algorithms for planar tree transformations. The first technique is an indirect approach which relies on some ‘canonical’ tree to obtain such transformation results. It is shown that it takes at most 2n−m−s−2 flips (m,s>0) which is an improvement over the result in [D. Avis, K. Fukuda, Reverse search for enumeration, Discrete Applied Mathematics 65 (1996) 21-46]. Second, we present a direct approach which takes at most n−1+k flips (k?0) for such transformation when S in convex position and also show results when the points are in general position. We provide cases where the second technique performs an optimal number of flips. A counterexample is given to show that if |T₁?T₂|=k then they cannot be transformed to one another by k flips.     

Geometric pattern matching for point sets in the plane under similarity transformations

We consider the following geometric pattern matching problem: Given two sets of points in the plane, P and Q, and some (arbitrary) δ>0, find a similarity transformation T (translation, rotation and scale) such that h(T(P),Q)<δ, where h(⋅,⋅) is the directional Hausdorff distance with L_∞ as the underlying metric; or report that none exists. We are only interested in the decision problem, not in minimizing the Hausdorff distance, since in the real world, where our applications come from, δ is determined by the practical uncertainty in the position of the points (pixels). Similarity transformations have not been dealt with in the context of the Hausdorff distance and we fill the gap here. We present efficient algorithms for this problem imposing a reasonable separation restriction on the points in the set Q. If the L_∞ distance between every pair of points in Q is at least 8δ, then the problem can be solved in O(mn²logn) time, where m and n are the numbers of points in P and Q respectively. If the L_∞ distance between every pair of points in Q is at least cδ, for some c, 0<c<1, we present a randomized approximate solution with expected runtime O(n²c−4ε−8log⁴mn), where ε>0 controls the approximation. Our approximation is on the size of the subset, B⊆P, such that h(T(B),Q)<δ and |B|>(1−ε)|P| with high probability.     

Covering Many or Few Points with Unit Disks

Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems. In the first problem we want to place m unit disks, for a given constant m≥1, such that the total weight of the points from P inside the union of the disks is maximized. We present algorithms that compute, for any fixed ε>0, a (1−ε)-approximation to the optimal solution in O(nlog n) time. In the second problem we want to place a single disk with center in a given constant-complexity region X such that the total weight of the points from P inside the disk is minimized. Here we present an algorithm that computes, for any fixed ε>0, in O(nlog ² n) expected time a disk that is, with high probability, a (1+ε)-approximation to the optimal solution. A preliminary version of this work has appeared in Approximation and Online Algorithms—WAOA 2006, LNCS, vol. 4368.     

A discrete geometry approach for dominant point detection

We propose two fast methods for dominant point detection and polygonal representation of noisy and possibly disconnected curves based on a study of the decomposition of the curve into the sequence of maximal blurred segments [2]. Starting from results of discrete geometry [3] and [4], the notion of maximal blurred segment of width ν[2] has been proposed, well adapted to possibly noisy curves. The first method uses a fixed parameter that is the width of considered maximal blurred segments. The second method is deduced from the first one based on a multi-width approach to obtain a non-parametric method that uses no threshold for working with noisy curves. Comparisons with other methods in the literature prove the efficiency of our approach. Thanks to a recent result [5] concerning the construction of the sequence of maximal blurred segments, the complexity of the proposed methods is O(n log n). An application of vectorization is also given in this paper.     

Subsumptive general solutions and parametric general solutions of Post equations

In this paper we generalize Rudeanu’s results from [13] to Post algebras. We give a necessary and sufficient condition for the existence of a Post function f such that the set of solutions of equation f(x) = 0 is a given interval. We also prove that every Post transformation is the parametric solution of some consistent Post equation.     

An optimal approximation algorithm for the rectilinearm-center problem

Given a set ofn points on the plane, the rectilinearm-center problem is to findn rectilinear squares covering all thesen points such that the maximum side length of these squares is minimized. In this paper we prove that there is no polynomial-time algorithm with an error ratio ? < 2 for the rectilinearm-center problem unless NP = P. A polynomial-time approximation algorithm with an error ratio of 2 is also proposed.     

An ideal multi-secret sharing scheme based on MSP

A multi-secret sharing scheme is a protocol to share m arbitrarily related secrets s₁, … , s_m among a set of n participants. In this paper, we propose an ideal linear multi-secret sharing scheme, based on monotone span programs, where each subset of the set of participants may have the associated secret. Our scheme can be used to meet the security requirement in practical applications, such as secure group communication and privacy preserving data mining etc. We also prove that our proposed scheme satisfies the definition of a perfect multi-secret sharing scheme.     

Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix

Given a matrix A∈? ^m×n (n vectors in m dimensions), and a positive integer k<n, we consider the problem of selecting k column vectors from A such that the volume of the parallelepiped they define is maximum over all possible choices. We prove that there exists δ<1 and c>0 such that this problem is not approximable within 2^?ck for k=δn, unless P=NP.     

An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs has attracted many research efforts, mainly due to its interesting structure and its numerous applications, especially in DNA sequence analysis and resource allocation, among others. In one of the most natural generalizations of tolerance graphs, namely multitolerance graphs, two tolerances are allowed for each interval—one from the left and one from the right side of the interval. Then, in its interior part, every interval tolerates the intersection with others by an amount that is a convex combination of its two border-tolerances. In the comparison of DNA sequences between different organisms, the natural interpretation of this model lies on the fact that, in some applications, we may want to treat several parts of the genomic sequences differently. That is, we may want to be more tolerant at some parts of the sequences than at others. These two tolerances for every interval—together with their convex hull—define an infinite number of the so called tolerance-intervals, which make the multitolerance model inconvenient to cope with. In this article we introduce the first non-trivial intersection model for multitolerance graphs, given by objects in the 3-dimensional space called trapezoepipeds. Apart from being important on its own, this new intersection model proves to be a powerful tool for designing efficient algorithms. Given a multitolerance graph with n vertices and m edges along with a multitolerance representation, we present algorithms that compute a minimum coloring and a maximum clique in optimal O(nlogn) time, and a maximum weight independent set in O(m+nlogn) time. Moreover, our results imply an optimal O(nlogn) time algorithm for the maximum weight independent set problem on tolerance graphs, thus closing the complexity gap for this problem. Additionally, by exploiting more the new 3D-intersection model, we completely classify multitolerance graphs in the hierarchy of perfect graphs. The resulting hierarchy of classes of perfect graphs is complete, i.e. all inclusions are strict.     

On Some Proximity Problems of Colored Sets

The maximum diameter color-spanning set problem（MaxDCS） is defined as follows： given n points with m colors, select m points with m distinct colors such that the diameter of the set of chosen points is maximized. In this paper, we design an optimal O（n log n） time algorithm using rotating calipers for MaxDCS in the plane. Our algorithm can also be used to solve the maximum diameter problem of imprecise points modeled as polygons. We also give an optimal algorithm for the all farthest foreign neighbor problem（AFFN） in the plane, and propose algorithms to answer the farthest foreign neighbor query（FFNQ） of colored sets in two- and three-dimensional space. Furthermore, we study the problem of computing the closest pair of color-spanning set（CPCS） in d-dimensional space, and remove the log m factor in the best known time bound if d is a constant.     

On counting pairs of intersecting segments and off-line triangle range searching

We describe a method for decomposing planar sets of segments and points. Using this method we obtain new efficientdeterministic algorithms for counting pairs of intersecting segments, and for answering off-line triangle range queries. In particular we obtain the following results:

1. Givenn segments in the plane, the number of pairs of intersecting segments is counted in timeO(n ^1+?+K ^1/3 n ^2/3+?), whereK is the number of intersection points among the segments, and ?>0 is an arbitrarily small constant.
2. Givenn segments in the plane which are colored with two colors, the number of pairs ofbichromatic intersecting segments is counted in timeO(n ^1+?+K _m ^1/3 n ^2/3+?), whereK _m is the number ofmonochromatic intersection points, and ?>0 is an arbitrarily small constant.
3. Givenn weighted points andn triangles on a plane, the sum of weights of points in each triangle is computed in timeO(n ^1+ε+?^1/3 n ^2/3+ε), where ? is the number of vertices in the arrangement of the triangles, and ?>0 is an arbitrarily small constant.

The above bounds depend sublinearly on the number of intersections among input segmentsK (resp.K _m , ?), which is desirable sinceK (resp.K _m , ?) can range from zero toO(n ²). All of the above algorithms use optimal Θ(n) storage. The constants of proportionality in the big-Oh notation increase as ? decreases. These results are based on properties of the sparse nets introduced by Chazelle [Cha3].     

Clustering Large Graphs via the Singular Value Decomposition

We consider the problem of partitioning a set of m points in the n-dimensional Euclidean space into k clusters (usually m and n are variable, while k is fixed), so as to minimize the sum of squared distances between each point and its cluster center. This formulation is usually the objective of the k-means clustering algorithm (Kanungo et al. (2000)). We prove that this problem in NP-hard even for k = 2, and we consider a continuous relaxation of this discrete problem: find the k-dimensional subspace V that minimizes the sum of squared distances to V of the m points. This relaxation can be solved by computing the Singular Value Decomposition (SVD) of the m × n matrix A that represents the m points; this solution can be used to get a 2-approximation algorithm for the original problem. We then argue that in fact the relaxation provides a generalized clustering which is useful in its own right. Finally, we show that the SVD of a random submatrix—chosen according to a suitable probability distribution—of a given matrix provides an approximation to the SVD of the whole matrix, thus yielding a very fast randomized algorithm. We expect this algorithm to be the main contribution of this paper, since it can be applied to problems of very large size which typically arise in modern applications.     

Quasi-optimal upper bounds for simplex range searching and new zone theorems

This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a setP ofn points in ?^d so that, given any query simplexq, the points inP ∩q can be counted or reported efficiently. Ifm units of storage are available (n <m <n ^d ), then we show that it is possible to answer any query inO(n ^1+?/m ^1/d ) query time afterO(m ^1+?) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieveO(logn) query time at the expense ofO(n ^d+?) storage for any fixed ? > 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.     

Pathwidth of cubic graphs and exact algorithms

We prove that for any ?>0 there exists an integer n? such that the pathwidth of every cubic (or 3-regular) graph on n>n? vertices is at most (1/6+?)n. Based on this bound we improve the worst case time analysis for a number of exact exponential algorithms on graphs of maximum vertex degree three.     

The globally Bi-3-connected property of the honeycomb rectangular torus

The honeycomb rectangular torus is an attractive alternative to existing networks such as mesh-connected networks in parallel and distributed applications because of its low network cost and well-structured connectivity. Assume that m and n are positive even integers with n ? 4. It is known that every honeycomb rectangular torus HReT(m,n) is a 3-regular bipartite graph. We prove that in any HReT(m,n), there exist three internally-disjoint spanning paths joining x and y whenever x and y belong to different partite sets. Moreover, for any pair of vertices x and y in the same partite set, there exists a vertex z in the partite set not containing x and y, such that there exist three internally-disjoint spanning paths of G-{z} joining x and y. Furthermore, for any three vertices x, y, and z of the same partite set there exist three internally-disjoint spanning paths of G-{z} joining x and y if and only if n ? 6 or m = 2.     

Domination number of Cartesian products of directed cycles

Let γ(G) denote the domination number of a digraph G and let Cm□Cn denote the Cartesian product of Cm and Cn, the directed cycles of length m,n?2. In Liu et al. (2010) [11], we determined the exact values of γ(Cm□Cn) when m=2,3,4. In this paper, we give a lower and upper bounds for γ(Cm□Cn). Furthermore, we prove a necessary and sufficient conditions for Cm□Cn to have an efficient dominating set. Also, we determine the exact values: γ(C₅□Cn)=2n; γ(C₆□Cn)=2n if n≡0(mod 3), otherwise, γ(C₆□Cn)=2n+2; if m≡0(mod 3) and n≡0(mod 3).     

On singularities of flat affine systems with n states and n−1 controls

We study the set of intrinsic singularities of flat affine systems with n?1 controls and n states using the notion of Lie‐Bäcklund atlas, previously introduced by the authors. For this purpose, we prove two easily computable sufficient conditions to construct flat outputs as a set of independent first integrals of distributions of vector fields: the first one in a generic case, namely, in a neighborhood of a point where the n?1 control vector fields are independent and the second one at a degenerate point where p?1 control vector fields are dependent of the n?p others, with p>1. After introducing the Γ‐accessibility rank condition, we show that the set of intrinsic singularities includes the set of points where the system does not satisfy this rank condition and is included in the set where a distribution of vector fields introduced in the generic case is singular. We conclude this analysis by three examples of apparent singularities of flat systems in generic and nongeneric degenerate cases.     

On planar path transformation

A flip or edge-replacement is considered as a transformation by which one edge e of a geometric object is removed and an edge f (f≠e) is inserted such that the resulting object belongs to the same class as the original object. Here, we consider Hamiltonian planar paths as geometric objects. A technique is presented for transforming a given planar path into another one for a set S of n points in convex position in the plane. Under these conditions, we show that any planar path can be transformed into another planar path by at most 2n−5 flips. For the case when the points are in general position we provide experimental results regarding transformability of any planar path into another. We show that for n?8 points in general position any two paths can be transformed into each other. For n points in convex position we show that there are n²n−2 directed Hamiltonian planar paths. An algorithm is presented which uses flips of size 1 and flips of size 2 to generate all such paths with O(n) time between the generation of two successive paths.     

Approximation and inapproximability results for maximum clique of disc graphs in high dimensions

We prove algorithmic and hardness results for the problem of finding the largest set of a fixed diameter in the Euclidean space. In particular, we prove that if A^∗ is the largest subset of diameter r of n points in the Euclidean space, then for every ε>0 there exists a polynomial time algorithm that outputs a set B of size at least |A^∗| and of diameter at most . On the hardness side, roughly speaking, we show that unless P=NP for every ε>0 it is not possible to guarantee the diameter for B even if the algorithm is allowed to output a set of size .