共查询到3条相似文献,搜索用时 0 毫秒
1.
2.
The diameter of a set P of n points in ℝ
d
is the maximum Euclidean distance between any two points in P. If P is the vertex set of a 3-dimensional convex polytope, and if the combinatorial structure of this polytope is given, we prove
that, in the worst case, deciding whether the diameter of P is smaller than 1 requires Ω(nlog n) time in the algebraic computation tree model. It shows that the O(nlog n) time algorithm of Ramos for computing the diameter of a point set in ℝ3 is optimal for computing the diameter of a 3-polytope. We also give a linear time reduction from Hopcroft’s problem of finding
an incidence between points and lines in ℝ2 to the diameter problem for a point set in ℝ7. 相似文献
3.
Higman showed that if A is any language then SUBSEQ(A) is regular. His proof was nonconstructive. We show that the result cannot be made constructive. In particular we show that
if f takes as input an index e of a total Turing Machine M
e
, and outputs a DFA for SUBSEQ(L(M
e
)), then ∅″≤T
f (f is Σ
2-hard). We also study the complexity of going from A to SUBSEQ(A) for several representations of A and SUBSEQ(A). 相似文献