اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRainbow polygons for colored point sets in the plane
93
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Given a colored point set in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color, either in its interior or on its boundary. Let $operatorname{rb-index}(S)$ denote the smallest size of a perfect rainbow polygon for a colored point set $S$, and let $operatorname{rb-index}(k)$ be the maximum of $operatorname{rb-index}(S)$ over all $k$-colored point sets in general position; that is, every $k$-colored point set $S$ has a perfect rainbow polygon with at most $operatorname{rb-index}(k)$ vertices. In this paper, we determine the values of $operatorname{rb-index}(k)$ up to $k=7$, which is the first case where $operatorname{rb-index}(k) eq k$, and we prove that for $kge 5$, [ frac{40lfloor (k-1)/2 rfloor -8}{19} %Birgit: leqoperatorname{rb-index}(k)leq 10 bigglfloorfrac{k}{7}biggrfloor + 11. ] Furthermore, for a $k$-colored set of $n$ points in the plane in general position, a perfect rainbow polygon with at most $10 lfloorfrac{k}{7}rfloor + 11$ vertices can be computed in $O(nlog n)$ time.
قيم البحث
اقرأ أيضاً
We consider the construction of a polygon $P$ with $n$ vertices whose turning angles at the vertices are given by a sequence $A=(alpha_0,ldots, alpha_{n-1})$, $alpha_iin (-pi,pi)$, for $iin{0,ldots, n-1}$. The problem of realizing $A$ by a polygon ca
n be seen as that of constructing a straight-line drawing of a graph with prescribed angles at vertices, and hence, it is a special case of the well studied problem of constructing an emph{angle graph}. In 2D, we characterize sequences $A$ for which every generic polygon $Psubset mathbb{R}^2$ realizing $A$ has at least $c$ crossings, for every $cin mathbb{N}$, and describe an efficient algorithm that constructs, for a given sequence $A$, a generic polygon $Psubset mathbb{R}^2$ that realizes $A$ with the minimum number of crossings. In 3D, we describe an efficient algorithm that tests whether a given sequence $A$ can be realized by a (not necessarily generic) polygon $Psubset mathbb{R}^3$, and for every realizable sequence the algorithm finds a realization.
Let $S$ be a finite set of geometric objects partitioned into classes or emph{colors}. A subset $Ssubseteq S$ is said to be emph{balanced} if $S$ contains the same amount of elements of $S$ from each of the colors. We study several problems on partit
ioning $3$-colored sets of points and lines in the plane into two balanced subsets: (a) We prove that for every 3-colored arrangement of lines there exists a segment that intersects exactly one line of each color, and that when there are $2m$ lines of each color, there is a segment intercepting $m$ lines of each color. (b) Given $n$ red points, $n$ blue points and $n$ green points on any closed Jordan curve $gamma$, we show that for every integer $k$ with $0 leq k leq n$ there is a pair of disjoint intervals on $gamma$ whose union contains exactly $k$ points of each color. (c) Given a set $S$ of $n$ red points, $n$ blue points and $n$ green points in the integer lattice satisfying certain constraints, there exist two rays with common apex, one vertical and one horizontal, whose union splits the plane into two regions, each one containing a balanced subset of $S$.
K{a}rolyi, Pach, and T{o}th proved that every 2-edge-colored straight-line drawing of the complete graph contains a monochromatic plane spanning tree. It is open if this statement generalizes to other classes of drawings, specifically, to simple draw
ings of the complete graph. These are drawings where edges are represented by Jordan arcs, any two of which intersect at most once. We present two partial results towards such a generalization. First, we show that the statement holds for cylindrical simple drawings. (In a cylindrical drawing, all vertices are placed on two concentric circles and no edge crosses either circle.) Second, we introduce a relaxation of the problem in which the graph is $k$-edge-colored, and the target structure must be hypochromatic, that is, avoid (at least) one color class. In this setting, we show that every $lceil (n+5)/6rceil$-edge-colored monotone simple drawing of $K_n$ contains a hypochromatic plane spanning tree. (In a monotone drawing, every edge is represented as an $x$-monotone curve.)
We give an overview of the 2020 Computational Geometry Challenge, which targeted the problem of partitioning the convex hull of a given planar point set P into the smallest number of convex faces, such that no point of P is contained in the interior of a face.
We study several problems concerning convex polygons whose vertices lie in a Cartesian product (for short, grid) of two sets of n real numbers. First, we prove that every such grid contains a convex polygon with $Omega$(log n) vertices and that this
bound is tight up to a constant factor. We generalize this result to d dimensions (for a fixed d $in$ N), and obtain a tight lower bound of $Omega$(log d--1 n) for the maximum number of points in convex position in a d-dimensional grid. Second, we present polynomial-time algorithms for computing the largest convex chain in a grid that contains no two points of the same x-or y-coordinate. We show how to efficiently approximate the maximum size of a supported convex polygon up to a factor of 2. Finally, we present exponential bounds on the maximum number of convex polygons in these grids, and for some restricted variants. These bounds are tight up to polynomial factors.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
