20.500.12556/DiRROS-18407 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 and independently considered by Dupin, Nielsen and Talbi 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 false Angleški jezik Ni določen Neznano 2024-03-15 09:17:04 2024-03-15 09:17:05 2024-03-16 03:37:14 0000-00-00 00:00:00 2023 0 0 Spletna objava: 16. 3. 2023; str. 441-466 iss. 2 Vol. 86 June 2023 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2023-06-01 004.9:519.8 0925-5001 10.1007/s10898-023-01280-1 145465859 https://link.springer.com/article/10.1007/s10898-023-01280-1 1 69e8abb2-e2a4-11ee-9dd4-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=25066 s10898-023-01280-1-1.pdf s10898-023-01280-1-1.pdf 1 6B274F3D80C2B0EF1B0EF7D70DB07F8A fd596ede1c23d4e2a05dc327feb74b2a13a4aac921f6c88fdf207edf6ef32b2e a098b48a-e2a4-11ee-9dd4-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=25067 Inštitut za matematiko, fiziko in mehaniko 0 0 0