What Is the Center Selection Problem in Geometry?

[zak100]

TL;DR

I am trying to understand the center selection problem but I have some problems in understanding the fundamental things.

Hi
I have some questions about the center selection problem:
1) K= 4, Are we finding the center of 4 circles?
2) r(C) = maxi dist(si, C) = smallest covering radius.
In case of r(C), I can’t understand what is meant by $max_i dist(s_i, C)$
How the max will work?

Some body please guide me.

Zulfi.

 

[DrClaude]

1) K= 4, Are we finding the center of 4 circles?

Yes, if $k=4$ you need to find the center of 4 circles. $k$ is the number of centers, so the number of circles.

2) r(C) = maxi dist(si, C) = smallest covering radius.
In case of r(C), I can’t understand what is meant by $max_i dist(s_i, C)$
How the max will work?

The function $\mathrm{dist}(s_i, C)$ should return the distance between site $s_i$ and the nearest center $C$. Then you find the maximum of all the distances thus calculated, and that becomes $r(C)$. The task is then to find where to place the centers to minimize $r(C)$.

Note that in the picture, $\max_i \mathrm{dist}(s_i, C)$ corresponds to two sites from the upper left circle, where you have sites just on the edge of the circle.

 

[zak100]

Hi,
Thanks for your response.
<Then you find the maximum of all the distances thus calculated, and that becomes r(C).>
(1)How may distances are returned by $dist(s_i, C) ?$
(2)Why we don't find the minimum distance directly from the value return by the distance function?
Book says:

<
we define the distance of a site s to the centers as $dist(s, C) = min_{c∈C} dist(s, c)$.
We say that C forms an r-cover if each site is within distance at most r from one of the centers—that is, if dist(s, C) ≤ r for all sites s ∈ S. The minimum r for which C is an r-cover will be called the covering radius of C and will be denoted by r(C). In other words, the covering radius of a set of centers C is the farthest that anyone needs to travel to get to his or her nearest center.>

Kleinberg, Jon. Algorithm Design (p. 607). Pearson Education. Kindle Edition.
(3)What is the difference between 'c' and 'C'?
(4)The function $dist(s_i,C) \text{ should return the distance between site } s_i$ and the nearest center C.
Sorry I can't understand the sentence $\text{"between the site } s_i \text{ and the nearest center C" }$. Are we considering the point within the site or on the edge?
(5)Why the book uses the word "farthest" if we are interested in finding out the closest distance.
Some body please guide me.
Zulfi.

 

[DrClaude]

(1)How may distances are returned by $dist(s_i, C) ?$

One. As the book itself says, you have $dist(s_i, C) = min_{c \in C} dist(s_i, c)$.

(2)Why we don't find the minimum distance directly from the value return by the distance function?

I'm not sure what you are asking here. Yes, $dist(s_i, C)$ is found as the minimum distance. But the work here is to optimize $C$ such that $max_i dist(s_i, C)$ is minimum.

(3)What is the difference between 'c' and 'C'?

$c$ is one center while $C$ is the set of all centers.

(4)The function $dist(s_i,C) \text{ should return the distance between site } s_i$ and the nearest center C.
Sorry I can't understand the sentence $\text{"between the site } s_i \text{ and the nearest center C" }$. Are we considering the point within the site or on the edge?

This is simply a reformulation of $dist(s_i, C) = min_{c \in C} dist(s_i, c)$. You need a function $dist(s_i, C)$ that will calculate the distance between $s_i$ and all the centers, and return the smallest of these values, which is then simply the distance between $s_i$ and the nearest center.

(5)Why the book uses the word "farthest" if we are interested in finding out the closest distance.

Because you are minimizing a maximum. You want the smallest possible travel distance for the site that is farthest away from its nearest center.

 

[zak100]

Hi,

Thanks. God bless you.

Zulfi.