Problema de cobertura (transmisor y receptor)

Intento resolver el siguiente problema de cobertura.

Hay transmisores con un área de cobertura de 1 km receptores. Decida en que todos los receptores están cubiertos por cualquier transmisor. Todos los reverentes y transmisores están representados por sus coordenadas e . $n$ $n$ $O(n\log n)$ $x$ $y$

La solución más avanzada que puedo encontrar toma . Para cada receptor, clasifique todos los transmisores por su distancia a este receptor actual, luego tome el transmisor con la distancia más corta y esta distancia más corta debe estar dentro de 0.5 km. $O(n^2\log n)$

Pero el enfoque ingenuo parece mucho mejor en la complejidad del tiempo . Simplemente calcule toda la distancia entre todos los pares de transmisor y receptor. $O(n^2)$

No estoy seguro si puedo aplicar algoritmos de búsqueda de rango en este problema. Por ejemplo, los árboles kd nos permiten encontrar tales rangos, sin embargo, nunca vi un ejemplo, y no estoy seguro de si hay algún tipo de búsqueda de rango para círculos.

La complejidad dada supone que la solución debería ser de alguna manera similar a la ordenación. $O(n\log n)$

algorithms computational-geometry search-problem com
fuente

Si el tiempo esperado

está bien, creo que podría construir un árbol

sobre los transmisores (tomar tiempo

) y luego realizar una consulta de vecino más cercano para cada receptor (tomando un promedio del tiempo

para cada receptor). Esto debería ser el truco, pero supongo que necesita la peor complejidad del caso. Parece que hay algunos trucos para acelerar cuando está realizando múltiples consultas de vecinos más cercanos en un

-tree.

O (n \log n)

$O(n \log n)$

k d

$kd$

O (n \log n)

$O(n \log n)$

O (\log n)

$O(\log n)$

k d

$kd$

utdiscant

Supongo que un algoritmo de línea de barrido puede hacer el truco: ordenar los transmisores y receptores por coordenada x y recorrer la lista. La gestión inteligente del conjunto de transmisores viables es esencial.

Raphael

@Raphael, ¿puedes explicar un poco más? Parece que va a ser muy lento en el peor de los casos.

com

Creo que vale la pena echar un vistazo al algoritmo de Fortune para calcular un diagrama de Voronoi en el avión. Funciona en

, y dado un diagrama de Voronoi, su problema se vuelve fácil.

O (n \log n)

$O(n\log n)$

Syzygy

Respuestas:

Puede usar el diagrama de Voronoi, junto con la estructura de datos de Kirkpatrick para resolver este problema.

Como sugirieron Raphael y Syzygy, puede usar el algoritmo de Fortune (línea de barrido) para crear el diagrama de Voronoi. El peor caso: . $\mathcal{O}(n \log n)$

El diagrama de Voronoi tendrá un montón de polígonos, cada uno con un transmisor. Cualquier punto dentro del polígono está más cerca de ese transmisor. Por lo tanto, si puede averiguar qué polígono contiene el receptor, puede encontrar el transmisor más cercano al mismo de alguna manera descubriendo en qué polígono se encuentra. Después de eso, verifica si ese transmisor está dentro de . $1\ \text{km}$

Para determinar qué polígono de Voronoi contiene el receptor, primero triangula cada polígono en el diagrama. Ahora tienes una malla triangular. Luego, usa la estructura de datos de Kirkpatrick para localizar cualquier triángulo que contenga un punto dado en el tiempo , el peor de los casos. La construcción de la estructura de datos de Kirkpatrick toma peor de los casos. Una vez que conozca el triángulo, sabrá el polígono que lo contiene y, por lo tanto, el transmisor más cercano. Hacer esto para todos los receptores será , el peor de los casos. $\mathcal{O}(\log n)$ $\mathcal{O}(n\log n)$ $\mathcal{O}(n\log n)$

Cada celda en un diagrama de Voronoi es un polígono convexo, posiblemente sin límites.

...

El número de vértices [de un diagrama de Voronoi de n sitios] V ≤ 2n-5

- www.cs.arizona.edu

$\Theta(v)$ $v$ $n$ $n$ $\mathcal{O}(n)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$

Ensalada Realz
fuente