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.     

Algorithms for optimal area triangulations of a convex polygon

Given a convex polygon with n vertices in the plane, we are interested in triangulations of its interior, i.e., maximal sets of non-intersecting diagonals that subdivide the interior of the polygon into triangles. The MaxMin area triangulation is the triangulation of the polygon that maximizes the area of the smallest triangle in the triangulation. Similarly, the MinMax area triangulation is the triangulation that minimizes the area of the largest area triangle in the triangulation. We present algorithms that construct MaxMin and MinMax area triangulations of a convex polygon in O(n²logn) time and O(n²) space. The algorithms use dynamic programming and a number of geometric properties that are established within the paper.     

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.     

Pseudoarcs, pseudocircles, Lakes of Wada and generic maps on

We prove a Bruckner–Garg type theorem for the fiber structure of a generic map from a continuum X into the unit interval I. We also study the specific case of X=S². We show that each nondegenerate component of each fiber of a generic map in C(S²,I) is figure-eight-like. This together with a result by Krasinkiewicz and Levin gives that each nondegenerate component of each fiber of a generic map in C(S²,I) is hereditarily indecomposable and figure-eight-like. We also show that pseudoarcs, pseudocircles and Lakes of Wada appear in abundance in fibers of a generic map in C(S²,I). We also exhibit a general method for proving when a P-like hereditarily indecomposable continuum is Q-like when Q is a certain graph containing P.     

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.     

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.     

On fat partitioning, fat covering and the union size of polygons

The complexity of the contour of the union of simple polygons with n vertices in total can be O(n²) in general. A notion of fatness for simple polygons is introduced that extends most of the existing fatness definitions. It is proved that a set of fat polygons with n vertices in total has union complexity O(n log log n), which is a generalization of a similar result for fat triangles (Matou ek et al., 1994). Applications to several basic problems in computational geometry are given, such as efficient hidden surface removal, motion planning, injection molding, and more. The result is based on a new method to partition a fat simple polygon P with n vertices into O(n) fat convex quadrilaterals, and a method to cover (but not partition) a fat convex quadrilateral with O(l) fat triangles. The maximum overlap of the triangles at any point is two, which is optimal for any exact cover of a fat simple polygon by a linear number of fat triangles.     

2-Tree probe interval graphs have a large obstruction set

Probe interval graphs (PIGs) are used as a generalization of interval graphs in physical mapping of DNA. G=(V,E) is a probe interval graph (PIG) with respect to a partition (P,N) of V if vertices of G correspond to intervals on a real line and two vertices are adjacent if and only if their corresponding intervals intersect and at least one of them is in P; vertices belonging to P are called probes and vertices belonging to N are called non-probes. One common approach to studying the structure of a new family of graphs is to determine if there is a concise family of forbidden induced subgraphs. It has been shown that there are two forbidden induced subgraphs that characterize tree PIGs. In this paper we show that having a concise forbidden induced subgraph characterization does not extend to 2-tree PIGs; in particular, we show that there are at least 62 minimal forbidden induced subgraphs for 2-tree PIGs.     

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.     

Recognizing Hopf algebroids defined by a group action

Let A be a complete noetherian regular local ring, and suppose that S is a profinite group acting continuously on A via ring homomorphisms. Let Γ=Map_c(S,A), the algebra of continuous functions from S to A. Then (A,Γ) has a canonical structure of a complete Hopf algebroid, determined by the action of S on A. We give necessary and sufficient conditions for a general complete Hopf algebroid to be of this form. Applications to Morava theory are also discussed.     

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.     

Farthest-point queries with geometric and combinatorial constraints

In this paper we discuss farthest-point problems in which a set or sequence S of n points in the plane is given in advance and can be preprocessed to answer various queries efficiently. First, we give a data structure that can be used to compute the point farthest from a query line segment in O(log²n) time. Our data structure needs O(nlogn) space and preprocessing time. To the best of our knowledge no solution to this problem has been suggested yet. Second, we show how to use this data structure to obtain an output-sensitive query-based algorithm for polygonal path simplification. Both results are based on a series of data structures for fundamental farthest-point queries that can be reduced to each other.     

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.     

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.     

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.     

Eigenvalues of association schemes of quadratic forms

The duality and primitivity of the association scheme Qua(n,q) of quadratic forms in n variables and the association scheme Sym(n,q) of symmetric bilinear forms in n variables over the finite field are discussed by Wang et al. [Association schemes of quadratic forms and symmetric bilinear forms, J. Algebraic Combin. 17 (2003) 149–161]. In this paper, eigenvalues of Qua(n,q) are computed, where q is a power of 2. As an application, two fusion schemes of Qua(n,q) are discussed and their dual schemes are constructed.     

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.     

Constrained tree inclusion

The tree matching problem is considered of given labeled trees P and T, determining if the pattern tree P can be obtained from the text tree T by deleting degree-one and degree-two nodes and, in the case of unordered trees, by also permuting siblings. The constrained tree inclusion problem is more sensitive to the structure of the pattern tree than the general tree inclusion problem. Further, it can be solved in polynomial time for both unordered and ordered trees. Algorithms based on the restricted subtree homeomorphism algorithm of M.-J. Chung [J. Algorithms 8 (1) (1987) 106–112] are presented that solve the constrained tree inclusion problem in O(m^1.5n) time on unordered trees with m and n nodes, and in O(mn) time on ordered trees, using O(mn) additional space.     

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.     

The Erdős–Nagy theorem and its ramifications

Given a simple polygon in the plane, a flip is defined as follows: consider the convex hull of the polygon. If there are no pockets do not perform a flip. If there are pockets then reflect one pocket across its line of support of the polygon to obtain a new simple polygon. In 1934 Paul Erdős introduced the problem of repeatedly flipping all the pockets of a simple polygon simultaneously and he conjectured that the polygon would become convex after a finite number of flips. In 1939 Béla Nagy proved that if at each step only one pocket is flipped the polygon will become convex after a finite number of flips. The history of this problem is reviewed, and a simple elementary proof is given of a stronger version of the theorem. Variants, generalizations, and applications of the theorem of interest in computational knot theory, polymer physics and molecular biology are discussed. Several results in the literature are improved with the application of the theorem. For example, Grünbaum and Zaks recently showed that even non-simple (self-crossing) polygons may be convexified in a finite number of suitable flips. Their flips each take Θ(n²) time to determine. A simpler proof of this result is given that yields an algorithm that takes O(n) time to determine each flip. In the context of knot theory Millet proposed an algorithm for convexifying equilateral polygons in 3-dimensions with a generalization of a flip called a pivot. Here Millet's algorithm is generalized so that it works also in dimensions higher than three and for polygons containing edges with arbitrary lengths. A list of open problems is included.