  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$.

Computational Geometry;Databases;Data Structures and Algorithms;Optimization and Control