Article
Separability of Point Sets by k-Level Linear Classification Trees
Author/s | Arkin, Esther M.
Garijo Royo, Delia Márquez Pérez, Alberto Mitchell, Joseph S. B. Seara Ojea, Carlos |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Publication Date | 2012 |
Deposit Date | 2016-03-17 |
Published in |
|
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 ... 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). |
Files | Size | Format | View | Description |
---|---|---|---|---|
Separability of points.pdf | 382.9Kb | [PDF] | View/ | |