ﻻ يوجد ملخص باللغة العربية
In the classic polyline simplification problem we want to replace a given polygonal curve $P$, consisting of $n$ vertices, by a subsequence $P$ of $k$ vertices from $P$ such that the polygonal curves $P$ and $P$ are as close as possible. Closeness is usually measured using the Hausdorff or Frechet distance. These distance measures can be applied globally, i.e., to the whole curves $P$ and $P$, or locally, i.e., to each simplified subcurve and the line segment that it was replaced with separately (and then taking the maximum). This gives rise to four problem variants: Global-Hausdorff (known to be NP-hard), Local-Hausdorff (in time $O(n^3)$), Global-Frechet (in time $O(k n^5)$), and Local-Frechet (in time $O(n^3)$). Our contribution is as follows. - Cubic time for all variants: For Global-Frechet we design an algorithm running in time $O(n^3)$. This shows that all three problems (Local-Hausdorff, Local-Frechet, and Global-Frechet) can be solved in cubic time. All these algorithms work over a general metric space such as $(mathbb{R}^d,L_p)$, but the hidden constant depends on $p$ and (linearly) on $d$. - Cubic conditional lower bound: We provide evidence that in high dimensions cubic time is essentially optimal for all three problems (Local-Hausdorff, Local-Frechet, and Global-Frechet). Specifically, improving the cubic time to $O(n^{3-epsilon} textrm{poly}(d))$ for polyline simplification over $(mathbb{R}^d,L_p)$ for $p = 1$ would violate plausible conjectures. We obtain similar results for all $p in [1,infty), p e 2$. In total, in high dimensions and over general $L_p$-norms we resolve the complexity of polyline simplification with respect to Local-Hausdorff, Local-Frechet, and Global-Frechet, by providing new algorithms and conditional lower bounds.
In this article, we provide new structural results and algorithms for the Homotopy Height problem. In broad terms, this problem quantifies how much a curve on a surface needs to be stretched to sweep continuously between two positions. More precisely
We study the problem of polygonal curve simplification under uncertainty, where instead of a sequence of exact points, each uncertain point is represented by a region, which contains the (unknown) true location of the vertex. The regions we consider
Simplification is one of the fundamental operations used in geoinformation science (GIS) to reduce size or representation complexity of geometric objects. Although different simplification methods can be applied depending on ones purpose, a simplific
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
Sentence simplification is the task of rewriting texts so they are easier to understand. Recent research has applied sequence-to-sequence (Seq2Seq) models to this task, focusing largely on training-time improvements via reinforcement learning and mem