Maximal empty coboids among points and blocks. (English) Zbl 0939.68145
Summary: Given a three-dimensional box containing \(n\) points, we consider the problem of identifying all Maximal Empty Isothetic Cuboids (MEC), i.e., all 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 the worst case. An output-sensitive algorithm, based on plane-sweep paradigm, is proposed for generating all the MECs present on the floor. The algorithm runs in \(O(C+ n^2\log n)\) time in the worst case, and requires \(O(n)\) space, where \(C\) is the number of MECs present inside the box.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
maximal empty isothetic cuboidsReferences:
| [1] | Naamad, A.; Lee, D. T.; Hsu, W. L., On the maximum empty rectangle problem, Discrete Applied Mathematics, 8, 267-277 (1984) · Zbl 0543.68057 |
| [2] | Chazelle, B.; Drysdale, R. L.; Lee, D. T., Computing the largest empty rectangle, SIAM Journal on Computing, 15, 300-315 (1986) · Zbl 0608.68059 |
| [3] | Aggarwal, A.; Suri, S., Fast algorithm for computing the largest empty rectangle, (Proc. Third ACM Symposium on Computational Geometry (1987)), 278-290 |
| [4] | Rawlins, G. J.E.; Wood, D., Orthoconvexity and its generalizations, (Toussaint, G., Computational Morphology (1988), Elsevier Science B. V), 137-152 · Zbl 0651.52001 |
| [5] | Nandy, S. C.; Bhattacharya, B. B.; Ray, S., Efficient algorithms for identifying all maximal isothetic empty rectangles in VLSI layout design, (Proc. FSTTCS-10, Volume 472 (1990), Springer-Verlag: Springer-Verlag Berlin), 255-269, Lecture Notes in Computer Science · Zbl 0733.68090 |
| [6] | Nandy, S. C.; Sinha, A.; Bhattacharya, B. B., Location of the largest empty rectangle among arbitrary obstacles, (Proc. FSTTCS-14, Volume 880 (1994), Springer-Verlag: Springer-Verlag Berlin), 159-170, Lecture Notes in Computer Science · Zbl 1044.68864 |
| [7] | Dobkkin, D.; Suri, S., Dynamically computing the maxima of decomposable functions with applications, (Proc. \(29^{th}\) FOCS (1989)), 488-493 |
| [8] | Orlowski, M., A new algorithm for the largest empty rectangle problem, Algorithmica, 5, 65-73 (1990) · Zbl 0689.68065 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
