Repositorio de producción científica de la Universidad de Sevilla

Separability of Point Sets by k-Level Linear Classification Trees

Opened Access Separability of Point Sets by k-Level Linear Classification Trees


buscar en

Exportar a
Autor: Arkin, Esther M.
Garijo Royo, Delia
Márquez Pérez, Alberto
Mitchell, Joseph S.B.
Seara, Carlos
Departamento: Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Fecha: 2012
Publicado en: International Journal of Computational Geometry & Applications, 22 (2), 143-165.
Tipo de documento: Artículo
Resumen: Let R and B be sets of red and blue points in the plane in general position. We study the problem of computing a k-level binary space partition (BSP) tree to classify/separate R and B, such that the tree defines a linear decision at each internal node and each leaf of the tree corresponds to a (convex) cell of the partition that contains only red or only blue points. Specifically, we show that a 2-level tree can be computed, if one exists, in time O(n2). We show that a minimum-level (3 ≤ k ≤ log n) tree can be computed in time nO(log n). In the special case of axis-parallel partitions, we show that 2-level and 3-level trees can be computed in time O(n), while a minimum-level tree can be computed in time O(n5).
Tamaño: 382.9Kb
Formato: PDF



Mostrar el registro completo del ítem

Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones