اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدGeometric Systems of Unbiased Representatives
42
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $P$ be a set of points in $mathbb{R}^d$, $B$ a bicoloring of $P$ and $Oo$ a family of geometric objects (that is, intervals, boxes, balls, etc). An object from $Oo$ is called balanced with respect to $B$ if it contains the same number of points from each color of $B$. For a collection $B$ of bicolorings of $P$, a geometric system of unbiased representatives (G-SUR) is a subset $OosubseteqOo$ such that for any bicoloring $B$ of $B$ there is an object in $Oo$ that is balanced with respect to $B$. We study the problem of finding G-SURs. We obtain general bounds on the size of G-SURs consisting of intervals, size-restricted intervals, axis-parallel boxes and Euclidean balls. We show that the G-SUR problem is NP-hard even in the simple case of points on a line and interval ranges. Furthermore, we study a related problem on determining the size of the largest and smallest balanced intervals for points on the real line with a random distribution and coloring. Our results are a natural extension to a geometric context of the work initiated by Balachandran et al. on arbitrary systems of unbiased representatives.
قيم البحث
اقرأ أيضاً
Efficient algorithms are presented for constructing spanners in geometric intersection graphs. For a unit ball graph in R^k, a (1+epsilon)-spanner is obtained using efficient partitioning of the space into hypercubes and solving bichromatic closest p
air problems. The spanner construction has almost equivalent complexity to the construction of Euclidean minimum spanning trees. The results are extended to arbitrary ball graphs with a sub-quadratic running time. For unit ball graphs, the spanners have a small separator decomposition which can be used to obtain efficient algorithms for approximating proximity problems like diameter and distance queries. The results on compressed quadtrees, geometric graph separators, and diameter approximation might be of independent interest.
We study several natural instances of the geometric hitting set problem for input consisting of sets of line segments (and rays, lines) having a small number of distinct slopes. These problems model path monitoring (e.g., on road networks) using the
fewest sensors (the hitting points). We give approximation algorithms for cases including (i) lines of 3 slopes in the plane, (ii) vertical lines and horizontal segments, (iii) pairs of horizontal/vertical segments. We give hardness and hardness of approximation results for these problems. We prove that the hitting set problem for vertical lines and horizontal rays is polynomially solvable.
For smooth convex disks $A$, i.e., convex compact subsets of the plane with non-empty interior, we classify the classes $G^{text{hom}}(A)$ and $G^{text{sim}}(A)$ of intersection graphs that can be obtained from homothets and similarities of $A$, resp
ectively. Namely, we prove that $G^{text{hom}}(A)=G^{text{hom}}(B)$ if and only if $A$ and $B$ are affine equivalent, and $G^{text{sim}}(A)=G^{text{sim}}(B)$ if and only if $A$ and $B$ are similar.
We consider paths with low emph{exposure} to a 2D polygonal domain, i.e., paths which are seen as little as possible; we differentiate between emph{integral} exposure (when we care about how long the path sees every point of the domain) and emph{0/1}
exposure (just counting whether a point is seen by the path or not). For the integral exposure, we give a PTAS for finding the minimum-exposure path between two given points in the domain; for the 0/1 version, we prove that in a simple polygon the shortest path has the minimum exposure, while in domains with holes the problem becomes NP-hard. We also highlight connections of the problem to minimum satisfiability and settle hardness of variants of planar min- and max-SAT.
We study four classical graph problems -- Hamiltonian path, Traveling salesman, Minimum spanning tree, and Minimum perfect matching on geometric graphs induced by bichromatic (red and blue) points. These problems have been widely studied for points i
n the Euclidean plane, and many of them are NP-hard. In this work, we consider these problems in two restricted settings: (i) collinear points and (ii) equidistant points on a circle. We show that almost all of these problems can be solved in linear time in these constrained, yet non-trivial settings.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
