اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدUniversal Guard Problems
33
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We provide a spectrum of results for the Universal Guard Problem, in which one is to obtain a small set of points (guards) that are universal in their ability to guard any of a set of possible polygonal domains in the plane. We give upper and lower bounds on the number of universal guards that are always sufficient to guard all polygons having a given set of n vertices, or to guard all polygons in a given set of k polygons on an n-point vertex set. Our upper bound proofs include algorithms to construct universal guard sets of the respective cardinalities.
قيم البحث
اقرأ أيضاً
In the metric multi-cover problem (MMC), we are given two point sets $Y$ (servers) and $X$ (clients) in an arbitrary metric space $(X cup Y, d)$, a positive integer $k$ that represents the coverage demand of each client, and a constant $alpha geq 1$.
Each server can have a single ball of arbitrary radius centered on it. Each client $x in X$ needs to be covered by at least $k$ such balls centered on servers. The objective function that we wish to minimize is the sum of the $alpha$-th powers of the radii of the balls. In this article, we consider the MMC problem as well as some non-trivial generalizations, such as (a) the non-uniform MMC, where we allow client-specific demands, and (b) the $t$-MMC, where we require the number of open servers to be at most some given integer $t$. For each of these problems, we present an efficient algorithm that reduces the problem to several instances of the corresponding $1$-covering problem, where the coverage demand of each client is $1$. Our reductions preserve optimality up to a multiplicative constant factor. Applying known constant factor approximation algorithms for $1$-covering, we obtain the first constant approximations for the MMC and these generalizations.
We study a simple reconfigurable robot model which has not been previously examined: cubic robots comprised of three-dimensional cubic modules which can slide across each other and rotate about each others edges. We demonstrate that the cubic robot m
odel is universal, i.e., that an n-module cubic robot can reconfigure itself into any specified n-module configuration. Additionally, we provide an algorithm that efficiently plans and executes cubic robot motion. Our results directly extend to a d-dimensional model.
In this article, we consider a collection of geometric problems involving points colored by two colors (red and blue), referred to as bichromatic problems. The motivation behind studying these problems is two fold; (i) these problems appear naturally
and frequently in the fields like Machine learning, Data mining, and so on, and (ii) we are interested in extending the algorithms and techniques for single point set (monochromatic) problems to bichromatic case. For all the problems considered in this paper, we design low polynomial time exact algorithms. These algorithms are based on novel techniques which might be of independent interest.
We give both efficient algorithms and hardness results for reconfiguring between two connected configurations of modules in the hexagonal grid. The reconfiguration moves that we consider are pivots, where a hexagonal module rotates around a vertex sh
ared with another module. Following prior work on modular robots, we define two natural sets of hexagon pivoting moves of increasing power: restricted and monkey moves. When we allow both moves, we present the first universal reconfiguration algorithm, which transforms between any two connected configurations using $O(n^3)$ monkey moves. This result strongly contrasts the analogous problem for squares, where there are rigid examples that do not have a single pivoting move preserving connectivity. On the other hand, if we only allow restricted moves, we prove that the reconfiguration problem becomes PSPACE-complete. Moreover, we show that, in contrast to hexagons, the reconfiguration problem for pivoting squares is PSPACE-complete regardless of the set of pivoting moves allowed. In the process, we strengthen the reduction framework of Demaine et al. [FUN18] that we consider of independent interest.
We present improved universal covers for carpenters rule folding in the plane.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
