logo móvil
Contáctanos

Selección de subconjuntos de posición general en disposiciones de líneas

Autores: Dumitrescu, Adrian

Idioma: Inglés

Editor: MDPI

Año: 2025

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro