Enclosing a Set of Objects by Two Minimum Area Rectangles

✍ Scribed by Bruno Becker; Paolo Giulio Franciosa; Stephan Gschwind; Stefano Leonardi; Thomas Ohler; Peter Widmayer

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 737 KB
• Volume: 21
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1996.0057

✦ Synopsis

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␣ n log n worst-case time algorithm, where ␣ is the inverse Ackermann's function, for finding, given a set M of points, segments and polygons * Work partially supported by the Schweizerischer Nationalfonds zur Forderung der ẅissenschaftlichen Forschung and by the Italian MURST National Project ''Algoritmi, Modelli di Calcolo e Strutture Informative.'' 520