In this paper, we face the problem of computing an enclosing pair of axis-parallel rectangles of a set of polygonal objects in the plane, serving as a simple container. We propose an O(n alpha(n)log n) worst-case time algorithm, where alpha() is the inverse Ackermann's function, for finding, given a set M of points, segments and polygons defined by n vertices, a pair of axis-parallel rectangles (s,t) such that s boolean OR t encloses all objects in M and area(s) + area(t) is minimum. The algorithm works in O(n alpha (n) log log n) worst-case space. Moreover, we prove an Omega(n log n) lower bound for the one-dimensional version of the problem. We also show that for the special case of enclosing a set of polygons with axis-parallel sides, our algorithm runs in optimal worst-case time O(n log n), using worst-case space O(n log log n). (C) 1996 Academic Press, Inc.

Enclosing a set of objects by two minimum area rectangles / Bruno, Becker; Franciosa, Paolo Giulio; Stephan, Gschwind; Leonardi, Stefano; Thomas, Ohler; Peter, Widmayer. - In: JOURNAL OF ALGORITHMS. - ISSN 0196-6774. - STAMPA. - 21:3(1996), pp. 520-541. [10.1006/jagm.1996.0057]

Enclosing a set of objects by two minimum area rectangles

FRANCIOSA, Paolo Giulio;Stefano Leonardi;
1996

Abstract

In this paper, we face the problem of computing an enclosing pair of axis-parallel rectangles of a set of polygonal objects in the plane, serving as a simple container. We propose an O(n alpha(n)log n) worst-case time algorithm, where alpha() is the inverse Ackermann's function, for finding, given a set M of points, segments and polygons defined by n vertices, a pair of axis-parallel rectangles (s,t) such that s boolean OR t encloses all objects in M and area(s) + area(t) is minimum. The algorithm works in O(n alpha (n) log log n) worst-case space. Moreover, we prove an Omega(n log n) lower bound for the one-dimensional version of the problem. We also show that for the special case of enclosing a set of polygons with axis-parallel sides, our algorithm runs in optimal worst-case time O(n log n), using worst-case space O(n log log n). (C) 1996 Academic Press, Inc.
1996
01 Pubblicazione su rivista::01a Articolo in rivista
Enclosing a set of objects by two minimum area rectangles / Bruno, Becker; Franciosa, Paolo Giulio; Stephan, Gschwind; Leonardi, Stefano; Thomas, Ohler; Peter, Widmayer. - In: JOURNAL OF ALGORITHMS. - ISSN 0196-6774. - STAMPA. - 21:3(1996), pp. 520-541. [10.1006/jagm.1996.0057]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/48477
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 4
social impact