JCSE, vol. 14, no. 1, pp.1-8, 2020

DOI: http://dx.doi.org/10.5626/JCSE.2020.14.1.1

Minimum-Width Cuboidal Shells with Outliers

Sang Won Bae
Division of Computer Science and Engineering, Kyonggi University, Suwon, Korea

Abstract: A (hyper-)cuboid, also known as a hyper-rectangle or a box, is a compact body of dimension three or higher, extending its two-dimensional analog, rectangles. A cuboidal shell is the compact volume between a cuboid and its inward offset. In this paper, we address the problem of computing a minimum-width cuboidal shell that encloses at least n-k points out of n given points in Rd when d??. The number k is given as input and the k excluded points as a result are considered outliers of the n input points. Prior to our work, there was no known algorithm for the cuboidal shell problem considering outliers. We solve the problem for the first time by presenting two efficient algorithms. Our algorithms run in O(k2d n) time and O(n) space or in O(n logd-1 n + k2d logd n) time and O(n logd-1 n) space.

Keyword: Algorithm; Computational geometry; High-dimensional geometry; Cuboidal shell; Outlier

Full Paper:   183 Downloads, 1273 View