Computing Voronoi Adjacencies in High Dimensional Spaces by Using Linear Programming

摘要: Some algorithms in Pattern Recognition and Machine Learning as neighborhood-based classification dataset condensation can be improved with the use of Voronoi tessellation. This paper shows weakness some existing tessellation to deal high-dimensional datasets. The linear programming improve procedures by focusing on adjacency. It will shown that adjacency test based is a version polytope search. However, search procedure provides more information than simple Boolean test. proposes strategy additional contained basis algorithm obtain other tests. theoretical results are applied tessellate several random datasets, also for much-used datasets repositories.