Casco convexo son bien conocidos. Sin embargo, en mi caso, el objetivo se modifica ligeramente:
Dado $N$ puntos en un plano, construya un polígono convexo de área mínima de modo que contenga todos los puntos y no haya ningún punto que esté más cerca que la distancia dada $d$ a partir de las aristas del polígono, y el número de vértices de dicho polígono es el mismo que el número de vértices del casco convexo de los puntos dados.
En otras palabras, dado $N$ ovejas:
... encontrar la valla:
(Las ovejas pueden considerarse puntos, pero $d$ sigue siendo mayor que $0$ .)
0 votos
Un problema interesante. Obsérvese que encontrar el casco convexo de discos centrados en la oveja no es necesariamente óptimo.
0 votos
¿Probablemente inflar el casco convexo ayudaría?
0 votos
@lisyarus Correcto, esa fue mi primera versión, en resumen: encontrar el centroide e "inflar" el casco convexo moviendo los bordes del casco convexo lejos del centroide. Sin embargo, no he podido demostrar que sea un método correcto.
0 votos
@VividD No me refería al centroide. Puedes inflar las aristas por distancia $d$ a lo largo de sus normales. Computing es una especie de esqueleto recto, pero no es obvio para mí que el área sería mínimo =(
2 votos
Supongamos que $d=1$ . Pon cuatro ovejas en $(1,0),(-1,0),(0,-0.01)$ y $(0,100)$ . Entonces el casco convexo inflado no es ciertamente óptimo $-$ puede hacerlo mejor truncando el casco en $y=101$ y fusionando los dos bordes inferiores en uno solo.
0 votos
El siguiente artículo describe el problema del casco convexo en el que se tienen discos en lugar de puntos, quizás pueda serte útil aunque no resuelva directamente tu problema: RAPPAPORT, David. A convex hull algorithm for discs, and applications. Geometría computacional , 1992, 1.3: 171-187. ac.els-cdn.com/092577219290015K/…
0 votos
@uvts_cvs, ¡qué buena información!