Sábháilte in:
| Príomhchruthaitheoirí: | , |
|---|---|
| Formáid: | Preprint |
| Foilsithe / Cruthaithe: |
2024
|
| Ábhair: | |
| Rochtain ar líne: | https://arxiv.org/abs/2403.02071 |
| Clibeanna: |
Cuir clib leis
Níl clibeanna ann, Bí ar an gcéad duine le clib a chur leis an taifead seo!
|
Clár na nÁbhar:
- In this paper we study the NP-Hard problem of maximizing the distance over an intersection of balls to a given point. We expand the results found in \cite{funcos1}, where the authors characterize the farthest in an intersection of balls $\mathcal{Q}$ to the given point $C_0$ by constructing some intersection of halfspaces. In this paper, by slightly modifying the technique found in literature, we characterize the farthest in an intersection of balls $\mathcal{Q}$ with another intersection of balls $\mathcal{Q}_1$. As such, going backwards, we are naturally able to find the given intersection of balls $\mathcal{Q}$ as the max indicator intersection of balls of another one $\mathcal{Q}_{-1}$. By repeating the process, we find a sequence of intersection of balls $(\mathcal{Q}_{i})_{i \in \mathbb{Z}}$, which has $\mathcal{Q}$ as an element, namely $\mathcal{Q}_{0}$ and show that $\mathcal{Q}_{-\infty} = \mathcal{B}(C_0,R_0)$ where $R_0$ is the maximum distance from $C_0$ to a point in $\mathcal{Q}$. As a final application of the proposed theory we give a polynomial algorithm for computing the maximum distance under an oracle which returns the volume of an intersection of balls, showing that the later is NP-Hard. Finally, we present a randomized method %of polynomial complexity which allows an approximation of the maximum distance.