Line Transversals to Translates of a Convex Body

Let K be a convex body in the plane. Define λ(K,t) as the smallest number satisfying the following: if F\mathcal{F} is any family of translates of K such that every t members of F\mathcal{F} have a common transversal, then all the members of l(K,t)F\lambda(K,t)\mathcal{F} have a common transversal. We give bounds for λ(K,3) and λ(K,4) for a general convex figure K. In particular, we obtain that λ(K,3)≤1.79 when K is the Euclidean disc.     

Cylinder Multipliers Associated with a Convex Polygon

In this paper we prove that sharp weak-type estimates for the maximal operators associated with a cylindric distance function associated with a convex polygon on when 2/3 < p < 1 and , or when p = 2/3 and . This work was supported (in part) by research funds from Chosun University, 2007.     

Minimal Convex k-Gons Containing a Given Convex Polygon

There is a k-gon of minimal area containing a given convex n-gon (k<n) such that k-1 sides of the n-gon lie on the sides of the k-gon. All midpoints of the sides of the k-gon belong to the n-gon. Bibliography: 3 titles.     

Pairs of Convex Bodies with Centrally Symmetric Intersections of Translates

For a pair of convex bodies $K$ and $K$ in $E^d$, the $d$-dimensional intersections $K \cap (x + K),$ $x \in E^d,$ are centrally symmetric if and only if $K$ and $K$ are represented as direct sums $K = R \oplus P$ and $K = R \oplus P$ such that: (i) $R$ is a compact convex set of some dimension $m$, $0 \le m \le d,$ and $R = z - R$ for a suitable vector $z \in E^d$, (ii) $P$ and $P$ are isothetic parallelotopes, both of dimension $d-m$.     

Covering a Convex Polygon by Triangles

According to a theorem of A. V. Bogomolnaya, F. L. Nazarov and S. E. Rukshin, if n points are given inside a convex n-gon, then the points and the sides of the polygon can be numbered from 1 to n so that the triangles spanned by the ith point and the ith side(i=1....,n ) cover the polygon. In this paper, we prove that the same can be done without assuming that the given points are inside the convex n-gon. We also show that in the general case at least [(n/3)] mutually nonoverlapping triangles can be constructed in the same manner.     

Coverings of Convex Sets and Volume Inequalities

We give diverse coverings of convex sets and sections of convex sets in R ⁿ by balls and cylinder sets, and establish volume inequalities which generalize the famous Santalo and inverse Santalo inequalities. The tools which we use are developed from the viewpoint of geometric and functional analysis. Received May 27, 1998, and in revised form January 25, 1999.     

Transversals for Families of Translates of a Two-Dimensional Convex Compact Set

The following Theorem 1 gives an affirmative answer to Grünbaum's old question. Let F be a family of translates of a convex compact set K⊂R ² . If every two elements of F have a common point, then there exist three points A, B, C ∈ R ² such that every element of F contains some of these points. Received December 28, 1998, and in revised form October 20, 1999. Online publication May 15, 2000.     

Optimally Computing the Shortest Weakly Visible Subedge of a Simple Polygon

Given ann-vertex simple polygonP, the problem of computing the shortest weakly visible subedge ofPis that of finding a shortest line segmentson the boundary ofPsuch thatPis weakly visible froms(ifsexists). In this paper, we present new geometric observations that are useful for solving this problem. Based on these geometric observations, we obtain optimal sequential and parallel algorithms for solving this problem. Our sequential algorithm runs inO(n) time, and our parallel algorithm runs inO(log n) time usingO(n/log n) processors in the CREW PRAM computational model. Using the previously best known sequential algorithms to solve this problem would takeO(n²) time. We also give geometric observations that lead to extremely simple and optimal algorithms for solving, both sequentially and in parallel, the case of this problem where the polygons are rectilinear.     

凸多边形切割方法

本文讨论了二维平面上给定区域内的凸多边形切割问题 .按“顶点度数”该问题可以分为两种类型 .在两种类型下并给出了凸多边形的简单切割方法 .     

On Distinct Distances from a Vertex of a Convex Polygon

Given a set P of n points in convex position in the plane, we prove that there exists a point such that the number of distinct distances from p is at least The best previous bound, from 1952, is due to Moser.     

Motion Planning for a Convex Polygon in a Polygonal Environment

We study the motion-planning problem for a convex m -gon P in a planar polygonal environment Q bounded by n edges. We give the first algorithm that constructs the entire free configuration space (the three-dimensional space of all free placements of P in Q ) in time that is near-quadratic in mn , which is nearly optimal in the worst case. The algorithm is also conceptually simple. Previous solutions were incomplete, more expensive, or produced only part of the free configuration space. Combining our solution with parametric searching, we obtain an algorithm that finds the largest placement of P in Q in time that is also near-quadratic in mn . In addition, we describe an algorithm that preprocesses the computed free configuration space so that reachability queries can be answered in polylogarithmic time. Received September 9, 1997, and in revised form September 24, 1998.     

On the Determination of Convex Bodies by Translates of Their Projections

It is a well-known fact that a three-dimensional convex body is, up to translations, uniquely determined by the translates of its orthogonal projections onto all planes. Simple examples show that this is no longer true if only lateral projections are permitted, that is orthogonal projections onto all planes that contain a given line. In this article large classes of convex bodies are specified that are essentially determined by translates or homothetic images of their lateral projections. The problem is considered for all dimensions , and corresponding stability results are proved. Finally, it is investigated to which degree of precision a convex body can be determined by a finite number of translates of its projections. Various corollaries concern characterizations and corresponding stability statements for convex bodies of constant width and spheres.     

Decompositions,Partitions, and Coverings with Convex Polygons and Pseudo-Triangles

We propose a novel subdivision of the plane that consists of both convex polygons and pseudo-triangles. This pseudo-convex decomposition is significantly sparser than either convex decompositions or pseudo-triangulations for planar point sets and simple polygons. We also introduce pseudo-convex partitions and coverings. We establish some basic properties and give combinatorial bounds on their complexity. Our upper bounds depend on new Ramsey-type results concerning disjoint empty convex k-gons in point sets.     

凸多边形的最优切割策略

本文研究的是在一个平面区域内切割出一个预定的凸多边形的最优策略问题 .首先应用动态规划建立模型 ,然后 ,证明了优化变换的两个准则 ,最后 ,我们对极先切割边进行了讨论 ,得出了简明的最优切割策略     

Some Computational Aspects of Geodesic Convex Sets in a Simple Polygon

In this article, we deal with some computational aspects of geodesic convex sets. Motzkin-type theorem, Radon-type theorem, and Helly-type theorem for geodesic convex sets are shown. In particular, given a finite collection of geodesic convex sets in a simple polygon and an “oracle,” which accepts as input three sets of the collection and which gives as its output an intersection point or reports its nonexistence; we present an algorithm for finding an intersection point of this collection.     

Largest Placement of One Convex Polygon Inside Another

We show that the largest similar copy of a convex polygon P with m edges inside a convex polygon Q with n edges can be computed in O(mn ² log n) time. We also show that the combinatorial complexity of the space of all similar copies of P inside Q is O(mn ² ) , and that it can also be computed in O(mn ² log n) time. Received December 11, 1995, and in revised form March 3, 1997.     

The Poisson and the Biharmonic Equations in the Interior of a Convex Polygon

A new method for analyzing linear elliptic partial differential equations in the interior of a convex polygon was developed in the late 1990s. This method does not rely on the classical approach of separation of variables and on the use of classical integral transforms and therefore is well suited for the investigation of the biharmonic equation. Here, we present a novel integral representation of the solution of the biharmonic equation in the interior of a convex polygon. This representation contains certain free parameters and therefore is more general than the one presented in [1]. For a given boundary value problem, by choosing these free parameters appropriately, one can obtain the simplest possible representation for the solution. This representation still involves certain unknown boundary values, thus for this formula to become effective it is necessary to characterize the unknown boundary values in terms of the given boundary conditions. This requires the investigation of certain relations refereed to as the global relations. A general approach for analyzing these relations is illustrated by solving several problems formulated in the interior of a semistrip. In addition, for completeness, similar results are presented for the Poisson equation by employing an integral representation for the Laplace equation which is more general than the one derived in the late 1990s.     

Covering the Plane with Translates of a Triangle

The minimum density of a covering of the plane with translates of a triangle is frac32frac{3}{2} .     

带有给定凸切线多边形的保形五次样条逼近

本讨论带有给定切线多边形的保形逼近问题．给出了一条与给定切线多边形相切的保形五次参数祥条曲线。