CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishIn 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.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
| Titolo: | Enclosing a set of objects by two minimum area rectangles |
| Autori: | |
| Data di pubblicazione: | 1996 |
| Rivista: | |
| Citazione: | 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. |
| Handle: | http://hdl.handle.net/11573/48477 |
| Appartiene alla tipologia: | 01a Articolo in rivista |
File allegati a questo prodotto
http://hdl.handle.net/11573/48477
Copyright © 2020