In this paper we consider a new type of cryptographic scheme, which can decode concealed images without any cryptographic computations. The scheme is perfectly secure and very easy to implement. We extend it into a vi...
详细信息
We extend the concept of the polygon visible from a source point S in a simple polygon by considering visibility with two types of reflection, specular and diffuse. In specular reflection a light ray reflects from an ...
详细信息
We present exact algorithms for finding a solution to the two-dimensional translational containment problem: find translations for k polygons which place them inside a polygonal container without overlApplng. We also ...
详细信息
ISBN:
(纸本)0898713498
We present exact algorithms for finding a solution to the two-dimensional translational containment problem: find translations for k polygons which place them inside a polygonal container without overlApplng. We also give an approximate algorithm: given any ϵ, it finds a set of translations such that no point of any polygon is more than 2ϵ inside the boundary of any other polygon or outside the container. The term &CN denotes a containment problem in which the κ polygons are convex and the container is nonconvex, and fcNN denotes nonconvex polygons and container. The polygons have up to m vertices, and the container has n vertices, where n > m (typically). We give exact algorithms for the following: 2CN in O(mnlogn) time, 3CN in O(m3ralogn) time, and ANN in O((mti)2κ+1LP(2κmn, + k2m2)) time, where LP(a, 6) is the time to solve a linear program with o variables and 6 constraints. We present an approximate algorithm for κNN whose running time is O((1/ϵ)κ log (1/ϵ)κ5slog s), where s is the largest number of vertices of any polygon that can generated by applying a certain set of operations to the input. We have no polynomial bound on s, but, in practice, it is usually not more than quadratic in n.
In "hot potato" packet routing problems, packets need to be routed to their respective destinations on a network. At each time step, each communication link can be traversed by at most one packet. Packets mu...
详细信息
In "hot potato" packet routing problems, packets need to be routed to their respective destinations on a network. At each time step, each communication link can be traversed by at most one packet. Packets must keep on moving until they reach their destinations, even if this means temporarily moving further away from their destinations. We investigate some simple design principles for hot potato routing algorithms. Perhaps our most important negative result is that for a wide class of natural algorithms, the number of deflections that a packet suffers can grow experimentally in the number of other packets in the network. On the positive side, we present some (admitedly weak) upper bounds on the worst case performance for algorithms for general networks, and for special cases such as the mesh, the torus, and the infinite line.< >
On-line machine scheduling has been studied extensively, but the fundamental issue of fairness in scheduling is still mostly open. In this paper we explore the issue in settings where there are long living processes w...
详细信息
ISBN:
(纸本)0898713498
On-line machine scheduling has been studied extensively, but the fundamental issue of fairness in scheduling is still mostly open. In this paper we explore the issue in settings where there are long living processes which should be repeatedly scheduled for various tasks throughout the lifetime of a system. For any such instance we develop a notion of desired load of a process, which is a function of the tasks it participates in. The unfairness of a system is the maximum, taken over all processes, of the difference between the desired load and the actual load. An example of such a setting is the carpooi problem suggested by Fagin and Williams [17]. In this problem, a set of n people form a carpooi. On each day a subset of the people arrive and one of them is designated as the driver. A scheduling rule is required so that the driver will be determined in a 'fair' way. We investigate this problem under various assumptions on the input distribution. We also show that the carpooi problems can capture several other problems of fairness in scheduling.
Multithreaded execution models attempt to combine some aspects of dataflow-like execution with von Neumann model execution. Their main objective is to mask the latency of inter-processor communications and remote memo...
详细信息
Multithreaded execution models attempt to combine some aspects of dataflow-like execution with von Neumann model execution. Their main objective is to mask the latency of inter-processor communications and remote memory accesses in large scale multiprocessors. An important issue in the analysis and evaluation of multithreaded execution is the design and performance of the storage hierarchy. Because of the sequential execution of threads, the locality of access within an executing thread can be exploited using registers and cache. At the inter-thread level, however, the locality of accesses to memory and its effect on the cache is not yet well understood. A storage model which can exploit this locality is developed and evaluated. The results indicate there is a large amount of inter-thread locality that can be exploited and that we can get an efficient storage system by exploiting the characteristics of nonblocking threads.
暂无评论