MAXIMAL EMPTY CUBOIDS AMONG POINTS AND BLOCKS

Authors
NANDY SC BHATTACHARYA BB
Citation
Sc. Nandy et Bb. Bhattacharya, MAXIMAL EMPTY CUBOIDS AMONG POINTS AND BLOCKS, Computers & mathematics with applications (1987), 36(3), 1998, pp. 11-20
Citations number
8
Categorie Soggetti
Mathematics,"Computer Science Interdisciplinary Applications",Mathematics,"Computer Science Interdisciplinary Applications
Journal title
Computers & mathematics with applications (1987) → ACNP
ISSN journal
08981221
Volume
36
Issue
3
Year of publication
1998
Pages
11 - 20
Database
ISI
SICI code
0898-1221(1998)36:3<11:MECAPA>2.0.ZU;2-P
Abstract
Given a three-dimensional box containing n points, we consider the pro blem of identifying all Maximal Empty Isothetic Cuboids (MEC), i.e., a ll 3D empty parallelepiped bounded by six isothetic rectangular faces. It is shown that the total number of MECs is bounded by O(n(3)) in th e worst case. An output-sensitive algorithm, based on plane-sweep para digm, is proposed for generating all the MECs present on the floor. Th e algorithm runs in O(C + n(2) log n) time in the worst case, and requ ires O(n) space, where C is the number of MECs present inside the box. (C) 1998 Elsevier Science Ltd. All rights reserved.