Método eficaz para la detección de un cuerpo convexo en $\mathbb{R}^n$

Question

Deje $K_0$ ser un almacén de conjunto convexo en $\mathbf{R}^n$ dentro del cual se encuentran dos conjuntos de $K_1$$K_2$. Supongamos que,

1. $K_1\cup K_2=K_0$ $K_1\cap K_2=\emptyset$.
2. El límite entre el $K_1$ $K_2$ es desconocido. (Para evitar que el caso trivial, asumimos que el límite no es un hyperplane.)
3. Cualquiera de las $K_1$ o $K_2$ es un conjunto convexo, pero no sabemos que uno es.
4. Tenemos dos puntos iniciales $x,y$ a mano, donde$x\in K_1$$y\in K_2$. (Por favor, consulte la actualización de abajo).

Esencialmente, $K_0$ puede ser visto como una caja negra. Suponga que uno puede consultar cualquier punto en $K$, con una membresía de oracle, es decir, un procedimiento que dado un punto de $x\in K$, informa el set contiene $x$.

El objetivo es determinar el conjunto es convexo usando como algunos de pertenencia consultas como sea posible.

Existe un algoritmo para hacer esto?

---

Actualización:

Para realizar el muestreo en $K_1$ $K_2$ (también se $K_0$) factible, supongamos que tenemos dos puntos iniciales $x$ $y$ donde$x\in K_1$$y\in K_2$. Por lo tanto, uno puede emplear por ejemplo hit-and-run algoritmo con el punto de partida $x$ (o $y$) para los puntos de muestreo en $K_1$ (o $K_2$).

Answer 1

Deje $K_0$ ser la unidad de disco en $\mathbb{R}^2$. $K_1$ consiste en el punto en el $(1,0)$ y algún otro punto de $\zeta$ uniforme y elegido al azar en el límite de $K_0$ (el círculo unitario). No es convexo. $K_2$ es el complemento de a$K_1$$K_0$. Esto es convexo. Por lo tanto, esta es una instancia válida del problema.

Suponga que empieza con $x$ $(1,0)$ cualquier $y$$K_2$, dicen en $(0,0)$. La probabilidad de que cualquier algoritmo dado nunca las consultas $\zeta$$0$. Por lo tanto, casi seguramente, el resultado de todas las consultas serán para detectar puntos adicionales en $K_2$, pero nunca más puntos en $K_1$. Lo que no se puede determinar cual de $K_1$ o $K_2$ es el subconjunto convexo.

Contemplar una situación similar en la que $K_1$ es la intersección de una bola de radio $\delta$ $(1,0)$ $K_0$ y de nuevo $x$$(1,0)$. Esta vez, $K_1$ es convexo y $K_2$ no lo es. Dado cualquier algoritmo que se propone para resolver el problema y cualquier número natural $N$, elija $\delta$ tan pequeño que el algoritmo no probe $K_1$ dentro $N$ pasos. (Si se trata de un algoritmo estocástico, el pequeño diámetro de $K_1$ implica la posibilidad de sondear será infinitamente pequeño). Esto muestra el número de pasos en el algoritmo es ilimitado (o el número esperado de pasos es arbitrariamente grande, si el algoritmo es estocástico). Lo mejor que podemos decir es que los dos conjuntos pueden ser diferenciadas mediante una serie de pasos proporcional a la relación de áreas.

Para distinguir entre los dos casos, que son esencialmente de emprender una búsqueda de un segundo punto en $K_1$ (que es pequeña), pero todas las sondas están siempre volviendo puntos en $K_2$. Evidentemente un completamente al azar de búsqueda (uniformemente a lo largo de $K_0$) se va a realizar, así como cualquier otro podría. (Una vez que obtenga $2$ puntos dentro de cada uno de $K_1$$K_2$, el juego está casi terminado: es fácil de construir un pequeño número de puntos adicionales que le dicen que es el subconjunto convexo.)

Estas consideraciones no se descarta una solución al problema, sino que implica que la solución debe depender adicional asumido propiedades de $K_1$$K_2$; por ejemplo, que ambos tienen medida positiva con un valor distinto de cero como límite inferior, o otra cosa que un modelo diferente de espacio que se necesita; por ejemplo, que es totalmente discreto y contiene un número finito de puntos (que es un modelo más realista de lo que los ordenadores suelen hacer).

Answer 2

Dadas las limitaciones, creo que el siguiente enfoque será cercana a la óptima.

Empezar por azar la consulta de puntos hasta tener 1 punto en un conjunto y 2 en el otro. Entonces usted tiene los extremos de dos segmentos de cruzar la frontera.

Mediante el uso de interseccion en cada uno de esos segmentos, usted puede encontrar los pares de puntos en establecer arbitrariamente cerca de la frontera. Si uno de los conjuntos decir $K_1$, es estrictamente convexa, en última instancia, usted encontrará dos puntos en $K_2$ lo suficientemente cerca como para la límite de que su media es de $K_1$. Esto muestra que el $K_2$ no es convexa.