Hierarchical Decompositions and Circular Ray Shooting in Simple Polygons

A hierarchical decomposition of a simple polygon is introduced. The hierarchy has logarithmic depth, linear size, and its regions have at most three neighbors. Using this hierarchy, circular ray shooting queries in a simple polygon on n vertices can be answered in O(log² n) query time and O(n log n) space. If the radius of the circle is fixed, the query time can be improved to O(log n) and the space to O(n).     

Implicit Convex Polygons

Convex polygons in the plane can be defined explicitly as an ordered list of vertices, or given implicitly, for example by a list of linear constraints. The latter representation has been considered in several fields such as facility location, robotics and computer graphics. In this paper, we investigate many fundamental geometric problems for implicitly represented polygons and give simple and fast algorithms that are easy to implement. We uncover an interesting partition of the problems into two classes: those that exhibit an (nlogn) lower bound on their complexity, and those that yield O(n) time algorithms via prune-and-search methods.     

Pebble Sets in Convex Polygons

Lukács and András posed the problem of showing the existence of a set of n−2 points in the interior of a convex n-gon so that the interior of every triangle determined by three vertices of the polygon contains a unique point of S. Such sets have been called pebble sets by De Loera, Peterson, and Su. We seek to characterize all such sets for any given convex polygon in the plane. We first consider a certain class of pebble sets, called peripheral because they consist of points that lie close to the boundary of the polygon. We characterize all peripheral pebble sets, and show that for regular polygons, these are the only ones. Though we demonstrate examples of polygons where there are other pebble sets, we nevertheless provide a characterization of the kinds of points that can be involved in non-peripheral pebble sets. We furthermore describe algorithms to find such points.     

Convex Polygons are Cover-Decomposable

We show that for any open convex polygon P, there is a constant k(P) such that any k(P)-fold covering of the plane with translates of P can be decomposed into two coverings.     

Asymptotic Enumeration of Convex Polygons

A polygon is an elementary (self-avoiding) cycle in the hypercubic lattice ^dtaking at least one step in every dimension. A polygon on ^dis said to be convex if its length is exactly twice the sum of the side lengths of the smallest hypercube containing it. The number ofd-dimensional convex polygonsp_{n, d}of length 2nwithd(n)→∞ is asymptoticallywherer=r(n, d) is the unique solution ofr coth r=2n/d−1andb(r)=d(r coth r−r²/sinh² r). The convergence is uniform over alld?ω(n) for any functionω(n)→∞. Whendis constant the exponential is replaced with (1−d⁻¹)^2d. These results are proved by asymptotically enumerating a larger class of combinatorial objects calledconvex proto-polygonsby the saddle-point method and then finding the asymptotic probability a randomly chosen convex proto-polygon is a convex polygon.     

Circle Numbers of Regular Convex Polygons

The circle number function is extended here to regular convex polygons. To this end, the radius of the polygonal circle is defined as the Minkowski functional of the circumscribed polygonal disc, and the arc-length of the polygonal circle is measured in a generalized Minkowski space having the rotated polar body as the unit disc.     

Affine Properties of Convex Equal-Area Polygons

In this paper we discuss some affine properties of convex equal-area polygons, which are convex polygons such that all triangles formed by three consecutive vertices have the same area. Besides being able to approximate closed convex smooth curves almost uniformly with respect to affine length, convex equal-area polygons admit natural definitions of the usual affine differential geometry concepts, like affine normal and affine curvature. These definitions lead to discrete analogous to the six-vertex theorem and an affine isoperimetric inequality. One can also define discrete counterparts of the affine evolute, parallels and the affine distance symmetry set preserving many of the properties valid for smooth curves.     

凸多边形上的Bezier曲面片

本文建立了正多边形上的重心坐标，并构造了多边形上的Ｂｅｚｉｅｒ曲面片、     

Helly Type Problems forSome Special Convex Polygons

In the combinatorial geometry of convex sets the question of how efficiently a family ofconvex sets can be pierced by points has led to various problems which may be regarded asextensions of the Helly-type problems. A family of sets is said to be n-pierceable (abbreviatedas n) if there exists a set of n points such that each member of the family contains at leastone of them. A family of sets is said to be nk: if every subfamily of size k or less is n. Thefamous Helly theorem in combinatorial …     

Tiling Convex Polygons with Congruent Equilateral Triangles

We study the sets $\mathcal{T}_{v}=\{m \in\{1,2,\ldots\}: \mbox{there is a convex polygon in }\mathbb{R}^{2}\mbox{ that has }v\mbox{ vertices and can be tiled with $m$ congruent equilateral triangles}\}$ , v=3,4,5,6. $\mathcal{T}_{3}$ , $\mathcal{T}_{4}$ , and $\mathcal{T}_{6}$ can be quoted completely. The complement $\{1,2,\ldots\} \setminus\mathcal{T}_{5}$ of $\mathcal{T}_{5}$ turns out to be a subset of Euler’s numeri idonei. As a consequence, $\{1,2,\ldots\} \setminus\mathcal{T}_{5}$ can be characterized with up to two exceptions, and a complete characterization is given under the assumption of the Generalized Riemann Hypothesis.     

Tilings of Convex Polygons with Congruent Triangles

By the spectrum of a polygon A we mean the set of triples (??,??,??) such that A can be dissected into congruent triangles of angles ??,??,??. We propose a technique for finding the spectrum of every convex polygon. Our method is based on the following classification. A tiling is called regular if there are two angles of the triangles, ?? and ?? such that at every vertex of the tiling the number of triangles having angle ?? equals the number of triangles having angle ??. Otherwise the tiling is irregular. We list all pairs (A,T) such that A is a convex polygon and T is a triangle that tiles A regularly. The list of triangles tiling A irregularly is always finite, and can be obtained, at least in principle, by considering the system of equations satisfied by the angles, examining the conjugate tilings, and comparing the sides and the area of the triangles to those of A. Using this method we characterize the convex polygons with infinite spectrum, and determine the spectrum of the regular triangle, the square, all rectangles, and the regular N-gons with N large enough.     

On Minimal Triangulations of Products of Convex Polygons

We give new lower bounds for the minimal number of simplices needed in a triangulation of the product of two convex polygons, improving the lower bounds in Bowen et al. (Topology 44:321–339, 2005).     

Reconstructing Convex Polygons in the Plane from One Directed X-Ray

Gardner [7] proved that with the exception of a simple class of nonparallel wedges, convex polygons in the plane are uniquely determined by one directed X-ray. This paper develops methods for reconstructing convex polygons in the plane from one directed X-ray. We show that nonsmooth points on the boundary of a convex body are located along rays where the derivative of the data have a jump discontinuity. Location of the nonsmooth points divides a convex polygon into a finite set of wedges. We prove uniqueness theorems and give algorithms for reconstructing nonparallel wedges from line integrals along four or more rays. Also, we characterize discrete data sets that are directed X-rays of both parallel and nonparallel wedges. Several examples of reconstructions are included. Received August 16, 1999, and in revised form September 13, 2000. Online publication May 4, 2001.     

The Unit Distance Problem for Centrally Symmetric Convex Polygons

   Abstract. Let f(n) be the maximum number of unit distances determined by the vertices of a convex n -gon. Erdos and Moser conjectured that this function is linear. Supporting this conjecture we prove that f ^sym (n)

Irregularities of Point Distribution Relative to Convex Polygons III

Suppose that P is a distribution of N points in the unit squareU=[0, 1]². For every x=(x₁, x₂)U, let B(x)=[0, x₁]x[0, x₂] denotethe aligned rectangle containing all points y=(y₁, y₂)U satisfying0y₁x₁ and 0y₂x₂. Denote by Z[P; B(x)] the number of points ofP that lie in B(x), and consider the discrepancy function D[P; B(x)]=Z[P; B(x)]–Nµ(B(x)), where µ denotes the usual area measure.     

RESEARCH ANNOUNCEMENTS Helly Type Problems for Some Special Convex Polygons

In the combinatorial geometry of convex sets the question of how efficiently a family of convex sets can be pierced by points has led to various problems which may be regarded as extensions of the Helly-type problems. A family of sets is said to be n-pierceable (abbreviated as Пn) if there exists a set of n points such that each member of the family contains at least one of them. A family of sets is said to be Пnk if every subfamily of size k or less is Пn. The famous Helly theorem in combinatorial geometry asserts that for finite families of convex sets in the plane П13 implies П1. In a recent paper by M. Katchalski and D. Nashtir[a] the following conjecture of Griinbaum[2] was mentioned again:     

A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk

We propose a very simple ray-shooting algorithm, whose only data structure is a triangulation. The query algorithm, after locating the triangle containing the origin of the ray, walks along the ray, advancing from one triangle to a neighboring one until the polygon boundary is reached. The key result of the paper is a Steiner triangulation of a simple polygon with the property that a ray can intersect at most O(log n) triangles before reaching the polygon boundary. We are able to compute such a triangulation in linear sequential time, or in O(log n) parallel time using O(n/log n) processors. This gives a simple, yet optimal, ray-shooting algorithm for a simple polygon. Using a well-known technique, we can extend our triangulation procedure to a multiconnected polygon with k components and n vertices, so that a ray intersects at most O(√k log n) triangles.     

A Sufficient Condition for the Existence of Large Empty Convex Polygons

   Abstract. Let P be a set of points in general position in the plane. We say that P is k -convex if no triangle determined by P contains more than k points of P in the interior. We say that a subset A of P in convex position forms an empty polygon (in P ) if no point of P \ A lies in the convex hull of A . We show that for any k,n there is an N=N(k,n) such that any k -convex set of at least N points in general position in the plane contains an empty n -gon. We also prove an analogous statement in R ^d for each odd d≥ 3 .