اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدApproximating the volume of unions and intersections of high-dimensional geometric objects
49
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We consider the computation of the volume of the union of high-dimensional geometric objects. While showing that this problem is #P-hard already for very simple bodies (i.e., axis-parallel boxes), we give a fast FPRAS for all objects where one can: (1) test whether a given point lies inside the object, (2) sample a point uniformly, (3) calculate the volume of the object in polynomial time. All three oracles can be weak, that is, just approximate. This implies that Klees measure problem and the hypervolume indicator can be approximated efficiently even though they are #P-hard and hence cannot be solved exactly in time polynomial in the number of dimensions unless P=NP. Our algorithm also allows to approximate efficiently the volume of the union of convex bodies given by weak membership oracles. For the analogous problem of the intersection of high-dimensional geometric objects we prove #P-hardness for boxes and show that there is no multiplicative polynomial-time $2^{d^{1-epsilon}}$-approximation for certain boxes unless NP=BPP, but give a simple additive polynomial-time $epsilon$-approximation.
قيم البحث
اقرأ أيضاً
Compressed bitmap indexes are used to speed up simple aggregate queries in databases. Indeed, set operations like intersections, unions and complements can be represented as logical operations (AND,OR,NOT) that are ideally suited for bitmaps. However
, it is less obvious how to apply bitmaps to more advanced queries. For example, we might seek products in a store that meet some, but maybe not all, criteria. Such threshold queries generalize intersections and unions; they are often used in information-retrieval and data-mining applications. We introduce new algorithms that are sometimes three orders of magnitude faster than a naive approach. Our work shows that bitmap indexes are more broadly applicable than is commonly believed.
We give a polynomial-time constant-factor approximation algorithm for maximum independent set for (axis-aligned) rectangles in the plane. Using a polynomial-time algorithm, the best approximation factor previously known is $O(loglog n)$. The results
are based on a new form of recursive partitioning in the plane, in which faces that are constant-complexity and orthogonally convex are recursively partitioned into a constant number of such faces.
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 f
rom 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.
The Euclidean $k$-center problem is a classical problem that has been extensively studied in computer science. Given a set $mathcal{G}$ of $n$ points in Euclidean space, the problem is to determine a set $mathcal{C}$ of $k$ centers (not necessarily p
art of $mathcal{G}$) such that the maximum distance between a point in $mathcal{G}$ and its nearest neighbor in $mathcal{C}$ is minimized. In this paper we study the corresponding $(k,ell)$-center problem for polygonal curves under the Frechet distance, that is, given a set $mathcal{G}$ of $n$ polygonal curves in $mathbb{R}^d$, each of complexity $m$, determine a set $mathcal{C}$ of $k$ polygonal curves in $mathbb{R}^d$, each of complexity $ell$, such that the maximum Frechet distance of a curve in $mathcal{G}$ to its closest curve in $mathcal{C}$ is minimized. In this paper, we substantially extend and improve the known approximation bounds for curves in dimension $2$ and higher. We show that, if $ell$ is part of the input, then there is no polynomial-time approximation scheme unless $mathsf{P}=mathsf{NP}$. Our constructions yield different bounds for one and two-dimensional curves and the discrete and continuous Frechet distance. In the case of the discrete Frechet distance on two-dimensional curves, we show hardness of approximation within a factor close to $2.598$. This result also holds when $k=1$, and the $mathsf{NP}$-hardness extends to the case that $ell=infty$, i.e., for the problem of computing the minimum-enclosing ball under the Frechet distance. Finally, we observe that a careful adaptation of Gonzalez algorithm in combination with a curve simplification yields a $3$-approximation in any dimension, provided that an optimal simplification can be computed exactly. We conclude that our approximation bounds are close to being tight.
Graph drawing addresses the problem of finding a layout of a graph that satisfies given aesthetic and understandability objectives. The most important objective in graph drawing is minimization of the number of crossings in the drawing, as the aesthe
tics and readability of graph drawings depend on the number of edge crossings. VLSI layouts with fewer crossings are more easily realizable and consequently cheaper. A straight-line drawing of a planar graph G of n vertices is a drawing of G such that each edge is drawn as a straight-line segment without edge crossings. However, a problem with current graph layout methods which are capable of producing satisfactory results for a wide range of graphs is that they often put an extremely high demand on computational resources. This paper introduces a new layout method, which nicely draws internally convex of planar graph that consumes only little computational resources and does not need any heavy duty preprocessing. Here, we use two methods: The first is self organizing map known from unsupervised neural networks which is known as (SOM) and the second method is Inverse Self Organized Map (ISOM).
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
