Sharif Digital Repository

In this paper, we consider the problem of computing the visibility polygon (VP) of a query point q (or VP(q)) in a scene consisting of some obstacles with total complexity of n. We show that the combinatorial representation of VP(q) can be computed in logarithmic time by preprocessing the scene in O( n4logn) time and using O( n4) space. We can also report the actual VP(q) in additional O(|VP(q)|) time. As a main result of this paper, we will prove that we can have a tradeoff between the query time and the preprocessing time/space. In other words, we will show that using O(m) space, we can obtain O( n2log(m/n)/m) query time, where m is a parameter satisfying n2≤m≤ n4. For example, when m= n3,... 

This paper presents a new balanced, distributed data structure for storing data with multidimensional keys in a peer-to-peer network. It supports range queries as well as single point queries which are routed in O (log n) hops. Our structure, called SkipTree, is fully decentralized with each node being connected to O (log n) other nodes. We propose modifications to the structures, so that the memory usage for maintaining the link structure at each node is reduced from the worst case of O (n) to O (log n log log n) on the average and O (log2 n) in the worst case. It is also shown that the load balancing is guaranteed to be within a constant factor. Our experimental results verify our... 

Key predistribution in sensor networks refers to the problem of distributing secret keys among sensor nodes prior to deployment. Recently, many key predistribution schemes have been proposed for wireless sensor networks. To further improve these techniques, researchers have also proposed to use sensors' expected location information to help predistribution of keying materials. In this paper we propose a lightweight and scalable key establishment scheme for GPS-enabled wireless sensor networks. This scheme has little communication overhead and memory usage. Since communications and computations of key establishment schemes are done only once and when the network is begin initiated, actually... 

Different efforts have been done to address the problem of information overload on the Internet. Recommender systems aim at directing users through this information space, toward the resources that best meet their needs and interests by extracting knowledge from the previous users' interactions. In this paper, we propose an algorithm to solve the web page recommendation problem. In our algorithm, we use distributed learning automata to learn the behavior of previous users' and recommend pages to the current user based on learned pattern. Our experiments on real data set show that the proposed algorithm performs better than the other algorithms that we compared to and, at the same time, it is... 

In this paper a variational framework for joint segmentation and motion estimation is employed for inspecting heart in Cine MRI sequences. A functional including Mumford-Shah segmentation and optical flow based dense motion estimation is approximated using the phase-field technique. The minimizer of the functional provides an optimum motion field and edge set by considering both spatial and temporal discontinuities. Exploiting calculus of variation principles, multiple partial differential equations associated with the Euler-Lagrange equations of the functional are extracted, first. Next, the finite element method is used to discretize the resulting PDEs for numerical solution. Several... 

Image based registration of rigid objects has been frequently addressed in the literature to obtain an object's motion parameters. In this paper, a new approach of joint segmentation-rigid registration, within the variational framework of the phase field approximation of the Mumford-Shah's functional, is proposed. The defined functional consists of two Mumford-Shah equations, extracting the discontinuity set of the reference and target images due to a rigid spatial transformation. Multiscale minimization of the proposed functional after finite element discretization provided a sub-pixel, robust algorithm for edge extraction as well as edge based rigid registration. The implementation...