Artículo
Separability of Point Sets by k-Level Linear Classification Trees
Autor/es | Arkin, Esther M.
Garijo Royo, Delia Márquez Pérez, Alberto Mitchell, Joseph S. B. Seara Ojea, Carlos |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2012 |
Fecha de depósito | 2016-03-17 |
Publicado en |
|
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 ... 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). |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Separability of points.pdf | 382.9Kb | [PDF] | Ver/ | |