×

Visibility of rectangular objects in \(L_1\) metric. (English) Zbl 0916.65150

The paper investigates the problem of computing the visibility of geometric objects from a source point. Given a set of \(n\) 2D-rectangles parallel to the \(xy\)-plane and a point \(P(x,y,z)\) in the 3D-space, the authors provide an algorithm that find the visibility of all rectangles, i.e. the set of all visible points of rectangles from \(P\), in the \(L_1\) metric. The computational complexity of the visibility obtained algorithm is \(O(n^4)\) in time and \(O(n^3)\) in space. Visibility algorithms are also provided for the case when the point \(P\) is moved along one of the coordinate axes, and the rectangles are inserted and deleted dynamically.
Reviewer: N.Curteanu (Iaşi)

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65Y20 Complexity and performance of numerical algorithms
51N05 Descriptive geometry
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Mccreight Edward M., SIAM J. Computing 14 pp 257– (1985) · Zbl 0564.68050 · doi:10.1137/0214021
[2] Bern Marshall, Algorithmica 11 pp 360– (1994) · Zbl 0804.68147 · doi:10.1007/BF01187019
[3] Lenhof H.P., Algorithmica 13 pp 301– (1995) · Zbl 0816.68123 · doi:10.1007/BF01190509
[4] Alt, Helmut, Fleischer, Rudolf, Kaufmann, Michael, Mehlhorn, Kurt, Naher, Stefan, Schirra, Stefan and Uhrig, Christian. Approximate Motion Planning and the Complexity of the Boundary of the Union of Simple Geometric Figures. Sixth Annual Symposium on Computational Geometry. Vol. 2, pp.281–289. tp appear · Zbl 0760.68082
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.