论文标题
基于距离的代表天际线和飞机沿帕累托前沿的$ k $中心
Faster Distance-Based Representative Skyline and $k$-Center Along Pareto Front in the Plane
论文作者
论文摘要
我们考虑了在平面中计算\ emph {基于距离的代表天际线}的问题，这是陶，丁，林和pei引入的问题[proc。第25届IEEE国际数据工程会议（ICDE），2009年]，并在多目标优化的背景下由杜平，尼尔森和塔尔比（Optimization and Learning）独立考虑。给定飞机上的$ n $点的$ p $和参数$ k $，其任务是选择由$ p $定义的天际线的$ k $点（也称为$ p $的帕托阵线），以最大程度地减少从天际线到所选点的最大距离。我们表明，问题可以在$ o（n \ log h）$时间中解决，其中$ h $是$ p $的天际线的点数。我们还表明，可以在$ O（n \ log k）$时间中解决决策问题，并且可以在$ o（n \ log k + n \ operatatorName {loglog} n）$ time中解决优化问题。这改善了以前的算法，对于$ k $的大量值是最佳的。
We consider the problem of computing the \emph{distance-based representative skyline} in the plane, a problem introduced by Tao, Ding, Lin and Pei [Proc. 25th IEEE International Conference on Data Engineering (ICDE), 2009] and independently considered by Dupin, Nielsen and Talbi [Optimization and Learning - Third International Conference, OLA 2020] in the context of multi-objective optimization. Given a set $P$ of $n$ points in the plane and a parameter $k$, the task is to select $k$ points of the skyline defined by $P$ (also known as Pareto front for $P$) to minimize the maximum distance from the points of the skyline to the selected points. We show that the problem can be solved in $O(n\log h)$ time, where $h$ is the number of points in the skyline of $P$. We also show that the decision problem can be solved in $O(n\log k)$ time and the optimization problem can be solved in $O(n \log k + n \operatorname{loglog} n)$ time. This improves previous algorithms and is optimal for a large range of values of $k$.
