An optimal algorithm for reporting visible rectangles

✍ Scribed by N. Kitsios; C. Makris; S. Sioutas; A. Tsakalidis; J. Tsaknakis; B. Vassiliadis

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 75 KB
• Volume: 81
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(01)00228-9

✦ Synopsis

We consider the following problem as defined by Grove et al. [Internat. J. Comput. Geom. Appl. 9 (1999) 207-217]: Given a set of n isothetic rectangles in 3D space determine the subset of rectangles, that are not completely hidden. We present an optimal algorithm for this problem that runs in O(n log n) time and O(n) space. Our result is an improvement over the one of Grove et al. by a logarithmic factor in storage and is achieved by using a different approach. An analogous approach gives non-trivial solutions for other kinds of objects too.