Ajuste de esfera con aplicaciones al seguimiento de máquinas
Autores: Epstein, Dror; Feldman, Dan
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Ajuste de esfera con aplicaciones al seguimiento de máquinas
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Algoritmo
Esfera
Aproximación
Puntos
Coreset
Distancia
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 48
Citaciones: Sin citaciones
Proponemos un algoritmo de aproximación demostrable y práctico para ajustar un conjunto de puntos en una esfera. Aquí, una esfera se representa por su centro y radio. El objetivo es minimizar la suma de distancias a los puntos hasta un factor multiplicativo de , para una constante dada, sobre cada uno de estos y . Nuestro resultado técnico principal es una sumarización de datos del conjunto de entrada, llamada coreset, que aproxima la suma de distancias mencionada en el conjunto original (grande) para cada esfera. Luego, una esfera precisa puede extraerse rápidamente a través de una búsqueda exhaustiva ineficiente desde el pequeño coreset. La mayoría de los artículos se centran principalmente en la identificación de esferas (por ejemplo, círculos en imágenes) en lugar de encontrar la coincidencia exacta (en el sentido de medidas de extensión), y no proporcionan garantías de aproximación. Implementamos nuestro algoritmo y proporcionamos extensos resultados experimentales tanto en datos sintéticos como del mundo real. Luego combinamos nuestro algoritmo en un sistema de control de presión mecánica cuyo principal cuello de botella es el seguimiento de una bola que cae. También se proporciona el código fuente completo.
Descripción
Proponemos un algoritmo de aproximación demostrable y práctico para ajustar un conjunto de puntos en una esfera. Aquí, una esfera se representa por su centro y radio. El objetivo es minimizar la suma de distancias a los puntos hasta un factor multiplicativo de , para una constante dada, sobre cada uno de estos y . Nuestro resultado técnico principal es una sumarización de datos del conjunto de entrada, llamada coreset, que aproxima la suma de distancias mencionada en el conjunto original (grande) para cada esfera. Luego, una esfera precisa puede extraerse rápidamente a través de una búsqueda exhaustiva ineficiente desde el pequeño coreset. La mayoría de los artículos se centran principalmente en la identificación de esferas (por ejemplo, círculos en imágenes) en lugar de encontrar la coincidencia exacta (en el sentido de medidas de extensión), y no proporcionan garantías de aproximación. Implementamos nuestro algoritmo y proporcionamos extensos resultados experimentales tanto en datos sintéticos como del mundo real. Luego combinamos nuestro algoritmo en un sistema de control de presión mecánica cuyo principal cuello de botella es el seguimiento de una bola que cae. También se proporciona el código fuente completo.