Affinely Regular Polygons as Extremals of Area Functionals

For any convex n-gon P we consider the polygons obtained by dropping a vertex or an edge of P. The area distance of P to such (n−1)-gons, divided by the area of P, is an affinely invariant functional on n-gons whose maximizers coincide with the affinely regular polygons. We provide a complete proof of this result. We extend these area functionals to planar convex bodies and we present connections with the affine isoperimetric inequality and parallel X-ray tomography.     

Primitive and mensurable hex-triangles

When the corners of a planar polygon P are restricted to lie in the set H of vertices of a tiling of the plane by hexagons of unit area, then very often the area of P is given by the Pick-type formula A(P)=b/4+i/2+c/12-1, where b and i count the number of points of H on the boundary P and in the interior of P respectively, and c is the boundary characteristic. We now characterize all primitive triangles for which this formula holds, and consider the magnitude of the error when it fails.     

On the Area Bisectors of a Polygon

We consider the family of lines that are area bisectors of a polygon (possibly with holes) in the plane. We say that two bisectors of a polygon P are combinatorially distinct if they induce different partitionings of the vertices of P . We derive an algebraic characterization of area bisectors. We then show that there are simple polygons with n vertices that have Ω(n ² ) combinatorially distinct area bisectors (matching the obvious upper bound), and present an output-sensitive algorithm for computing an explicit representation of all the bisectors of a given polygon. Received September 11, 1997, and in revised form April 8, 1998.     

Extremal point queries with lines and line segments and related problems

We address a number of extremal point query problems when P is a set of n points in , d3 a constant, including the computation of the farthest point from a query line and the computation of the farthest point from each of the lines spanned by the points in P. In , we give a data structure of size O(n¹⁺), that can be constructed in O(n¹⁺) time and can report the farthest point of P from a query line segment in O(n^2/3+) time, where >0 is an arbitrarily small constant. Applications of our results also include: (1) Sub-cubic time algorithms for fitting a polygonal chain through an indexed set of points in , d3 a constant, and (2) A sub-quadratic time and space algorithm that, given P and an anchor point q, computes the minimum (maximum) area triangle defined by q with P{q}.     

Realizable Quadruples for Hex-polygons

There are many interesting combinatorial results and problems dealing with lattice polygons, that is, polygons in ℝ² with vertices in the integral lattice ℤ². Geometrically, ℤ² is the set of corners of a tiling of ℝ² by unit squares. Denote by H the set of corners of a tiling of the plane by regular hexagons of unit area and call a polygon P a Hex-polygon or an H-polygon if all vertices of P are in H. Our purpose is to study several combinatorial properties of H-polygons that are analogous to properties of lattice polygons. In particular we aim to find some relationships between the numbers b and i of points from H on the boundary and in the interior of an H-polygon P with the numbers v and c of vertices and the so-called boundary characteristic of P. We also pose three open problems dealing with convex Hex-polygons.     

On Monoids for Which all Condition (P) Acts are Strongly Flat

In this article, we continue to investigate the monoids over which all right S-acts satisfying condition (P) are strongly flat, and we obtain some new classes of monoids, thereby extending all previous results in this area.     

Affine Maps That Induce Polyhedral Complex Isomorphisms

In this paper we show that an affine bijection f : T ₁ → T ₂ between two polyhedral complexes T ₁ ,T ₂ , both of which consist of a union of faces of two convex polyhedra P ₁ and P ₂ , necessarily respects the cell-complex structure of T ₁ and T ₂ inherited from P ₁ and P ₂ , respectively, provided f extends to an affine map from P ₁ into P ₂ . In addition, we present an application of this result within the area of T-theory to obtain a far-reaching generalization of previous results regarding the equivalence of two distinct constructions of the phylogenetic tree associated to ``perfect' (that is, treelike) distance data. Received September 30, 1999, and in revised form February 25, 2000. Online publication May 15, 2000.     

Polyhedral hyperbolic metrics on surfaces

Let S be a topologically finite surface, and g be a hyperbolic metric on S with a finite number of conical singularities of positive singular curvature, cusps and complete ends of infinite area. We prove that there exists a convex polyhedral surface P in hyperbolic space and a group G of isometries of such that the induced metric on the quotient P/G is isometric to g. Moreover, the pair (P, G) is unique among a particular class of convex polyhedra.      

On Simple Polygonalizations with Optimal Area

We discuss the problem of finding a simple polygonalization for a given set of vertices P that has optimal area. We show that these problems are very closely related to problems of optimizing the number of points from a set Q in a simple polygon with vertex set P and prove that it is NP-complete to find a minimum weight polygon or a maximum weight polygon for a given vertex set, resulting in a proof of NP-completeness for the corresponding area optimization problems. This answers a generalization of a question stated by Suri in 1989. Finally, we turn to higher dimensions, where we prove that, for 1 k d , 2 d , it is NP-hard to determine the smallest possible total volume of the k -dimensional faces of a d -dimensional simple nondegenerate polyhedron with a given vertex set, answering a generalization of a question stated by O'Rourke in 1980. Received June 26, 1997, and in revised form February 13, 1999, and May 19, 1999.     

Approximation of smooth convex bodies by circumscribed polytopes with respect to the surface area

Let K be a convex body with C ² boundary in the Euclidean d-space. Following the work of L. Fejes Tóth, R. Vitale, R. Schneider, P.M. Gruber, S. Glasauer and M. Ludwig, best approximation of K by polytopes of restricted number of vertices or facets is well-understood if the approximation is with respect to the volume or the mean width. In this paper we consider the circumscribed polytope P _(n) of n facets with minimal surface area, and present an asymptotic formula in terms of n for the difference of surface areas of P _(n) and K.     

Safety Zone Problem

Given a simple polygon P, its safety zone S (of width δ) is a closed region consisting of straight line segments and circular arcs (of radius δ) bounding the polygon P such that there exists no pair of points p (on the boundary of P) and q (on the boundary of S) having their Euclidean distance d(p, q) less than δ. In this paper we present a linear time algorithm for finding the minimum area safety zone of an arbitrarily shaped simple polygon. It is also shown that our proposed method can easily be modified to compute the Minkowski sum of a simple polygon and a convex polygon in O(MN) time, where M and N are the number of vertices of both the polygons.     

Zero Distribution of Bergman Orthogonal Polynomials for Certain Planar Domains

   Abstract. Let G be a simply connected domain in the complex plane bounded by a closed Jordan curve L and let P _n , n≥ 0 , be polynomials of respective degrees n=0,1,··· that are orthonormal in G with respect to the area measure (the so-called Bergman polynomials). Let ϕ be a conformal map of G onto the unit disk. We characterize, in terms of the asymptotic behavior of the zeros of P _n 's, the case when ϕ has a singularity on L . To investigate the opposite case we consider a special class of lens-shaped domains G that are bounded by two orthogonal circular arcs. Utilizing the theory of logarithmic potentials with external fields, we show that the limiting distribution of the zeros of the P _n 's for such lens domains is supported on a Jordan arc joining the two vertices of G . We determine this arc along with the distribution function.     

Random points in halfspheres

A random spherical polytope P_n in a spherically convex set as considered here is the spherical convex hull of n independent, uniformly distributed random points in K. The behaviour of P_n for a spherically convex set K contained in an open halfsphere is quite similar to that of a similarly generated random convex polytope in a Euclidean space, but the case when K is a halfsphere is different. This is what we investigate here, establishing the asymptotic behaviour, as n tends to infinity, of the expectation of several characteristics of P_n, such as facet and vertex number, volume and surface area. For the Hausdorff distance from the halfsphere, we obtain also some almost sure asymptotic estimates. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 3–22, 2017     

A Cellular Triangle Containing a Specified Point

 Let P be a set of finite points in the plane in general position, and let x be a point which is not contained in any of the lines passing through at least two points of P. A line l is said to be a k-bisector if both of the two closed half-planes determined by l contain at least k points of P. We show that if any line passing through x is a -bisector and does not contain two or more points of P, then there exist three points P ₁, P ₂, P ₃ of P such that ΔP ₁ P ₂ P ₃ contains x and does not contain points of P in its interior, and such that each of the lines passing through two of them is a -bisector. Received: October 16, 1995 / Revised: October 16, 1996     

Sufficiency and completeness for classes of probability distributions generated by a single probability distribution

Let (Ω,A, P₀) denote a probability space andA some sub-σ-algebra ofA. Moreover,P _{P 0} stands for the set consisting of all probability distributionsP _{P 0} of the typeP _{P 0}(A) = ∫E _{P 0} (P _{A |B)dP,A ∈A, whereP is a probability distribution onA satisfyingP |B ≪P 0} |B. It is shown thatB is sufficient and (even totally) complete forP _{P 0}. This results is illustrated by examples. Finally, it is shown thatP _{P 0} ∈P _{P 0} is an extremal point ofP _{P 0} if and only ifP |B is {0, 1}-valued. Dedicated to the memory of Professor K. Behnen     

Compactness and subsets of ordered sets that meet all maximal chains

LetP be a chain complete ordered set. By considering subsets which meet all maximal chains, we describe conditions which imply that the space of maximal chains ofP is compact. The symbolsP ₁ andP ₂ refer to two particular ordered sets considered below. It is shown that the space of maximal chains (P) is compact ifP satisfies any of the following conditions: (i)P contains no copy ofP ₁ or its dual and all antichains inP are finite. (ii)P contains no properN and every element ofP belongs to a finite maximal antichain ofP. (iii)P contains no copy ofP ₁ orP ₂ and for everyx inP there is a finite subset ofP which is coinitial abovex. We also describe an example of an ordered set which is complete and densely ordered and in which no antichain meets every maximal chain.     

Minimal extensions of Π01 classes

A minimal extension of a Π⁰₁ class P is a Π⁰₁ class Q such that P ? Q, Q – P is infinite, and for any Π⁰₁ class R, if P ? R ? Q, then either R – P is finite or Q – R is finite; Q is a nontrivial minimal extension of P if in addition P and Q′ have the same Cantor‐Bendixson derivative. We show that for any class P which has a single limit point A, and that point of degree ≤ 0 , P admits a nontrivial minimal extension. We also show that as long as P is infinite, then P does not admit any decidable nontrivial minimal extension Q. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Strongly subadditive functions

Let f: ℝ⁺ → ℝ. The subject is the trace inequality Tr f(A) + Tr f(P ₂ AP ₂) ≦ Tr f(P ₁₂ AP ₁₂) + Tr f(P ₂₃ AP ₂₃), where A is a positive operator, P ₁; P ₂; P ₃ are orthogonal projections such that P ₁ + P ₂ + P ₃ = I, P ₁₂ = P ₁ + P ₂ and P ₂₃ = P ₂ + P ₃. There are several examples of functions f satisfying the inequality (called (SSA)) and the case of equality is described.     

Noncommuting (S 5, S 5)-Amalgams

ABSTRACT

Rank 2-amalgams (P ₁, P ₂, B), in which P ₁/O ₂(P ₁) ? P ₂/O ₂(P ₂) ? S ₅, are analyzed using the amalgam method. It is determined that in the noncommuting case either |O ₂(P ₁)| = |O ₂(P ₂)| ≤ 2⁶ or (P ₁, P ₂, B) has the same shape as an amalgam in Aut(G ₂(4)).     

Zur S-Darstellbarkeit endlicher lokal-affiner Kreisräume

An incidence structure (P, N, I) consisting of a set P of points, a set N of circles and an incidence relation I is called a locally affine circular space R, if the following holds: For any point PP the points and the circles of the internal structure R _P =(P _P , N _P , I _P ) with P _P =P{P}, N _P ={kN|PIk} and I _p =I(P _P ×N _P ) are respectively the points and the lines of an affine space.The purpose of this paper is at first to find conditions for representing a finite locally affine circular space R as a substrcture of a finite projective space B. In our representation (called S-representation) the points of R correspond to the elements of a spread L in B and the circles to certain lines of B not contained in elements of L. It is then shown that a finite inversive plane M of order q admits an S-representation if and only if q is even. As consequences we get characterizations of miquelian inversive planes of even order.