En geometría computacional , un conjunto de núcleos es un pequeño conjunto de puntos que se aproxima a la forma de un conjunto de puntos más grande, en el sentido de que aplicar alguna medida geométrica a los dos conjuntos (como su volumen mínimo de cuadro delimitador ) da como resultado números aproximadamente iguales. Muchos problemas de optimización geométrica natural tienen núcleos que se aproximan a una solución óptima dentro de un factor de 1 + ε , que se pueden encontrar rápidamente (en tiempo lineal o casi lineal), y cuyo tamaño está limitado por una función de 1 / ε independiente del tamaño de entrada, donde εes un número positivo arbitrario. Cuando este es el caso, se obtiene un esquema de aproximación de tiempo lineal o casi lineal, basado en la idea de encontrar un núcleo y luego aplicar un algoritmo de optimización exacto al núcleo. Independientemente de lo lento que sea el algoritmo de optimización exacto, para cualquier elección fija de ε , el tiempo de ejecución de este esquema de aproximación será O (1) más el tiempo para encontrar el núcleo. [1] [2]
Este artículo relacionado con algoritmos o estructuras de datos es un fragmento . Puedes ayudar a Wikipedia expandiéndolo .