Proximity problems on line segments spanned by points

Finding the closest or farthest line segment (line) from a point are fundamental proximity problems. Given a set S of n points in the plane and another point q, we present optimal O(nlogn) time, O(n) space algorithms for finding the closest and farthest line segments (lines) from q among those spanned by the points in S. We further show how to apply our techniques to find the minimum (maximum) area triangle with a vertex at q and the other two vertices in S{q} in optimal O(nlogn) time and O(n) space. Finally, we give an O(nlogn) time, O(n) space algorithm to find the kth closest line from q and show how to find the k closest lines from q in O(nlogn+k) time and O(n+k) space.     

The total chromatic number of regular graphs of even order and high degree

The total chromatic number χ_T(G) of a graph G is the minimum number of colours needed to colour the edges and the vertices of G so that incident or adjacent elements have distinct colours. We show that if G is a regular graph of even order and , thenχ_T(G)Δ(G)+2.     

Ore-type degree condition for heavy paths in weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number w(e), called the weight of e. For a vertex v of a weighted graph, d^w(v) is the sum of the weights of the edges incident to v. And the weight of a path is the sum of the weights of the edges belonging to it. In this paper, we give a sufficient condition for a weighted graph to have a heavy path which joins two specified vertices. Let G be a 2-connected weighted graph and let x and y be distinct vertices of G. Suppose that d^w(u)+d^w(v)2d for every pair of non-adjacent vertices u and vV(G) x,y . Then x and y are joined by a path of weight at least d, or they are joined by a Hamilton path. Also, we consider the case when G has some vertices whose weighted degree are not assumed.     

Sparse geometric graphs with small dilation

Given a set S of n points in , and an integer k such that 0k<n, we show that a geometric graph with vertex set S, at most n−1+k edges, maximum degree five, and dilation O(n/(k+1)) can be computed in time O(nlogn). For any k, we also construct planar n-point sets for which any geometric graph with n−1+k edges has dilation Ω(n/(k+1)); a slightly weaker statement holds if the points of S are required to be in convex position.     

Covering point sets with two disjoint disks or squares

We study the following problem: Given a set of red points and a set of blue points on the plane, find two unit disks C_R and C_B with disjoint interiors such that the number of red points covered by C_R plus the number of blue points covered by C_B is maximized. We give an algorithm to solve this problem in O(n^8/3log²n) time, where n denotes the total number of points. We also show that the analogous problem of finding two axis-aligned unit squares S_R and S_B instead of unit disks can be solved in O(nlogn) time, which is optimal. If we do not restrict ourselves to axis-aligned squares, but require that both squares have a common orientation, we give a solution using O(n³logn) time.     

On partitioning two matroids into common independent subsets

Let M₁ and M₂ be two matroids on the same ground set S. We conjecture that if there do not exist disjoint subsets A₁,A₂,…,A_k+1 of S, such that _isp_M1(A_i)≠Ø, and similarly for M₂, then S is partitioned into k sets, each independent in both M₁ and M₂. This is a possible generalization of König's edge-coloring theorem. We prove the conjecture for the case k=2 and for a regular case, in which both matroids have the same rank d, and S consists of k·d elements. Finally, we prove another special case related to a conjecture of Rota.     

On relations between 1-lines of Adams–Novikov spectral sequences modulo invariant prime ideals

We have a ring homomorphism Θ from the cohomology of the extended Morava stabilizer group G_n with coefficients in F[w^±1] to the cohomology of G_n+1 with coefficients in the graded field F((u_n))[u^±1]. In this note we study the behavior of Θ on H¹. Then it is shown that Θ is injective on H¹ for n1 and for all primes p.     

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.     

Chromatic numbers and products

Let f(n) be the smallest number so that there are two n chromatic graphs whose product has chromatic number f(n). Under the assumption that a certain sharper result than one obtained by Duffus et al. [On the chromatic number of the product of graphs, J. Graph Theory 9 (1985) 487–495], and Welzl [Symmetric graphs and interpretations, J. Combin. Theory, Sci. B 37 (1984) 235–244], holds we will prove that f(n)n/2.     

An algorithm for calculating the independence and vertex-cover polynomials of a graph

The independence polynomial, ω(G,x)=∑w_kx^k, of a graph, G, has coefficients, w_k, that enumerate the ways of selecting k vertices from G so that no two selected vertices share an edge. The independence number of G is the largest value of k for which w_k≠0. Little is known of less straightforward relationships between graph structure and the properties of ω(G,x), in part because of the difficulty of calculating values of w_k for specific graphs. This study presents a new algorithm for these calculations which is both faster than existing ones and easily adaptable to high-level computer languages.     

Cauchy–Riemann equations and J-symplectic forms

Let (Σ,j) be a Riemann surface. The almost complex manifolds (M,J) for which the J-holomorphic curves :Σ→M are of variational type, are characterized. This problem is related to the existence of a vertically non-degenerate closed complex 3-form on Σ×M (see Theorem 4.3 below), which determines a family of J-symplectic structures on (M,J) parametrized by Σ.     

Edge-coloring of multigraphs

We introduce a monotone invariant π(G) on graphs and show that it is an upper bound of the chromatic index of graphs. Moreover, there exist polynomial time algorithms for computing π(G) and for coloring edges of a multigraph G by π(G) colors. This generalizes the classical edge-coloring theorems of Shannon and Vizing.     

Extracting approximate patterns

In this paper, we define a family of patterns with don't cares occurring in a text. We call them primitive patterns. The set of primitive patterns forms a basis for all the maximal patterns occurring in the text. The number of primitive patterns is smaller than other known basis.

We present an incremental algorithm that computes the primitive patterns occurring at least q times in a text of length n, given the N primitive patterns occurring at least q−1 times, in time O(|Σ|Nn²logn), where Σ is the alphabet. In the particular case where q=2, the complexity in time is only O(|Σ|n²logn). We also give an algorithm that decides if a given pattern is primitive in a given text. These algorithms are generalized, taking many sequences in input. Finally, we give a solution for reducing the number of patterns of interest by using scoring techniques, as we show that the number of primitive patterns is exponential.     

Searching with lies under error cost constraints

The Rényi–Berlekamp–Ulam game is a classical model for the problem of determining the minimum number of queries to find an unknown member in a finite set when up to a finite number of the answers may be erroneous. In the variant considered in this paper, questions with q many possible answers are allowed, further lies are constrained by a bipartite graph with edges weighted by 0,1,2,… (the “channel”). The channel Γ is an arbitrary assignment stipulating the cost of the different possible lies, i.e., of each answer j≠i when the correct answer is i by Γ(i,j). It is also assumed that a maximum cost e (sum of the cost of all wrong answers) can be afforded by the responder during the whole game. We provide tight asymptotic bounds for the number of questions needed to solve this problem. The appropriate searching strategies are actually provided. We also show that adaptiveness can be dramatically reduced when the channel satisfies certain symmetry constraints.     

Characterizations of some classes of relatively regular operators

A bounded linear operator A on a Banach space is called relatively regular, if there is a bounded linear operator B such that ABA=A. In this case B is called a g₁-inverse of A. In this paper we characterize some classes of relatively regular operators A via the set {B₁-B₂:B₁ and B₂ are g₁-inverses of A}.     

Hyperasymptotic evaluation of the Pearcey integral via Hadamard expansions

We describe high-precision computations of the Pearcey integral Pe(x,y) for real x and y by means of Hadamard expansions. Numerical results for (x,y) situated in different regions of the x,y-plane are given to illustrate the levels of precision that can be achieved. Particular emphasis is given to computation in the neighbourhood of the two cusped curves associated with Pe(x,y) across which there is either a coalescence of saddles or a Stokes phenomenon.     

On four color monochromatic sets with nondecreasing diameter

Let m and r be positive integers. Define f(m,r) to be the least positive integer N such that for every coloring of the integers 1,…,N with r colors there exist monochromatic subsets B₁ and B₂ (not necessarily of the same color), each having m elements, such that (a) max(B₁)-min(B₁)max(B₂)-min(B₂), and (b) max(B₁)B₂). We improve previous upper bounds to determine that f(m,4)=12m-9.     

Visibility maps of segments and triangles in 3D

Let T be a set of n triangles in three-dimensional space, let s be a line segment, and let t be a triangle, both disjoint from T. We consider the subdivision of T based on (in)visibility from s; this is the visibility map of the segment s with respect to T. The visibility map of the triangle t is defined analogously. We look at two different notions of visibility: strong (complete) visibility, and weak (partial) visibility. The trivial Ω(n²) lower bound for the combinatorial complexity of the strong visibility map of both s and t is almost tight: we prove an O(n²(n)) upper bound for both structures, where (n) is the extremely slowly increasing inverse Ackermann function. Furthermore, we prove that the weak visibility map of s has complexity Θ(n⁵), and the weak visibility map of t has complexity Θ(n⁷). If T is a polyhedral terrain, the complexity of the weak visibility map is Ω(n⁴) and O(n⁵), both for a segment and a triangle. We also present efficient algorithms to compute all discussed structures.     

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.     

On association schemes all elements of which have valency 1 or 2

In the present note, we investigate schemes S in which each element s satisfies n_s2 and n_s^*s≠2. We show that such a scheme is schurian. More precisely, we show that it is isomorphic to G//t, where G is a finite group and t an involution of G weakly closed in C_G(t).

Groups G with an involution t weakly closed in C_G(t) have been described in Glauberman's Z^*-Theorem [G. Glauberman, Central elements in core-free groups, J. Algebra 4 (1966) 403–420] with the help of the largest normal subgroup of G having odd order.