Flipturning Polygons

   Abstract. A flipturn transforms a nonconvex simple polygon into another simple polygon by rotating a concavity 180° around the midpoint of its bounding convex hull edge. Joss and Shannon proved in 1973 that a sequence of flipturns eventually transforms any simple polygon into a convex polygon. This paper describes several new results about such flipturn sequences. We show that any orthogonal polygon is convexified after at most n-5 arbitrary flipturns, or at most

Isodiametric Problems for Polygons

The maximal area of a polygon with n = 2m edges and unit diameter is not known when m ≥ 5, nor is the maximal perimeter of a convex polygon with n = 2^m edges and unit diameter known when m ≥ 4. We construct improved polygons in both problems, and show that the values we obtain cannot be improved for large n by more than c₁/n³ in the area problem and c₂/n⁵ in the perimeter problem, for certain constants c₁ and c₂.     

How Many Diagonal Rectangles Are Needed to Cover an Orthogonal Polygon?

We show that any orthogonal polygon of n vertices can be covered with at most ``diagonal rectangles' where ω=1 (n=8,12,16) and ω=0 (otherwise). An orthogonal polygon is a polygon whose edges are horizontal or vertical. A diagonal rectangle (of an orthogonal polygon) is a rectangle whose opposite corners are vertices of the orthogonal polygon. The result is sharp and settles a question of Mamoru Watanabe [11]. Received July 25, 1999, and in revised form March 1, 2000. Online publication May 16, 2000.     

Diagonal Flips in Labelled Planar Triangulations

 A classical result of Wagner states that any two (unlabelled) planar triangulations with the same number of vertices can be transformed into each other by a finite sequence of diagonal flips. Recently Komuro gives a linear bound on the maximum number of diagonal flips needed for such a transformation. In this paper we show that any two labelled triangulations can be transformed into each other using at most O(nlogn) diagonal flips. We will also show that any planar triangulation with n>4 vertices has at least n− 2 flippable edges. Finally, we prove that if the minimum degree of a triangulation is at least 4, then it contains at least 2n + 3 flippable edges. These bounds can be achieved by an infinite class of triangulations. Received: June 3, 1998 Final version received: January 26, 2001     

A Jordan–Brouwer Separation Theorem for Polyhedral Pseudomanifolds

The Jordan Curve Theorem referring to a simple closed curve in the plane has a particularly simple proof in the case that the curve is polygonal, called the “raindrop proof”. We generalize the notion of a simple closed polygon to that of a polyhedral (d−1)-pseudomanifold (d≥2) and prove a Jordan–Brouwer Separation Theorem for such a manifold embedded in ℝ ^d . As a by-product, we get bounds on the polygonal diameter of the interior and exterior of such a manifold which are almost tight. This puts the result within the frame of computational geometry. The research of Y.S. Kupitz was partially supported by the Landau Center at the Mathematics Institute of the Hebrew University of Jerusalem (supported by Minerva Foundation, Germany), and by Deutsche Forschungsgemeinschaft.     

Random Subgraphs Of Finite Graphs: III. The Phase Transition For The n-Cube

We study random subgraphs of the n-cube {0,1}ⁿ, where nearest-neighbor edges are occupied with probability p. Let p_c(n) be the value of p for which the expected size of the component containing a fixed vertex attains the value λ2^n/3, where λ is a small positive constant. Let ε=n(p−p_c(n)). In two previous papers, we showed that the largest component inside a scaling window given by |ε|=Θ(2^−n/3) is of size Θ(2^2n/3), below this scaling window it is at most 2(log 2)nε⁻², and above this scaling window it is at most O(ε2ⁿ). In this paper, we prove that for the size of the largest component is at least Θ(ε2ⁿ), which is of the same order as the upper bound. The proof is based on a method that has come to be known as “sprinkling,” and relies heavily on the specific geometry of the n-cube.     

Joint bounds for the Perron roots of nonnegative matrices with applications

Given a finite set {A_x}_{x ∈ X} of nonnegative matrices, we derive joint upper and lower bounds for the row sums of the matrices D⁻¹ A^(x) D, x ∈ X, where D is a specially chosen nonsingular diagonal matrix. These bounds, depending only on the sparsity patterns of the matrices A^(x) and their row sums, are used to obtain joint two-sided bounds for the Perron roots of given nonnegative matrices, joint upper bounds for the spectral radii of given complex matrices, bounds for the joint and lower spectral radii of a matrix set, and conditions sufficient for all convex combinations of given matrices to be Schur stable. Bibliography: 20 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 334, 2006, pp. 30–56.     

Some results on 4<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript>2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> designs with clear two-factor interaction components

Clear effects criterion is one of the important rules for selecting optimal fractional factorial designs, and it has become an active research issue in recent years. Tang et al. derived upper and lower bounds on the maximum number of clear two-factor interactions (2fi’s) in 2 ^n−(n−k) fractional factorial designs of resolutions III and IV by constructing a 2 ^n−(n−k) design for given k, which are only restricted for the symmetrical case. This paper proposes and studies the clear effects problem for the asymmetrical case. It improves the construction method of Tang et al. for 2 ^n−(n−k) designs with resolution III and derives the upper and lower bounds on the maximum number of clear two-factor interaction components (2fic’s) in 4 ^m 2 ⁿ designs with resolutions III and IV. The lower bounds are achieved by constructing specific designs. Comparisons show that the number of clear 2fic’s in the resulting design attains its maximum number in many cases, which reveals that the construction methods are satisfactory when they are used to construct 4 ^m 2 ⁿ designs under the clear effects criterion. This work was supported by the National Natural Science Foundation of China (Grant Nos. 10571093, 10671099 and 10771123), the Research Foundation for Doctor Programme (Grant No. 20050055038) and the Natural Science Foundation of Shandong Province of China (Grant No. Q2007A05). Zhang’s research was also supported by the Visiting Scholar Program at Chern Institute of Mathematics.     

A finite difference scheme of improved accuracy on a priori adapted grids for a singularly perturbed parabolic convection-diffusion equation

In the case of the Dirichlet problem for a singularly perturbed parabolic convection-diffusion equation with a small parameter ɛ multiplying the higher order derivative, a finite difference scheme of improved order of accuracy that converges almost ɛ-uniformly (that is, the convergence rate of this scheme weakly depends on ɛ) is constructed. When ɛ is not very small, this scheme converges with an order of accuracy close to two. For the construction of the scheme, we use the classical monotone (of the first order of accuracy) approximations of the differential equation on a priori adapted locally uniform grids that are uniform in the domains where the solution is improved. The boundaries of such domains are determined using a majorant of the singular component of the grid solution. The accuracy of the scheme is improved using the Richardson technique based on two embedded grids. The resulting scheme converges at the rate of O((ɛ⁻¹ N ^−K ln² N)² + N ⁻²ln⁴ N + N ₀⁻²) as N, N ₀ → ∞, where N and N ₀ determine the number of points in the meshes in x and in t, respectively, and K is a prescribed number of iteration steps used to improve the grid solution. Outside the σ-neighborhood of the lateral boundary near which the boundary layer arises, the scheme converges with the second order in t and with the second order up to a logarithmic factor in x; here, σ = O(N ^{−(K − 1)}ln² N). The almost ɛ-uniformly convergent finite difference scheme converges with the defect of ɛ-uniform convergence ν, namely, under the condition N ⁻¹ ≪ ɛ^ν, where ν determining the required number of iteration steps K (K = K(ν)) can be chosen sufficiently small in the interval (0, 1]. When ɛ⁻¹ = O(N ^{K − 1}), the scheme converges at the rate of O(N ⁻²ln⁴ N + N ₀⁻²).     

Error bounds for asymptotic expansion of the scale mixtures of the normal distribution

Summary LetX be a standard normal random variable and let σ be a positive random variable independent ofX. The distribution of η=σX is expanded around that ofN(0, 1) and its error bounds are obtained. Bounds are given in terms of E(σ ²V−σ ²−1) ^k whereσ ²Vσ ⁻² denotes the maximum of the two quantitiesσ ² andσ ⁻², andk is a positive integer, and of E(σ ²−1) ^k , ifk is even. The Institute of Statistical Mathematics     

Cuttings for Disks and Axis-Aligned Rectangles in Three-Space

We present new asymptotically tight bounds on cuttings, a fundamental data structure in computational geometry. For n objects in space and a parameter r∈?, a $\frac{1}{r}We present new asymptotically tight bounds on cuttings, a fundamental data structure in computational geometry. For n objects in space and a parameter r∈ℕ, a \frac1r\frac{1}{r} -cutting is a covering of the space with simplices such that the interior of each simplex intersects at most n/r objects. For n pairwise disjoint disks in ℝ³ and a parameter r∈ℕ, we construct a \frac1r\frac{1}{r} -cutting of size O(r ²). For n axis-aligned rectangles in ℝ³, we construct a \frac1r\frac{1}{r} -cutting of size O(r ^3/2). As an application related to multi-point location in three-space, we present tight bounds on the cost of spanning trees across barriers. Given n points and a finite set of disjoint disk barriers in ℝ³, the points can be connected with a straight line spanning tree such that every disk is stabbed by at most O(?n)O(\sqrt{n}) edges of the tree. If the barriers are axis-aligned rectangles, then there is a straight line spanning tree such that every rectangle is stabbed by O(n ^1/3) edges. Both bounds are best possible.     

Nodal volumes for eigenfunctions of analytic regular elliptic problems

We establish sharp upper bounds on the (n−1)-dimensional Hausdorff measure of the zero (nodal) sets and on the maximal order of vanishing corresponding to eigenfunctions of a regular elliptic problem on a bounded domain Ω ⊆ ℝ ⁿ with real-analytic boundary. The elliptic operator may be of an arbitrary even order, and its coefficients are assumed to be real-analytic. This extends a result of Donnelly and Fefferman ([DF1], [DF3]) concerning upper bounds for nodal volumes of eigenfunctions corresponding to the Laplacian on compact Riemannian manifolds with boundary.     

On the average crosscap number II: Bounds for a graph

The bounds are obtained for the average crosscap number. Let G be a graph which is not a tree. It is shown that the average crosscap number of G is not less thanβ(G)-1/2β(G)-1β(G) and not larger thanβ(G). Furthermore, we also describe the structure of the graphs which attain the bounds of the average crosscap number.     

A simpler and tighter redundant Klee–Minty construction

By introducing redundant Klee–Minty examples, we have previously shown that the central path can be bent along the edges of the Klee–Minty cubes, thus having 2 ⁿ −2 sharp turns in dimension n. In those constructions the redundant hyperplanes were placed parallel with the facets active at the optimal solution. In this paper we present a simpler and more powerful construction, where the redundant constraints are parallel with the coordinate-planes. An important consequence of this new construction is that one of the sets of redundant hyperplanes is touching the feasible region, and N, the total number of the redundant hyperplanes is reduced by a factor of n ², further tightening the gap between iteration-complexity upper and lower bounds.     

A rank number for a class of polygons

Summary Il the number of tangents of a polygon of real order n in real projective n-space which intersect an arbitrary n−2 − space is counted according to a certain convention this number is shown not to exceed 2n−2. To Enrico Bompiani on his scientific Jubilee     

A class of constructions for turán’s (3, 4)-problem

Letf(n) denote the minimal number of edges of a 3-uniform hypergraphG=(V, E) onn vertices such that for every quadrupleY ⊂V there existsY ⊃e ∈E. Turán conjectured thatf(3k)=k(k−1)(2k−1). We prove that if Turán’s conjecture is correct then there exist at least 2 ^k−2 non-isomorphic extremal hypergraphs on 3k vertices.     

A Higman inequality for regular near polygons

The inequality of Higman for generalized quadrangles of order (s,t) with s>1 states that t≤s ². We generalize this by proving that the intersection number c _i of a regular near 2d-gon of order (s,t) with s>1 satisfies the tight bound c _i ≤(s ²ⁱ −1)/(s ²−1), and we give properties in case of equality. It is known that hemisystems in generalized quadrangles meeting the Higman bound induce strongly regular subgraphs. We also generalize this by proving that a similar subset in regular near 2d-gons meeting the bounds would induce a distance-regular graph with classical parameters (d,b,α,β)=(d,−q,−(q+1)/2,−((−q) ^d +1)/2) with q an odd prime power.     

New Similarity Measures between Polylines with Applications to Morphing and Polygon Sweeping

   Abstract. We introduce two new related metrics, the geodesic width and the link width , for measuring the ``distance' between two nonintersecting polylines in the plane. If the two polylines have n vertices in total, we present algorithms to compute the geodesic width of the two polylines in O(n <sup>2</sup> log n) time using O(n <sup>2</sup> ) space and the link width in O(n <sup>3</sup> log n) time using O(n <sup>2</sup> ) working space where n is the total number of edges of the polylines. Our computation of these metrics relies on two closely related combinatorial strutures: the shortest-path diagram and the link diagram of a simple polygon. The shortest-path (resp., link) diagram encodes the Euclidean (resp., link) shortest path distance between all pairs of points on the boundary of the polygon. We use these algorithms to solve two problems: • Compute a continuous transformation that ``morphs' one polyline into another polyline. Our morphing strategies ensure that each point on a polyline moves as little as necessary during the morphing, that every intermediate polyline is also simple and disjoint to any other intermediate polyline, and that no portion of the polylines to be morphed is stretched or compressed by more than a user-defined parameter during the entire morphing. We present an algorithm that computes the geodesic width of the two polylines and utilizes it to construct a corresponding morphing strategy in O(n ² log ² n) time using O(n ² ) space. We also give an O(nlog n) time algorithm to compute a 2-approximation of the geodesic width and a corresponding morphing scheme. • Locate a continuously moving target using a group of guards moving inside a simple polygon. The guards always determine a simple polygonal chain within the polygon, with consecutive guards along the chain being mutually visible. We compute a strategy that sweeps such a chain of guards through the polygon in order to locate a target. We compute in O(n ³ ) time and O(n ² ) working space the minimum number r ^* of guards needed to sweep an n -vertex polygon. We also give an approximation algorithm, using O(n log n) time and O(n) space, to compute an integer r such that max(r - 16, 2)≤ r ^* ≤ r and P can be swept with a chain of r guards.     

Asymptotic formulas for the enumerator of trees with a given number of hanging or internal vertices

Let t(r, n) be the number of trees with n vertices of which r are hanging and q are internal (r=n−9). For a fixed r or q we prove the validity of the asymptotic formulas (r > 2)t(r, n)≈t/r|(r−2)| 2^2−r n ^2r−4 (n→∞)t(n−q, n)≈1/q|(q&#x2212;1)|q ^q−2 n ^q−1 (n→∞) In the derivation of these formulas we do not use the expression for the enumerator of the trees with respect to the number of hanging vertices. Translated from Matematicheskie Zametki, Vol. 21, No. 1, pp. 65–70, January, 1977.     

On cardinalities of row spaces of Boolean matrices

We prove that there are exactlyn numbers greater than 2 ⁿ⁻¹ that can serve as the cardinalities of row spaces ofn×n Boolean matrices. The numbers are: 2 ⁿ⁻¹+1,2 ⁿ⁻¹+2,2 ⁿ⁻¹+4, ..., 2 ⁿ⁻¹+2 ⁿ⁻², 2 ⁿ . Two consequences follow. The first is that the height of the partial order ofD-classes in the semigroup ofn×n Boolean matrices is at most 2 ⁿ⁻¹+n−1. The second is that the numbers listed above are precisely the numbers greater than 2 ⁿ⁻¹ that can serve as the cardinalities of topologies on a finite setX withn elements.