اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAlgorithms for Subpath Convex Hull Queries and Ray-Shooting Among Segments
83
0
0.0
(
0
)
تأليف
Haitao Wang
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper, we first consider the subpath convex hull query problem: Given a simple path $pi$ of $n$ vertices, preprocess it so that the convex hull of any query subpath of $pi$ can be quickly obtained. Previously, Guibas, Hershberger, and Snoeyink [SODA 90] proposed a data structure of $O(n)$ space and $O(log nloglog n)$ query time; reducing the query time to $O(log n)$ increases the space to $O(nloglog n)$. We present an improved result that uses $O(n)$ space while achieving $O(log n)$ query time. Like the previous work, our query algorithm returns a compact interval tree representing the convex hull so that standard binary-search-based queries on the hull can be performed in $O(log n)$ time each. Our new result leads to improvements for several other problems. In particular, with the help of the above result, we present new algorithms for the ray-shooting problem among segments. Given a set of $n$ (possibly intersecting) line segments in the plane, preprocess it so that the first segment hit by a query ray can be quickly found. We give a data structure of $O(nlog n)$ space that can answer each query in $(sqrt{n}log n)$ time. If the segments are nonintersecting or if the segments are lines, then the space can be reduced to $O(n)$. All these are classical problems that have been studied extensively. Previously data structures of $widetilde{O}(sqrt{n})$ query time (the notation $widetilde{O}$ suppresses a polylogarithmic factor) were known in early 1990s; nearly no progress has been made for over two decades. For all problems, our results provide improvements by reducing the space of the data structures by at least a logarithmic factor while the preprocessing and query times are the same as before or even better.
قيم البحث
اقرأ أيضاً
The it Convex Hull Membership(CHM) problem is: Given a point $p$ and a subset $S$ of $n$ points in $mathbb{R}^m$, is $p in conv(S)$? CHM is not only a fundamental problem in Linear Programming, Computational Geometry, Machine Learning and Statistics,
it also serves as a query problem in many applications e.g. Topic Modeling, LP Feasibility, Data Reduction. The {it Triangle Algorithm} (TA) cite{kalantari2015characterization} either computes an approximate solution in the convex hull, or a separating hyperplane. The {it Spherical}-CHM is a CHM, where $p=0$ and each point in $S$ has unit norm. First, we prove the equivalence of exact and approxima
Given $n$ points in a $d$ dimensional Euclidean space, the Minimum Enclosing Ball (MEB) problem is to find the ball with the smallest radius which contains all $n$ points. We give a $O(ndQcal/sqrt{epsilon})$ approximation algorithm for producing an e
nclosing ball whose radius is at most $epsilon$ away from the optimum (where $Qcal$ is an upper bound on the norm of the points). This improves existing results using emph{coresets}, which yield a $O(nd/epsilon)$ greedy algorithm. Finding the Minimum Enclosing Convex Polytope (MECP) is a related problem wherein a convex polytope of a fixed shape is given and the aim is to find the smallest magnification of the polytope which encloses the given points. For this problem we present a $O(mndQcal/epsilon)$ approximation algorithm, where $m$ is the number of faces of the polytope. Our algorithms borrow heavily from convex duality and recently developed techniques in non-smooth optimization, and are in contrast with existing methods which rely on geometric arguments. In particular, we specialize the excessive gap framework of citet{Nesterov05a} to obtain our results.
Number Decision Diagrams (NDD) provide a natural finite symbolic representation for regular set of integer vectors encoded as strings of digit vectors (least or most significant digit first). The convex hull of the set of vectors represented by a NDD
is proved to be an effectively computable convex polyhedron.
Given a finite set of points $P subseteq mathbb{R}^d$, we would like to find a small subset $S subseteq P$ such that the convex hull of $S$ approximately contains $P$. More formally, every point in $P$ is within distance $epsilon$ from the convex hul
l of $S$. Such a subset $S$ is called an $epsilon$-hull. Computing an $epsilon$-hull is an important problem in computational geometry, machine learning, and approximation algorithms. In many real world applications, the set $P$ is too large to fit in memory. We consider the streaming model where the algorithm receives the points of $P$ sequentially and strives to use a minimal amount of memory. Existing streaming algorithms for computing an $epsilon$-hull require $O(epsilon^{-(d-1)/2})$ space, which is optimal for a worst-case input. However, this ignores the structure of the data. The minimal size of an $epsilon$-hull of $P$, which we denote by $text{OPT}$, can be much smaller. A natural question is whether a streaming algorithm can compute an $epsilon$-hull using only $O(text{OPT})$ space. We begin with lower bounds that show that it is not possible to have a single-pass streaming algorithm that computes an $epsilon$-hull with $O(text{OPT})$ space. We instead propose three relaxations of the problem for which we can compute $epsilon$-hulls using space near-linear to the optimal size. Our first algorithm for points in $mathbb{R}^2$ that arrive in random-order uses $O(log ncdot text{OPT})$ space. Our second algorithm for points in $mathbb{R}^2$ makes $O(log(frac{1}{epsilon}))$ passes before outputting the $epsilon$-hull and requires $O(text{OPT})$ space. Our third algorithm for points in $mathbb{R}^d$ for any fixed dimension $d$ outputs an $epsilon$-hull for all but $delta$-fraction of directions and requires $O(text{OPT} cdot log text{OPT})$ space.
We present algorithms for length-constrained maximum sum segment and maximum density segment problems, in particular, and the problem of finding length-constrained heaviest segments, in general, for a sequence of real numbers. Given a sequence of n r
eal numbers and two real parameters L and U (L <= U), the maximum sum segment problem is to find a consecutive subsequence, called a segment, of length at least L and at most U such that the sum of the numbers in the subsequence is maximum. The maximum density segment problem is to find a segment of length at least L and at most U such that the density of the numbers in the subsequence is the maximum. For the first problem with non-uniform width there is an algorithm with time and space complexities in O(n). We present an algorithm with time complexity in O(n) and space complexity in O(U). For the second problem with non-uniform width there is a combinatorial solution with time complexity in O(n) and space complexity in O(U). We present a simple geometric algorithm with the same time and space complexities. We extend our algorithms to respectively solve the length-constrained k maximum sum segments problem in O(n+k) time and O(max{U, k}) space, and the length-constrained $k$ maximum density segments problem in O(n min{k, U-L}) time and O(U+k) space. We present extensions of our algorithms to find all the length-constrained segments having user specified sum and density in O(n+m) and O(nlog (U-L)+m) times respectively, where m is the number of output. Previously, there was no known algorithm with non-trivial result for these problems. We indicate the extensions of our algorithms to higher dimensions. All the algorithms can be extended in a straight forward way to solve the problems with non-uniform width and non-uniform weight.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
