On the Polynomial Time Computability of Abstract Ray-Tracing Problems

Shuji ISOBE; Tetsuo KURIYAMA; Masahiro MAMBO; Hiroki SHIZUYA

On the Polynomial Time Computability of Abstract Ray-Tracing Problems

Shuji ISOBE, Tetsuo KURIYAMA, Masahiro MAMBO, Hiroki SHIZUYA

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.5 pp.1209-1213

Publication Date: 2005/05/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Shuji ISOBE, Tetsuo KURIYAMA, Masahiro MAMBO, Hiroki SHIZUYA, "On the Polynomial Time Computability of Abstract Ray-Tracing Problems" in IEICE TRANSACTIONS on Fundamentals, vol. E88-A, no. 5, pp. 1209-1213, May 2005, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e88-a_5_1209/_p

Copy

@ARTICLE{e88-a_5_1209,
author={Shuji ISOBE, Tetsuo KURIYAMA, Masahiro MAMBO, Hiroki SHIZUYA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Polynomial Time Computability of Abstract Ray-Tracing Problems},
year={2005},
volume={E88-A},
number={5},
pages={1209-1213},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - On the Polynomial Time Computability of Abstract Ray-Tracing Problems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1209
EP - 1213
AU - Shuji ISOBE
AU - Tetsuo KURIYAMA
AU - Masahiro MAMBO
AU - Hiroki SHIZUYA
PY - 2005
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2005
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.
ER -