Return to Question

I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ hyperspheres whose centers are the closest to $p$ under the Euclidean metric (although I'm eventually interested in exploring other metrics as well). So this is a discrete optimization problem where we are minimizing the maximum distance of an element in our set from $p$. However, the side constraint is that these hyperspheres cannot overlap with each other.

I am considering approximating the hyperspheres as axis-aligned hypercubes, but am not sure if this actually simplifies the problem.

I think this can be formulated as maximum weighted independent set (with a cardinality constraint) in a geometric intersection graph (more specifically a disk intersection graph), where the weights are the distance from $p$, and we have an adjacency matrix where $A_{i,j} = 1$ if $dist(S_i, S_j) < c$ for some constant $c$. I'm not sure if there is some other formulation I am missing. Is there a name for this problem?

I am also considering this from a probabilistic perspective, in the case where we can assume that the hyperspheres are uniformly distributed.

I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non overlapping hyperspheres whose centers are the closest to $p$ under the Euclidean metric (although I'm eventually interested in exploring other metrics as well). So this is a discrete optimization problem where we are minimizing the maximum distance of an element in our set from $p$. However, the side constraint is that these hyperspheres cannot overlap with each other.

I am considering approximating the hyperspheres as axis-aligned hypercubes, but am not sure if this actually simplifies the problem.

I think this can be formulated as maximum weighted independent set (with a cardinality constraint) in a geometric intersection graph (more specifically a disk intersection graph), where the weights are the distance from $p$, and we have an adjacency matrix where $A_{i,j} = 1$ if $dist(S_i, S_j) < c$ for some constant $c$. I'm not sure if there is some other formulation I am missing. Is there a name for this problem?

I am also considering this from a probabilistic perspective, in the case where we can assume that the hyperspheres are uniformly distributed.

I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ hyperspheres whose centers are the closest to $p$ under the Euclidean metric (although I'm eventually interested in exploring other metrics as well). So this is a discrete optimization problem where we are minimizing the maximum distance of an element in our set from $p$. However, the side constraint is that these hyperspheres cannot overlap with each other.

I am considering approximating the hyperspheres as axis-aligned hypercubes, but am not sure if this actually simplifies the problem.

I think this can be formulated as maximum weighted independent set (with a cardinality constraint) in a geometric intersection graph, where the weights are the distance from $p$, and we have an adjacency matrix where $A_{i,j} = 1$ if $dist(S_i, S_j) < c$ for some constant $c$, but I'm not sure if there is some other formulation I am missing. Is there a name for this problem?

I am also considering this from a probabilistic perspective, in the case where we can assume that the hyperspheres are uniformly distributed.

I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ hyperspheres whose centers are the closest to $p$ under the Euclidean metric (although I'm eventually interested in exploring other metrics as well). So this is a discrete optimization problem where we are minimizing the maximum distance of an element in our set from $p$. However, the side constraint is that these hyperspheres cannot overlap with each other.

I am considering approximating the hyperspheres as axis-aligned hypercubes, but am not sure if this actually simplifies the problem.

I think this can be formulated as maximum weighted independent set (with a cardinality constraint) in a geometric intersection graph (more specifically a disk intersection graph), where the weights are the distance from $p$, and we have an adjacency matrix where $A_{i,j} = 1$ if $dist(S_i, S_j) < c$ for some constant $c$. I'm not sure if there is some other formulation I am missing. Is there a name for this problem?

I am also considering this from a probabilistic perspective, in the case where we can assume that the hyperspheres are uniformly distributed.

I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ hyperspheres whose centers are the closest to $p$ under the Euclidean metric (although I'm eventually interested in exploring other metrics as well). So this is a discrete optimization problem where we are minimizing the maximum distance of an element in our set from $p$. However, the side constraint is that these hyperspheres cannot overlap with each other.

I think this can be formulated as maximum weighted independent set (with a cardinality constraint) in a geometric intersection graph, where the weights are the distance from $p$, and we have an adjacency matrix where $A_{i,j} = 1$ if $dist(S_i, S_j) < c$ for some constant $c$, but I'm not sure if there is some other formulation I am missing. Is there a name for this problem?

I am also considering this from a probabilistic perspective, in the case where we can assume that the hyperspheres are uniformly distributed.

I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ hyperspheres whose centers are the closest to $p$ under the Euclidean metric (although I'm eventually interested in exploring other metrics as well). So this is a discrete optimization problem where we are minimizing the maximum distance of an element in our set from $p$. However, the side constraint is that these hyperspheres cannot overlap with each other.

I am considering approximating the hyperspheres as axis-aligned hypercubes, but am not sure if this actually simplifies the problem.

I think this can be formulated as maximum weighted independent set (with a cardinality constraint) in a geometric intersection graph, where the weights are the distance from $p$, and we have an adjacency matrix where $A_{i,j} = 1$ if $dist(S_i, S_j) < c$ for some constant $c$, but I'm not sure if there is some other formulation I am missing. Is there a name for this problem?

I am also considering this from a probabilistic perspective, in the case where we can assume that the hyperspheres are uniformly distributed.