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.     

The minimum-area spanning tree problem

Motivated by optimization problems in sensor coverage, we formulate and study the Minimum-Area Spanning Tree (mast) problem: Given a set of n points in the plane, find a spanning tree of of minimum “area”, where the area of a spanning tree is the area of the union of the n−1 disks whose diameters are the edges in . We prove that the Euclidean minimum spanning tree of is a constant-factor approximation for mast. We then apply this result to obtain constant-factor approximations for the Minimum-Area Range Assignment (mara) problem, for the Minimum-Area Connected Disk Graph (macdg) problem, and for the Minimum-Area Tour (mat) problem. The first problem is a variant of the power assignment problem in radio networks, the second problem is a related natural problem, and the third problem is a variant of the traveling salesman problem.     

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 quadratic distance bound on sliding between crossing-free spanning trees

Let S be a set of n points in the plane and let be the set of all crossing-free spanning trees of S. We show that it is possible to transform any two trees in into each other by O(n²) local and constant-size edge slide operations. Previously no polynomial upper bound for this task was known, but in [O. Aichholzer, F. Aurenhammer, F. Hurtado, Sequences of spanning trees and a fixed tree theorem, Comput. Geom.: Theory Appl. 21 (1–2) (2002) 3–20] a bound of O(n²logn) operations was conjectured.     

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.     

Computing the Fréchet distance between piecewise smooth curves

We consider the Fréchet distance between two curves which are given as a sequence of m+n curved pieces. If these pieces are sufficiently well-behaved, we can compute the Fréchet distance in O(mnlog(mn)) time. The decision version of the problem can be solved in O(mn) time. The results are based on an analysis of the possible intersection patterns between circles and arcs of bounded curvature.     

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.     

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.     

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].     

On periodic radical groups in which permutability is a transitive relation

A group G is said to be a -group if permutability is a transitive relation in the set of all subgroups of G. Our purpose in this paper is to study -groups in the class of periodic radical groups satisfying min-p for all primes p.     

Augmenting the connectivity of geometric graphs

Let G be a connected plane geometric graph with n vertices. In this paper, we study bounds on the number of edges required to be added to G to obtain 2-vertex or 2-edge connected plane geometric graphs. In particular, we show that for G to become 2-edge connected, additional edges are required in some cases and that additional edges are always sufficient. For the special case of plane geometric trees, these bounds decrease to and , respectively.     

Countable choice and compactness

We work in set-theory without choice ZF. Denoting by the countable axiom of choice, we show in that the closed unit ball of a uniformly convex Banach space is compact in the convex topology (an alternative to the weak topology in ZF). We prove that this ball is (closely) convex-compact in the convex topology. Given a set I, a real number p1 (respectively p=0), and some closed subset F of [0,1]^I which is a bounded subset of ℓ^p(I), we show that (respectively DC, the axiom of Dependent Choices) implies the compactness of F.     

A survey on proper codes

The performance of a linear t-error correcting code over a q-ary symmetric memoryless channel with symbol error probability ε is characterized by the probability that a transmission error will remain undetected. This probability is a function of ε involving the code weight distribution and the weight distribution of the cosets of minimum weight at most t. When the undetectable error probability is an increasing function of ε, the code is called t-proper.

The paper presents sufficient conditions for t-properness and a list of codes known to be proper, many of which have been studied by these sufficient conditions. Special attention is paid to error detecting codes of interest in modern communication.     

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 .     

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.     

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.     

Discrete subspaces of countably tight compacta

Our main result is that the following cardinal arithmetic assumption, which is a slight weakening of GCH, “2^κ is a finite successor of κ for every cardinal κ”, implies that in any countably tight compactum X there is a discrete subspace D with . This yields a (consistent) confirmation of Alan Dow’s Conjecture 2 from [A. Dow, Closures of discrete sets in compact spaces, Studia Math. Sci. Hung. 42 (2005) 227–234].     

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.     

Fractal sets determined by dilation-stable processes

Let be a dilation-stable process on . We determine a Hausdorff measure function (a) such that the fractal set X[0,1]={X(t):0t1} has positive finite -measure. We also investigate the packing measure of X[0,1].     

A non-normal topology generated by a two-point selection

We construct a two-point selection , where is the set of the irrational numbers, such that the space is not normal and it is not collectionwise Hausdorff either. Here, τ_f denotes the topology generated by the two-point selection f. This example answers a question posed by V. Gutev and T. Nogura. We also show that if is a two-point selection such that the topology τ_f has countable pseudocharacter, then τ_f is a Tychonoff topology.