排序方式: 共有2条查询结果,搜索用时 15 毫秒
1
1.
Stephan Eidenbenz 《Computational Geometry》2002,21(3):524-153
How many people can hide in a given terrain, without any two of them seeing each other? We are interested in finding the precise number and an optimal placement of people to be hidden, given a terrain with n vertices. In this paper, we show that this is not at all easy: The problem of placing a maximum number of hiding people is almost as hard to approximate as the
problem, i.e., it cannot be approximated by any polynomial-time algorithm with an approximation ratio of n for some >0, unless P=NP. This is already true for a simple polygon with holes (instead of a terrain). If we do not allow holes in the polygon, we show that there is a constant >0 such that the problem cannot be approximated with an approximation ratio of 1+. 相似文献
2.
A coding problem in steganography 总被引:1,自引:0,他引:1
To study how to design a steganographic algorithm more efficiently, a new coding problem—steganographic codes (abbreviated
stego-codes)—is presented in this paper. The stego-codes are defined over the field with q(q ≥ 2) elements. A method of constructing linear stego-codes is proposed by using the direct sum of vector subspaces. And the
problem of linear stego-codes is converted to an algebraic problem by introducing the concept of the tth dimension of a vector space. Some bounds on the length of stego-codes are obtained, from which the maximum length embeddable
(MLE) code arises. It is shown that there is a corresponding relation between MLE codes and perfect error-correcting codes.
Furthermore the classification of all MLE codes and a lower bound on the number of binary MLE codes are obtained based on
the corresponding results on perfect codes. Finally hiding redundancy is defined to value the performance of stego-codes.
相似文献
1