<p>Given a set of n points in 3d space and an integer k, it is NP-hard to select k points from the skyline to maximize the number of points dominated by them. Is it still NP-hard to select k points form the skyline to minimize the number of points dominated by them?</p>

CC BY-SA 4.0
2024-05-17T11:07:43.717Z
This question needs some context. What is a “skyline”? What does it mean to “dominate”?
Emil Jeřábek
CC BY-SA 4.0
2024-05-19T06:13:38.003Z
A point t is said to dominate another point s, if for each i, t[i] is less then s[i]. The skyline of a set of points is the set of points that are not dominated by any other point.
tics
<np-hardness>
Minimize the dominating points
tics
# Minimize the dominating points

(Asked by: username_0 on 2024-05-17)

Given a set of n points in 3d space and an integer k, it is NP-hard to select k points from the skyline to maximize the number of points dominated by them. Is it still NP-hard to select k points form the skyline to minimize the number of points dominated by them?

**Tags:** np-hardness

> **Comments:**
> **username_1**: This question needs some context. What is a “skyline”? What does it mean to “dominate”?  
> **username_0**: A point t is said to dominate another point s, if for each i, t[i] is less then s[i]. The skyline of a set of points is the set of points that are not dominated by any other point.  

---

## 0 answers

