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

Separability of Point Sets by k-Level Linear Classification Trees


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

Show item statistics
Export to
Author: Arkin, Esther M.
Garijo Royo, Delia
Márquez Pérez, Alberto
Mitchell, Joseph S.B.
Seara, Carlos
Department: Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Date: 2012
Published in: International Journal of Computational Geometry & Applications, 22 (2), 143-165.
Document type: Article
Abstract: 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).
Size: 382.9Kb
Format: PDF



This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)