Visibility of rectagular objects inL1metric

DOI10.1080/00207169808804743MaRDI QIDQ4236100zbMATH OpenOpenAlexWikidataFDO

Authors S. Jeyalakshmi, Kamala Krithivasan

Publication date 22 March 1999

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207169808804743

zbMATH Keywords

computational complexitycomputational geometryobject modellingvisibility algorithmsvisibility of geometric objects

Mathematics Subject Classification ID

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

Review text

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.

Recommendations

• On rectangular visibility
• An optimal algorithm for reporting visible rectangles
• scientific article; zbMATH DE number 1182918
• An optimal algorithm for computing visibility in the plane

Cites work

• Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
• Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity
• Priority Search Trees
• Visibility with a moving point of view

Cited in

(1)

• On rectangular visibility

This page was built for publication: Visibility of rectagular objects inL₁metric

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4236100)