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.     

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.     

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.     

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曲面片

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

Enumeration of Almost-Convex Polygons on the Square Lattice

We classify self-avoiding polygons on the square lattice according to a concavity measure, m, where 2m is the difference between the number of steps in the polygon and the perimeter of the minimal rectangle bounding the polygon. We generate series expansions for the perimeter generating functions S_m(x) for polygons of concavity m. We analyze the series S_m(x) for m = 0 to 3. If N_m,n denotes the number of polygons of perimeter 2n and concavity m, with m = o(n^1/2), we prove that N_m,n ? 2^2n?m?7n^m+1/m!, and that the radius of convergence of the series counting all polygons with m = o(n) is equal to 1/4. Our numerical data leads us to conjecture that in fact for m = o(n^1/2), a result confirmed for m = 0 and 1.     

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.     

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.     

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

Ray Shooting Amidst Convex Polygons in 2D

We consider the problem of ray shooting in a two-dimensional scene consisting ofmconvex polygons with a total ofnedges. We present a data structure that requiresO(mn log m) space and preprocessing time and that answers a ray shooting query inO(log² m log² n) time. If the polygons are pairwise disjoint, the space and preprocessing time can be improved toO((m²+n)log m) andO((m²+n log n)log m), respectively. Our algorithm also works for a collection of disjoint simple polygons. We also show that if we allow onlyO(n) space, a ray shooting query among a collection of disjoint simple polygons can be answered in timeO(m/[formula]¹⁺ log² n) time, for any >0.     

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.     

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)

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.     

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

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 .