Compact union of disjoint boxes: An efficient decomposition model for binary volumes

Irving Cruz-Matías, Dolors Ayala

Research output: Contribution to journalArticle

Abstract

This paper presents in detail the Compact Union of Disjoint Boxes (CUDB), a decomposition model for binary volumes that has been recently but briefly introduced. This model is an improved version of a previous model called Ordered Union of Disjoint Boxes (OUDB). We show here, several desirable features that this model has versus OUDB, such as less unitary basic elements (boxes) and thus, a better efficiency in some neighborhood operations. We present algorithms for conversion to and from other models, and for basic computations as area (2D) or volume (3D). We also present an efficient algorithm for connected-component labeling (CCL) that does not follow the classical two-pass strategy. Finally we present an algorithm for collision (or adjacency) detection in static environments. We test the efficiency of CUDB versus existing models with several datasets.
Original languageEnglish
Pages (from-to)275-292
Number of pages18
JournalComputacion y Sistemas
DOIs
Publication statusPublished - 1 Jan 2017

Fingerprint

Decomposition
Labeling

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Cite this

@article{3b0959b510dd4172bf9fddd2f2bebd5f,
title = "Compact union of disjoint boxes: An efficient decomposition model for binary volumes",
abstract = "This paper presents in detail the Compact Union of Disjoint Boxes (CUDB), a decomposition model for binary volumes that has been recently but briefly introduced. This model is an improved version of a previous model called Ordered Union of Disjoint Boxes (OUDB). We show here, several desirable features that this model has versus OUDB, such as less unitary basic elements (boxes) and thus, a better efficiency in some neighborhood operations. We present algorithms for conversion to and from other models, and for basic computations as area (2D) or volume (3D). We also present an efficient algorithm for connected-component labeling (CCL) that does not follow the classical two-pass strategy. Finally we present an algorithm for collision (or adjacency) detection in static environments. We test the efficiency of CUDB versus existing models with several datasets.",
author = "Irving Cruz-Mat{\'i}as and Dolors Ayala",
year = "2017",
month = "1",
day = "1",
doi = "10.13053/CyS-21-2-2737",
language = "English",
pages = "275--292",
journal = "Computacion y Sistemas",
issn = "1405-5546",
publisher = "Centro de Investigacion en Computacion (CIC) del Instituto Politecnico Nacional (IPN)",

}

Compact union of disjoint boxes: An efficient decomposition model for binary volumes. / Cruz-Matías, Irving; Ayala, Dolors.

In: Computacion y Sistemas, 01.01.2017, p. 275-292.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Compact union of disjoint boxes: An efficient decomposition model for binary volumes

AU - Cruz-Matías, Irving

AU - Ayala, Dolors

PY - 2017/1/1

Y1 - 2017/1/1

N2 - This paper presents in detail the Compact Union of Disjoint Boxes (CUDB), a decomposition model for binary volumes that has been recently but briefly introduced. This model is an improved version of a previous model called Ordered Union of Disjoint Boxes (OUDB). We show here, several desirable features that this model has versus OUDB, such as less unitary basic elements (boxes) and thus, a better efficiency in some neighborhood operations. We present algorithms for conversion to and from other models, and for basic computations as area (2D) or volume (3D). We also present an efficient algorithm for connected-component labeling (CCL) that does not follow the classical two-pass strategy. Finally we present an algorithm for collision (or adjacency) detection in static environments. We test the efficiency of CUDB versus existing models with several datasets.

AB - This paper presents in detail the Compact Union of Disjoint Boxes (CUDB), a decomposition model for binary volumes that has been recently but briefly introduced. This model is an improved version of a previous model called Ordered Union of Disjoint Boxes (OUDB). We show here, several desirable features that this model has versus OUDB, such as less unitary basic elements (boxes) and thus, a better efficiency in some neighborhood operations. We present algorithms for conversion to and from other models, and for basic computations as area (2D) or volume (3D). We also present an efficient algorithm for connected-component labeling (CCL) that does not follow the classical two-pass strategy. Finally we present an algorithm for collision (or adjacency) detection in static environments. We test the efficiency of CUDB versus existing models with several datasets.

U2 - 10.13053/CyS-21-2-2737

DO - 10.13053/CyS-21-2-2737

M3 - Article

SP - 275

EP - 292

JO - Computacion y Sistemas

JF - Computacion y Sistemas

SN - 1405-5546

ER -