¿Cuál es la forma de demostrar que el límite inferior del par más cercano es n log n utilizando Element Uniqueness?

La forma en que lo haría es reducir la unicidad del elemento al par más cercano. Esta reducción dice que el par más cercano (rhs) es al menos tan difícil como la unicidad del elemento (lhs), que se sabe que es Ω (n log n). Por lo tanto, el par más cercano es Ω (n log n).

La mecánica real es la siguiente.
Si reduce una instancia de unicidad del elemento a una instancia de resolver el par más cercano, entonces tiene una respuesta al par más cercano, puede responder a su pregunta de unicidad del elemento.

Por ejemplo, suponga que tiene los números: 1, 4, 2, 1, 5
Convierte eso en un problema de par más cercano en 2 días, con los siguientes puntos (1,0), (4,0), (2,0), (1,0), (5,0). Observe que convertimos un problema aparentemente 1-d en un problema 2-d. Es por eso que no podemos dar un límite superior en el par más cercano, ni podemos decir que el par más cercano se puede resolver en el tiempo Θ (n log n) simplemente usando esta reducción.

Ahora calcule la distancia entre el par de puntos más cercano. Si esta distancia es 0, entonces tiene puntos no únicos. De lo contrario, tienes puntos únicos.

Agregado: Curiosamente, no puedo realizar la reducción inversa del par más cercano -> unicidad del elemento. ¿Alguna idea de cómo se puede hacer eso o dar una prueba de por qué no es posible? Si no es posible, ¿significa que Element Uniqueness no tiene un límite inferior de Ω (n log n)? Sin embargo, sabemos que sí … Tal vez la falta de una reducción no significa que el límite inferior no sea eso, tal vez solo necesite encontrar una reducción con el límite inferior que desee. ¿Qué interpretación es la correcta? Parece que las reducciones son como depuración. La ausencia de uno no significa nada, pero la presencia señala algo.