Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9655988 | Electronic Notes in Theoretical Computer Science | 2005 | 13 Pages |
Abstract
The problem of finding a piecewise straight-line path, with a constant number of line segments, in a two-dimensional domain is studied in the Turing machine-based computational model and in the discrete complexity theory. It is proved that, for polynomial-time recognizable domains associated with polynomial-time computable distance functions, the complexity of this problem is equivalent to a discrete problem which is complete for â2P, the second level of the polynomial-time hierarchy.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Arthur W. Chou, Ker-I Ko,