Selección de subconjuntos de posición general en disposiciones de líneas
Autores: Dumitrescu, Adrian
Idioma: Inglés
Editor: MDPI
Año: 2025
Acceso abierto
Artículo científico
2025
Selección de subconjuntos de posición general en disposiciones de líneas
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Puntos
Problema de selección de subconjuntos de posición general
Ratio de aproximación
Puntos de la retícula
Disposición de líneas
Vértices
Colineales
Líneas
Métodos probabilísticos
Geometría de incidencia
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 56
Citaciones: Sin citaciones
Dado un conjunto de puntos en un plano, el problema de Selección de Subconjunto en Posición General consiste en encontrar un subconjunto de puntos de tamaño máximo en posición general, es decir, sin tres puntos colineales. Se sabe que el problema es computacionalmente difícil y la mejor relación de aproximación conocida es . Aquí, obtenemos mejores aproximaciones en tres casos especiales: (I) una aproximación de factor constante para el caso en que el conjunto de entrada consiste en puntos de red y es , lo que significa que la relación entre la distancia máxima y mínima en es del orden de ; (II) una aproximación de - para el caso en que el conjunto de entrada es el conjunto de vértices de un arreglo de líneas de -líneas, es decir, uno con vértices; y (III) una aproximación de - para el caso en que el conjunto de entrada tiene a lo sumo puntos colineales y puede ser cubierto por líneas. El escenario en (I) es un caso especial de (II). Nuestras aproximaciones se basan en métodos probabilísticos y resultados de geometría de incidencia.
Descripción
Dado un conjunto de puntos en un plano, el problema de Selección de Subconjunto en Posición General consiste en encontrar un subconjunto de puntos de tamaño máximo en posición general, es decir, sin tres puntos colineales. Se sabe que el problema es computacionalmente difícil y la mejor relación de aproximación conocida es . Aquí, obtenemos mejores aproximaciones en tres casos especiales: (I) una aproximación de factor constante para el caso en que el conjunto de entrada consiste en puntos de red y es , lo que significa que la relación entre la distancia máxima y mínima en es del orden de ; (II) una aproximación de - para el caso en que el conjunto de entrada es el conjunto de vértices de un arreglo de líneas de -líneas, es decir, uno con vértices; y (III) una aproximación de - para el caso en que el conjunto de entrada tiene a lo sumo puntos colineales y puede ser cubierto por líneas. El escenario en (I) es un caso especial de (II). Nuestras aproximaciones se basan en métodos probabilísticos y resultados de geometría de incidencia.