On the Polynomial Time Computability of Abstract Ray-Tracing Problems
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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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://global.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 -
English
