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.     

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.     

Reconstructing Boundary Points of Convex Sets from X-ray Pictures

A method for the reconstruction of boundary points of convex sets is provided starting from three X-ray pictures in two orthogonal directions and from a point.     

Forced Convex n -Gons in the Plane

In a seminal paper from 1935, Erdős and Szekeres showed that for each n there exists a least value g(n) such that any subset of g(n) points in the plane in general position must always contain the vertices of a convex n -gon. In particular, they obtained the bounds which have stood unchanged since then. In this paper we remove the +1 from the upper bound for n ≥ 4 . <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p367.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received January 1, 1997, and in revised form June 6, 1997.     

Convex Regions in the Plane and their Domes

We make a detailed study of the relation of a euclidean convexregion C Dome (). The dome is the relative boundary, in theupper halfspace model of hyperbolic space, of the hyperbolicconvex hull of the complement of . The first result is to provethat the nearest point retraction r: Dome () is 2-quasiconformal.The second is to establish precise estimates of the distortionof r near . 2000 Mathematics Subject Classification 30C75,30F40, 30F45, 30F60.     

Perfect Partitions of Convex Sets in the Plane

   Abstract. For a region X in the plane, we denote by area(X) the area of X and by ℓ (∂ (X)) the length of the boundary of X . Let S be a convex set in the plane, let n ≥ 2 be an integer, and let α ₁ , α ₂ , . . . ,α _n be positive real numbers such that α ₁ +α ₂ + ⋅ ⋅ ⋅ +α _n =1 and 0< α _i ≤ 1/2 for all 1 ≤ i ≤ n . Then we shall show that S can be partitioned into n disjoint convex subsets T ₁ , T ₂ , . . . ,T _n so that each T _i satisfies the following three conditions: (i) area(T _i )=α _i × area(S) ; (ii) ℓ (T _i ∩ ∂ (S))= α _i × ℓ (∂ (S)) ; and (iii) T _i ∩ ∂ (S) consists of exactly one continuous curve.     

Finding Convex Sets Among Points in the Plane

Let g(n) denote the least value such that any g(n) points in the plane in general position contain the vertices of a convex n -gon. In 1935, Erdős and Szekeres showed that g(n) exists, and they obtained the bounds Chung and Graham have recently improved the upper bound by 1; the first improvement since the original Erdős—Szekeres paper. We show that <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p405.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received January 1, 1997, and in revised form June 6, 1997.     

Perfect Partitions of Convex Sets in the Plane

Abstract. For a region X in the plane, we denote by area(X) the area of X and by ℓ (∂ (X)) the length of the boundary of X . Let S be a convex set in the plane, let n ≥ 2 be an integer, and let α ₁ , α ₂ , . . . ,α _n be positive real numbers such that α ₁ +α ₂ + ⋅ ⋅ ⋅ +α _n =1 and 0< α _i ≤ 1/2 for all 1 ≤ i ≤ n . Then we shall show that S can be partitioned into n disjoint convex subsets T ₁ , T ₂ , . . . ,T _n so that each T _i satisfies the following three conditions: (i) area(T _i )=α _i × area(S) ; (ii) ℓ (T _i ∩ ∂ (S))= α _i × ℓ (∂ (S)) ; and (iii) T _i ∩ ∂ (S) consists of exactly one continuous curve.     

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 .     

On Extreme Convex Subsets of the Plane

Let Q be a convex compact set in R2 with a non-empty interior. We denoteby C the family of all non-empty closed convex subsets of Q. The aim of thepaper is to characterize the extreme elements of C.     

复平面上正多边形的判定及应用

结合教学给出复平面上n个点成为正多边形的条件,最后讨论它的一些应用.     

On One Counterexample in Convex Approximation

We prove the existence of a function fcontinuous and convex on [–1, 1] and such that, for any sequence {p _n} _{n= 1} of algebraic polynomials p _nof degree nconvex on [–1, 1], the following relation is true: , where ₄(t, f) is the fourth modulus of continuity of the function fand . We generalize this result to q-convex functions.     

Computing Skeletons for Rectilinearly Convex Obstacles in the Rectilinear Plane

Journal of Optimization Theory and Applications - We introduce the concept of an obstacle skeleton, which is a set of line segments inside a polygonal obstacle $$\omega $$ that can be used in place...     

Allowable Interval Sequences and Separating Convex Sets in the Plane

In 2005, Goodman and Pollack introduced the concept of an allowable interval sequence, a combinatorial object which encodes properties of a family of pairwise disjoint convex sets in the plane. They, Dhandapani, and Holmsen used this concept to address Tverberg’s (1,k)-separation problem: How many pairwise disjoint compact convex sets in the plane are required to guarantee that one can be separated by a line from k others? (Denote this number by f _k .) A new proof was provided that f ₂=5, a result originally obtained by Tverberg himself, and the application of allowable interval sequences to the case of general k was left as an open problem. Hope and Katchalski, using other methods, proved in 1990 that 3k?1≤f _k ≤12(k?1). In this paper, we apply the method of allowable interval sequences to give an upper bound on f _k of under 7.2(k?1), shrinking the range given by Hope and Katchalski by more than half. For a family of translates we obtain a tighter upper bound of approximately 5.8(k?1).     

Cell Decompositions of the Projective Plane with Petrie Polygons of Constant Length

We study dual pairs of combinatorial face-to-face cell decompositions of the real projective plane P ² such that their canonically induced cell decompositions on the 2-sphere S ² form dual pairs of combinatorical types of convex polyhedra, and such that these dual pairs share two natural properties with those induced by dual pairs of Platonic solids: (1) Every Petrie polygon is a finite simple closed polygon of length 2(n-1) for some fixed n. (2) Every pair of Petrie polygons has precisely two common edges. Such pairs of face-to-face cell decompositions of the projective plane are in one-to-one correspondence with n-element pseudoline arrangements. We study in particular those dual pairs of cell decompositions in which has only 3-valent vertices, i.e., via the above one-to-one correspondence: p ₃-maximal pseudoline arrangements. A p ₃ -maximal pseudoline arrangement with n elements in turn determines a neighborly 2-manifold with Euler characteristic χ = n(7-n)/6, and vice versa, this neighborly 2-manifold uniquely determines its generating p ₃ -maximal pseudoline arrangement. We provide new inductive constructions for finding infinite example classes of p ₃-maximal pseudoline arrangements from small existing ones, we describe an algorithm for generating them, we provide a complete list of existence up to n = 40, and we discuss their properties. Received July 18, 1996, and in revised form October 28, 1996.     

Primitive Illumination Systems for Families of Convex Bodies in the Plane

Let F= {C₁,C₂,...,C} be a family of ndisjoint convex bodies in the plane. We say that a set Vof exterior light sources illuminates F, if for every boundary point of any member of Fthere is a point in Vsuch that is visible from ,i.e. the open line segment joining and is disjoint from F. An illumination system Vis called primitive if no proper subset of Villuminates F. Let p_max(F) denote the maximum number of points forming a primitive illumination system for F, and letp_max(n) denote the minimum of F) taken over all families Fconsisting of ndisjoint convex bodies in the plane. The aim of this paper is to investigate the quantities p_max(F) and p_max(n).     

Convex Sets in the Plane with Three of Every Four Meeting

Dedicated to the memory of Paul Erdős Suppose we have a finite collection of closed convex sets in the plane, (which without loss of generality we can take to be polygons). Suppose further that among any four of them, some three have non-empty intersection. We show that 13 points are sufficient to meet every one of the convex sets. Received October 27, 1999/Revised April 11, 2000 RID="*" ID="*" Supported by grant OTKA-T-029074. RID="†" ID="†" Supported by NSF grant DMS-99-70071, OTKA-T-020914 and OTKA-F-22234.