اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدProbing a Set of Trajectories to Maximize Captured Information
140
0
0.0
(
0
)
نشر من قبل
Dominik Michael Krupke
تاريخ النشر
2020
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We study a trajectory analysis problem we call the Trajectory Capture Problem (TCP), in which, for a given input set ${cal T}$ of trajectories in the plane, and an integer $kgeq 2$, we seek to compute a set of $k$ points (``portals) to maximize the total weight of all subtrajectories of ${cal T}$ between pairs of portals. This problem naturally arises in trajectory analysis and summarization. We show that the TCP is NP-hard (even in very special cases) and give some first approximation results. Our main focus is on attacking the TCP with practical algorithm-engineering approaches, including integer linear programming (to solve instances to provable optimality) and local search methods. We study the integrality gap arising from such approaches. We analyze our methods on different classes of data, including benchmark instances that we generate. Our goal is to understand the best performing heuristics, based on both solution time and solution quality. We demonstrate that we are able to compute provably optimal solutions for real-world instances.
قيم البحث
اقرأ أيضاً
Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functions that facilitates the efficient search for new materials and material properties. We prove invariance under isometries, continuity, and completeness i
n the generic case, which are necessary features for the reliable comparison of crystals. The proof of continuity integrates methods from discrete geometry and lattice theory, while the proof of generic completeness combines techniques from geometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and related inclusion-exclusion formulae. We have implemented the algorithm and describe its application to crystal structure prediction.
We study three covering problems in the plane. Our original motivation for these problems come from trajectory analysis. The first is to decide whether a given set of line segments can be covered by up to four unit-sized, axis-parallel squares. The s
econd is to build a data structure on a trajectory to efficiently answer whether any query subtrajectory is coverable by up to three unit-sized axis-parallel squares. The third problem is to compute a longest subtrajectory of a given trajectory that can be covered by up to two unit-sized axis-parallel squares.
We study subtrajectory clustering under the Frechet distance. Given one or more trajectories, the task is to split the trajectories into several parts, such that the parts have a good clustering structure. We approach this problem via a new set cover
formulation, which we think provides a natural formalization of the problem as it is studied in many applications. Given a polygonal curve $P$ with $n$ vertices in fixed dimension, integers $k$, $ell geq 1$, and a real value $Delta > 0$, the goal is to find $k$ center curves of complexity at most $ell$ such that every point on $P$ is covered by a subtrajectory that has small Frechet distance to one of the $k$ center curves ($leq Delta$). In many application scenarios, one is interested in finding clusters of small complexity, which is controlled by the parameter $ell$. Our main result is a tri-criterial approximation algorithm: if there exists a solution for given parameters $k$, $ell$, and $Delta$, then our algorithm finds a set of $k$ center curves of complexity at most $ell$ with covering radius $Delta$ with $k in O( k ell^2 log (k ell))$, $ellleq 2ell$, and $Deltaleq 19 Delta$. Moreover, within these approximation bounds, we can minimize $k$ while keeping the other parameters fixed. If $ell$ is a constant independent of $n$, then, the approximation factor for the number of clusters $k$ is $O(log k)$ and the approximation factor for the radius $Delta$ is constant. In this case, the algorithm has expected running time in $ tilde{O}left( k m^2 + mnright)$ and uses space in $O(n+m)$, where $m=lceilfrac{L}{Delta}rceil$ and $L$ is the total arclength of the curve $P$. For the important case of clustering with line segments ($ell$=2) we obtain bi-criteria approximation algorithms, where the approximation criteria are the number of clusters and the radius of the clustering.
This paper discusses the problem of covering and hitting a set of line segments $cal L$ in ${mathbb R}^2$ by a pair of axis-parallel squares such that the side length of the larger of the two squares is minimized. We also discuss the restricted versi
on of covering, where each line segment in $cal L$ is to be covered completely by at least one square. The proposed algorithm for the covering problem reports the optimum result by executing only two passes of reading the input data sequentially. The algorithm proposed for the hitting and restricted covering problems produces optimum result in $O(n)$ time. All the proposed algorithms are in-place, and they use only $O(1)$ extra space. The solution of these problems also give a $sqrt{2}$ approximation for covering and hitting those line segments $cal L$ by two congruent disks of minimum radius with same computational complexity.
We consider the problem of assigning radii to a given set of points in the plane, such that the resulting set of circles is connected, and the sum of radii is minimized. We show that the problem is polynomially solvable if a connectivity tree is give
n. If the connectivity tree is unknown, the problem is NP-hard if there are upper bounds on the radii and open otherwise. We give approximation guarantees for a variety of polynomial-time algorithms, describe upper and lower bounds (which are matching in some of the cases), provide polynomial-time approximation schemes, and conclude with experimental results and open problems.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
