Geometric applications of posets

We show the power of posets in computational geometry by solving several problems posed on a set S of n points in the plane: (1) find the n − k − 1 rectilinear farthest neighbors (or, equivalently, k nearest neighbors) to every point of S (extendable to higher dimensions), (2) enumerate the k largest (smallest) rectilinear distances in decreasing (increasing) order among the points of S, (3) given a distance δ > 0, report all the pairs of points that belong to S and are of rectilinear distance δ or more (less), covering k ≥ n/2 points of S by rectilinear (4) and circular (5) concentric rings, and (6) given a number k ≥ n/2 decide whether a query rectangle contains k points or less.     

On the multisearching problem for hypercubes

In this paper we give improved bounds for the multisearch problem on a hypercube. This is a parallel search problem where the elements in the structure S to be searched are totally ordered, but where it is not possible to compare in constant time any two given queries q and q′. More precisely, we are given on a n-processor hypercube a sorted n-element sequence S, and a set Q of n queries, and we need to find for each query q Q its location in the sorted S. We present an improved algorithm for the multisearch problem, one that takes O(log n(log log n)³) time on a n-processor hypercube. This problem is fundamental in computational geometry, for example it models planar point location in a slab. We give as application a trapezoidal decomposition algorithm with the same time complexity on a n log n-processor hypercube. The hypercube model for which we claim our bounds is the standard one, SIMD, with O(1) memory registers per processor, and with one-port communication. Each register can store O(log n) bits, so that a processor knows its ID.     

Efficient text fingerprinting via Parikh mapping

We consider the problem of fingerprinting text by sets of symbols. Specifically, if S is a string, of length n, over a finite, ordered alphabet Σ, and S′ is a substring of S, then the fingerprint of S′ is the subset φ of Σ of precisely the symbols appearing in S′. In this paper we show efficient methods of answering various queries on fingerprint statistics. Our preprocessing is done in time O(n|Σ|lognlog|Σ|) and enables answering the following queries:

(1)Given an integer k, compute the number of distinct fingerprints of size k in time O(1).

(2)Given a set φΣ, compute the total number of distinct occurrences in S of substrings with fingerprint φ in time O(|Σ|logn).

     

On the generalized Erdös-Szekeres Conjecture — a new upper bound

We prove the following result: For every two natural numbers n and q, n q + 2, there is a natural number E(n, q) satisfying the following:

1. (1) Let S be any set of points in the plane, no three on a line. If |S| E(n, q), then there exists a convex n-gon whose points belong to S, for which the number of points of S in its interior is 0 (mod q).

2. (2) For fixed q, E(n,q) 2^c(q)·n, c(q) is a constant depends on q only.

Part (1) was proved by Bialostocki et al. [2] and our proof is aimed to simplify the original proof. The proof of Part (2) is completely new and reduces the huge upper bound of [2] (a super-exponential bound) to an exponential upper bound.     

The greedy triangulation can be computed from the Delaunay triangulation in linear time

The greedy triangulation of a finite planar point set is obtained by repeatedly inserting a shortest diagonal that does not cross those already in the plane. The Delaunay triangulation, which is the straight-line dual of the Voronoi diagram, can be produced in O(nlogn) worst-case time, and often even faster, by several practical algorithms. In this paper we show that for any planar point set S, if the Delaunay triangulation of S is given, then the greedy triangulation of S can be computed in linear worst-case time (and linear space).     

A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree

Given an edge-weighted tree T and an integer p1, the minmax p-traveling salesmen problem on a tree T asks to find p tours such that the union of the p tours covers all the vertices. The objective is to minimize the maximum of length of the p tours. It is known that the problem is NP-hard and has a (2−2/(p+1))-approximation algorithm which runs in O(p^p−1n^p−1) time for a tree with n vertices. In this paper, we consider an extension of the problem in which the set of vertices to be covered now can be chosen as a subset S of vertices and weights to process vertices in S are also introduced in the tour length. For the problem, we give an approximation algorithm that has the same performance guarantee, but runs in O((p−1)!·n) time.     

Hamiltonian cycles in n-factor-critical graphs

A graph G is said to be n-factor-critical if G−S has a 1-factor for any SV(G) with |S|=n. In this paper, we prove that if G is a 2-connected n-factor-critical graph of order p with , then G is hamiltonian with some exceptions. To extend this theorem, we define a (k,n)-factor-critical graph to be a graph G such that G−S has a k-factor for any SV(G) with |S|=n. We conjecture that if G is a 2-connected (k,n)-factor-critical graph of order p with , then G is hamiltonian with some exceptions. In this paper, we characterize all such graphs that satisfy the assumption, but are not 1-tough. Using this, we verify the conjecture for k2.     

On embedding an outer-planar graph in a point set

Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(nlog³n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [8,12] that requires O(n²) time. Our algorithm is near-optimal as there is an Ω(nlogn) lower bound for the problem [4]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where lognd2n is the length of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(nlogn) and O(n²) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal Θ(nlogn) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.     

Some Ore-type Results for Matching and Perfect Matching in <Emphasis Type="Italic">k</Emphasis>-uniform Hypergraphs

Let S₁ and S₂ be two (k-1)-subsets in a k-uniform hypergraph H. We call S₁ and S₂ strongly or middle or weakly independent if H does not contain an edge e ∈ E(H) such that S₁ ∩ e ≠∅ and S₂ ∩ e ≠∅ or e ⊆ S₁ ∪ S₂ or e ⊇ S₁ ∪ S₂, respectively. In this paper, we obtain the following results concerning these three independence. (1) For any n ≥ 2k²-k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent (k-1)-sets equal to 2n-4(k-1), contains no perfect matching; (2) Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd+(k-2)k. If the degree sum of any two middle independent (k-1)-subsets is larger than 2(d-1), then H contains a d-matching; (3) For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent (k-1)-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n.     

On counting triangulations in d dimensions

Given a set of n labeled points on S^d, how many combinatorially different geometric triangulations for this point set are there? We show that the logarithm of this number is at most some positive constant times n^d/2+1. Evidence is provided that for even dimensions d the bound can be improved to some constant times n^d/2.     

Approximating geometric bottleneck shortest paths

In a geometric bottleneck shortest path problem, we are given a set S of n points in the plane, and want to answer queries of the following type: given two points p and q of S and a real number L, compute (or approximate) a shortest path between p and q in the subgraph of the complete graph on S consisting of all edges whose lengths are less than or equal to L. We present efficient algorithms for answering several query problems of this type. Our solutions are based on Euclidean minimum spanning trees, spanners, and the Delaunay triangulation. A result of independent interest is the following. For any two points p and q of S, there is a path between p and q in the Delaunay triangulation, whose length is less than or equal to 2π/(3cos(π/6)) times the Euclidean distance |pq| between p and q, and all of whose edges have length at most |pq|.     

Triangular range counting query in 2D and its application in finding k nearest neighbors of a line segment

We present an efficient algorithm for finding k nearest neighbors of a query line segment among a set of points distributed arbitrarily on a two dimensional plane. Along the way to finding this algorithm, we have obtained an improved triangular range searching technique in 2D. Given a set of n points, we preprocess them to create a data structure using O(n²) time and space, such that given a triangular query region Δ, the number of points inside Δ can be reported in O(logn) time. Finally, this triangular range counting technique is used for finding k nearest neighbors of a query straight line segment in O(log²n+k) time.     

Combinatorial theorems on contractive mappings in power sets

We prove that to every positive integer n there exists a positive integer h such that the following holds: If S is a set of h elements and ƒ a mapping of the power set of S into such that ƒ(T)T for all T , then there exists a strictly increasing sequence T₁T_n of subsets of S such that one of the following three possibilities holds: (a) all sets ƒ(T_i), i= 1,…,n, are equal; (b) for all i=1,…, n, we have ƒ(T_i)=T_i; (c) T_i=ƒ(T_i+1) for all i= 1,…,n-1. This theorem generalizes theorems of the author, Rado, and Leeb. It has applications for subtrees in power sets.     

Sequences with idempotent products from finite regular semigroups

We find the smallest integer (n) such that for every regular semigroup S of order n, every sequence of length (n) of elements of S contains a consecutive subsequence whose product is an -element, where = ‘idempotent’, ‘core’ and ‘subgroup and core’. For arbitrary semigroups of order n, we also find (n) where = ‘regular’, ‘group’, ‘core’, ‘regular and core’ and ‘subgroup and core’.     

An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model

In this paper, we present a direct approach for routing a shortest rectilinear path between two points among a set of rectilinear obstacles in a two-layer interconnection model that is used for VLSI routing applications. The previously best known direct approach for this problem takes O(nlog²n) time and O(nlogn) space, where n is the total number of obstacle edges. By using integer data structures and an implicit graph representation scheme (i.e., a generalization of the distance table method), we improve the time bound to O(nlog^3/2n) while still maintaining the O(nlogn) space bound. Comparing with the indirect approach for this problem, our algorithm is simpler to implement and is probably faster for a quite large range of input sizes.     

A note on minimum degree conditions for supereulerian graphs

A graph is called supereulerian if it has a spanning closed trail. Let G be a 2-edge-connected graph of order n such that each minimal edge cut SE(G) with |S|3 satisfies the property that each component of G−S has order at least (n−2)/5. We prove that either G is supereulerian or G belongs to one of two classes of exceptional graphs. Our results slightly improve earlier results of Catlin and Li. Furthermore, our main result implies the following strengthening of a theorem of Lai within the class of graphs with minimum degree δ4: If G is a 2-edge-connected graph of order n with δ(G)4 such that for every edge xyE(G) , we have max{d(x),d(y)}(n−2)/5−1, then either G is supereulerian or G belongs to one of two classes of exceptional graphs. We show that the condition δ(G)4 cannot be relaxed.     

On the structure of a random sum-free set of positive integers

Cameron introduced a natural probability measure on the set of sum-free sets, and asked which sets of sum-free sets have a positive probability of occurring in this probability measure. He showed that the set of subsets of the odd numbers has a positive probability, and that the set of subsets of any sum-free set corresponding to a complete modular sum-free set also has a positive probability of occurring. In this paper we consider, for every sum-free set S, the representation function r_s(n), and show that if r_s(n) grows sufficiently quickly then the set of subsets of S has positive probability, and conversely, that if r_s(n) has a sub-sequence with suitably slow growth, then the set of subsets of S has probability zero. The results include those of Cameron mentioned above as particular cases.     

Multiplicative properties of generalized matrix functions

We consider scalar-valued matrix functions for n×n matrices A=(a_ij) defined by Where G is a subgroup of S_n the group of permutations on n letters, and χ is a linear character of G. Two such functions are the permanent and the determinant. A function (1) is multiplicative on a semigroup S of n×n matrices if d(AB)=d(A)d(B) AB∈S.

With mild restrictions on the underlying scalar ring we show that every element of a semigroup containing the diagonal matrices on which (1) is multiplicative can have at most one nonzero diagonal(i.e., diagonal with all nonzero entries)and conversely, provided that χ is the principal character(χ≡1).     

The countability index of the endomorphism semigroup of a vector space

The countability index C(S) of a semigroup S is the least positive integer n, if such an integer exists, with the property that every countable subset of S is contained in a subsemigroup with n generators. If no such integer exists. C(S) is defined to be infinite. Let V be a vector space over a field F and denote by End V the endomorphism semigroup of V. In the two main results, it is determined precisely when C(End V)=2 and when C(End V)=x SpecificallyC(End V)=2 if and only if V is infinite dimensional or dim V=1 and F is finite and C(End V)=x if and only if F is infinite and dim V is an integer N≥1.     

Harary's conjectures on integral sum graphs

Let N denote the set of positive integers and Z denote all integers. The (integral) sum graph of a finite subset S N(Z) is the graph (S, E) with uv ε E if and only if u + v ε S. A graph G is said to be an (integral) sum graph if it is isomorphic to the (integral) sum graph of some S N(Z). The (integral) sum number of a given graph G is the smallest number of isolated nodes which when added to G result in an (integral) sum graph.

We show that the integral sum number of a complete graph with n 4 nodes equals 2n − 3, which proves a conjecture of Harary. And we disprove another conjecture of Harary by showing that there are infinitely many trees which are not caterpillars but are integral sum graphs.