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. To begin with, we show how to compute $(1+\epsilon\Delta)$- and $(1+\epsilon)$-approximations to a discrete median line segment in time $O(n\epsilon^{-2d}\log n)$ and $O(n^2\epsilon^{-d})$, respectively, where $\Delta$ 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. Furthermore, 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\epsilon^{-d})$-time algorithm for approximating a continuous median line segment in $\mathbb{R}^d$ within a factor of $1+\epsilon$. 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+\epsilon)$-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.
翻译:以 $mathb{R ⁇ d$ 设定 $ P$ 的立方 。 在离散的中位线段问题中, 目标是找到一个由一对点( $P) 捆绑的线性路段, 这样可以最小化Euclidean 从美元到线段的距离之和。 在连续的中位线段问题中, 给出了一个真实的数值 $ell>%0, 目标是找到一条长度为美元( $) 的线段, 但以美元为单位 。 在离散的中位线段中, 美元和线段的距离之和 美元, 开始显示如何将美元( 1 ⁇ silon\ delta) 的距离和 美元( 1\ ipsilon) 匹配到一个离散的中位线段 $( ==xxxxxxxxxxxxxxxxl) 。 美元规则的直线路段的分布将我们直线段的分布为直径直径, 的离线段, 以固定的平地段的平地段为固定的离点, 数据是固定的平地段 。