20.500.12556/RUL-147583 Faster distance-based representative skyline and k-center along pareto front in the plane We consider the problem of computing the 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 [Mathematics; 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 \log\log n)$ time. This improves previous algorithms and is optimal for a large range of values of $k$. geometric optimization skyline pareto front clustering k-center true false true Angleški jezik Ni določen Članek v reviji 2023-07-07 15:29:51 2023-07-07 15:29:54 2023-07-08 03:51:35 0000-00-00 00:00:00 2023 0 0 Str. 441-466 iss. 2 Vol. 86 Jun. 2023 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.9:519.8 0925-5001 10.1007/s10898-023-01280-1 145465859 s10898-023-01280-1.pdf s10898-023-01280-1.pdf 1 472AFBE293785604864B0708AB3BCBE2 12d82d84e67574d1cbe74e97b818f796bfd67ccb6ba4f0345fa38485792db906 84189b67-1cca-11ee-a314-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=171236 https://link.springer.com/article/10.1007/s10898-023-01280-1 1 ef85065f-1cc9-11ee-a314-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=171235 Fakulteta za matematiko in fiziko 0 0 0