TY - JOUR
T1 - On the polynomial time computability of abstract ray-tracing problems
AU - Isobe, Shuji
AU - Kuriyama, Tetsuo
AU - Mambo, Masahiro
AU - Shizuya, Hiroki
PY - 2005
Y1 - 2005
N2 - The abstract ray-tracing problem asks, for a given scene consisting of a light source, a light receiver and finitely many obstacles in a space, and a given positive integer ε +~ 0, whether a ray going out from the light source could reach the light receiver with intensity at least ε. The problem is known to be PSPACE-hard, and it is very unlikely that there exists an efficient algorithm to solve the problem without adding any restriction. In this paper, we show that the problem can be solved in polynomial time under some weak practical restrictions.
AB - The abstract ray-tracing problem asks, for a given scene consisting of a light source, a light receiver and finitely many obstacles in a space, and a given positive integer ε +~ 0, whether a ray going out from the light source could reach the light receiver with intensity at least ε. The problem is known to be PSPACE-hard, and it is very unlikely that there exists an efficient algorithm to solve the problem without adding any restriction. In this paper, we show that the problem can be solved in polynomial time under some weak practical restrictions.
KW - Abstract ray-tracing problem (ARTP)
KW - PSPACE-hard/complete
KW - Ray-tracing problem
KW - Scene
UR - http://www.scopus.com/inward/record.url?scp=24144495265&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=24144495265&partnerID=8YFLogxK
U2 - 10.1093/ietfec/e88-a.5.1209
DO - 10.1093/ietfec/e88-a.5.1209
M3 - Article
AN - SCOPUS:24144495265
SN - 0916-8508
VL - E88-A
SP - 1209
EP - 1213
JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
IS - 5
ER -