论文标题
在$ d $ dimensions中近似离散和连续的中间线段
Approximating the discrete and continuous median line segments in $d$ dimensions
论文作者
论文摘要
考虑$ \ Mathbb {r}^d $中的$ n $点的$ p $。在离散的中间线段问题中，目标是找到一个以$ p $中的点为界的线段，以便将欧几里得距离的总和从$ p $到线段的距离的总和最小化。在连续的中间线段问题中，给出了一个实数$ \ ell> 0 $，目标是在$ \ mathbb {r}^d $中找到一个长度$ \ ell $的行段，以使$ p $之间的欧几里得距离之和最小。 我们展示了如何计算$（1+εδ）$ - 和$（1+ε）$ - 分别与时间$ O（Nε^{ - 2D} \ log n）$和$ O（N^2ε^{ - d}）$的离散线中间线段的近似值，分别是$δ$，其中$δ$是$δ$，其中$δ$是点sprif ables bigess bic bigts bigess aviakes spiairs。在开发算法时，通过使用配对分解的原理，我们得出了新的数据结构，使我们可以快速近似从一组点到给定的线段或点的距离之和。据我们所知，我们对解决Minsum设施位置问题的利用是第一个同类。它是通用且易于实现的。 我们证明，仅使用尺子和指南针，无法在飞机上为$ n \ geq3 $非校准点构建连续的中间线段。鉴于此，我们提出了一个$ o（n^dε^{ - d}）$ - 时间算法，用于近似于$ \ mathbb {r}^d $中的连续中间线段，以内$ 1+ε$。该算法基于从离散到连续域的点段对分解。最后但并非最不重要的一点是，我们给出了$（1+ε）$ - 近似算法，其时间复杂性在$ n $中是子季节，用于求解$ \ mathbb {r}^2 $中的约束中间线段问题，其中端点或中位线段的斜率在输入处给出。
Consider a set $P$ of $n$ points in $\mathbb{R}^d$. In the discrete median line segment problem, the objective is to find a line segment bounded by a pair of points in $P$ such that the sum of the Euclidean distances from $P$ to the line segment is minimized. In the continuous median line segment problem, a real number $\ell>0$ is given, and the goal is to locate a line segment of length $\ell$ in $\mathbb{R}^d$ such that the sum of the Euclidean distances between $P$ and the line segment is minimized. We show how to compute $(1+εΔ)$- and $(1+ε)$-approximations to a discrete median line segment in time $O(nε^{-2d}\log n)$ and $O(n^2ε^{-d})$, respectively, where $Δ$ is the spread of line segments spanned by pairs of points. While developing our algorithms, by using the principle of pair decomposition, we derive new data structures that allow us to quickly approximate the sum of the distances from a set of points to a given line segment or point. To our knowledge, our utilization of pair decompositions for solving minsum facility location problems is the first of its kind; it is versatile and easily implementable. We prove that it is impossible to construct a continuous median line segment for $n\geq3$ non-collinear points in the plane by using only ruler and compass. In view of this, we present an $O(n^dε^{-d})$-time algorithm for approximating a continuous median line segment in $\mathbb{R}^d$ within a factor of $1+ε$. The algorithm is based upon generalizing the point-segment pair decomposition from the discrete to the continuous domain. Last but not least, we give an $(1+ε)$-approximation algorithm, whose time complexity is sub-quadratic in $n$, for solving the constrained median line segment problem in $\mathbb{R}^2$ where an endpoint or the slope of the median line segment is given at input.
