Sharif Digital Repository

Geographical environments can be modeled through the medium of TINs, in which some discrete points are sampled as vertices, and the union of polygonal faces, particularly triangles, constitutes its surface. As regards the two-dimensional space, the TIN boundary is an x-monotone path and we focus on this case. If the number of vertices is too large to be stored or some sampled points should be removed due to a lack of vital information, the necessity of TIN simplification arises. On top of this situation, if a point observer locates on or above the TIN, the points visible to the observer have more priorities to be considered in the simplified TIN. For example, human eyes can see the closer or... 

For a simple polygon in the plane, the visibility graph is a graph whose vertices are the vertices of the polygon and there is an edge between two vertices if and only if their corresponding vertices see each other in the polygon. Two points of the polygon see each other if the line segment connecting them lies completely inside (or on the boundary of) the polygon. Although computing the visibility graph of a polygon has been solved efficiently, its reverse problem after three decades is still an open problem. The reverse problem is known as recognition and reconstruction visibility graphs. Recognizing visibility graphs is to determine the necessary and sufficient conditions on a graph to be... 

Here, the properties of separability of linkages are studied. In general, a linkage is a simple polygonal chain embedded in 3-space with disjoint, straight-line edges, which are fixed-length bars. The internal vertices are called joints. If the two end points are connected then the linkage is a closed linkage, otherwise it is an open linkage. By imposing restrictions on the way the bars in joints can move, three kinds of linkages as rigid, revolute and flexible can be introduced. A motion in a linkage is the motion of its vertices that preserves the length of the bars, and adheres the restrictions on joints. A collection of linkages are said to be separatable if for any distance d, there is... 

Guarding terrains(or covering terrains) is a well known problem in the field of visibility and computational geometry. The aim of this problem is to select a minimal set of elements (such as points on terrain, line segment, points above terrain ,...),as guard set, such that every point of the terrain is visible from at least one member of the guard set.
This problem was introduced in 2-dimensions as art gallery problem. Various types of this problem have been defiend and studied in the literature. Guarding 3-dimensional terrains is an example of this problem. In 3-dimentional case, the guarded terrain can be modeled with triangulated irregullar network(TIN), as one of the surface models,... 

Many geometric problems have algorithms that exist on paper for them, such as the Convex Hull problem [1], Minimum Spanning Tree [2], Voronoi Diagram [3], Closest Pair of Points [4], Largest Empty Circle [5], Smallest Enclosing Circle [6], and more. In all of these problems, the assumption is that a certain number of points are given as input, and we must perform various operations on these points based on the nature of the problem. Furthermore, a stronger assumption is that these points are given to us precisely, but in reality, this is not the case, and for various reasons, it is not possible to determine the exact locations of these points. Therefore, it can be said that we are dealing... 

In this research, we consider the question of finding approximate bounds on some of computational geometry problems with uncertain data. We use color spanning set to model the uncertainty. Given a set of n points colored with m colors in d-dimension. The problem of minimum diameter in color spanning set model is finding a set of m points with distinct colors so as to minimize diameter of the points. We give an algorithm with an approximation factor (1 + ϵ) with running time O(21ϵd .ϵ−2d.n3) which improves the previous results. Next,we consider a new problem of finding bounds on unit covering in color-spanning set model:Minimum color spanning-set ball covering problem is to select m points of... 

In this research, we want to find a point of the kernel in an unknown star-shaped polygon by a robot with minimal sensing, such that the path is not far from the optimum path. The robot has a gap sensor which detects the dicontinuities (gaps) in its visibility polygon and detects the direction of gaps. The robat can move toward or against these gaps. Also, the robot has a compass, and detects the North, the West, the South and the East. The robot detects the position of gaps between these directions, and also, can move along these directions. In this research, we present an on-line algorithm, by which this robot can find a point of the kernel in an unknown star-shaped polygon. The... 

One of the ultimate goals in robotics is to design autonomous robots. Among other things, this means a robot has to be able to plan its own motion. To be able to plan a motion, a robot must have some knowledge about the environment in which it is moving. Some of this information can be provided by a floor plan. For other information the robot will have to rely on its sensors. In this thesis, we consider that the environment is unknown for the robot. So, the robot uses weak sensor to planning its motion. The sensor can distinguish between colors. The robot can follow the colors. Therefore, we need to specify the umber of colors in which the robot can navigate by them. We propose an efficient... 

Visibility is an important topic in computational geometry, computer graphics, and motion planning. Two points inside a polygon are visible to each other if their connecting segment remains completely inside the polygon. Visibility polygon of a point in a simple polygon P is the set of points inside P that are visible from the point. The visibility problem has also been considered for line segments. A point v is said to be weakly visible to a line segment pq if there exists a point w 2 pq, such that w and v are visible to each other. The problem of computing the weak visibility polygon (or WVP) of pq inside a polygon P is to compute all points of P that are weakly visible from pq. In this... 

Due to recent advancements and wide usage of location detection devices, huge amount of data are collected by GPS and cellular technologies which exhibits moving objects trajectories. Using this information, it is possible to track a set of objects over a long period of time, as happens for instance in studying animal migration. Always, in these situations it is undesirable or even impossible (due to process and storage limits) to store the complete stream of positioning data. Then, simplifying a trajectory as a data reduction technique is the option for resolving such problems. Moreover, there is an increasing interest in queries capturing ”aggregate” behavior of trajectories as groups like... 

We consider two variations of shortest paths problem inside a poly-gon. In the first variation, we want to find a shortest path from asource to view a destination inside a polygon with holes. We pro-pose two algorithms for this problem with the time complexity of O (hn log n) and O(n log n) in which the second one is optimal. In the second variation, we want to place a center policeman inside a sim-ple polygon so that the longer of the two shortest paths from two existing guards to the visibility polygon of the center policeman is minimized. We propose an algorithm for this problem with the time complexity of O(n 3)  

In this research, we focus on r-gather and (r; ϵ)-gather clustering. In the r-gather clustering, the input points are in metric space and must be clustered such that each cluster has at least r points and the objective is to minimize the radius of clustering. (r; ϵ)-gather clustering is a kind of r-gather clustering such that at most nϵ points can be unclustered. MapReduce model is one of the most used parallel models to process huge data and processes the input data in some machine simultaneously in parallel.In this research, we give a lower bound for the approximation factor of r-gather clustering in MapReduce model. This lower bound works in MapReduce model even an optimal algorithm... 

One of the methods to detect an unknown environment, is using the visual information about the environment. In this problem, we have an unknown two-dimensional environment consists of a set of edges and vertices that the geometric positions of vertices is not specified and only the combinatorial structure of the environment is available. In addition, certain information such as visibility of two vertices in the environment is known. The goal is to recognize the geometric shape of the environment with this information.This problem has many applications in Robotics particularly in dynamic envi- ronment where objects are moving.
In this thesis, we examine this problem in different conditions... 

The problem of guarding orthogonal art galleries with sliding cameras is a special case of the well-known art gallery problem when the goal is to minimize the number of guards. Each guard is considered as a point, which can guard all points that are in its visibility area. In the sliding camera model, each guard is specified by an orthogonal line segment which is completely inside the polygon. The visibility area of each sliding camera is defined by its line segment.Inspired by advancements in wireless technologies and the need to offer wireless ser- vices to clients, a new variant of the problems for covering the regions has been studied. In this problem, a guard is modeled as an... 

Given a set of obstacles as an arrangement of geometric shapes in the plane, we would like to find a path from the initial point s to the target point t that crosses the minimum number of obstacles. In other words, the goal is to determine the minimum number of obstacles that need to be removed to exist a collision-free path between s and t.On one hand, this problem can be used for measuring the strength of barrier coverage which is a fundamental concept in wireless sensor networks (WSNs), and on the other hand, it has been considered as a robot motion-planning problem. The objective of barrier coverage is to guarantee that any path from the start point to the target point, will intersect at... 

With the emergence of massive datasets, storing all of the data in memory is not feasible for many problems. This fact motivated the introduction of new data processing models such as the streaming model. In this model, data points arrive one by one and the available memory is too small to store all of the data points. For many problems, more recent data points are more important than the old ones. The sliding window model captures this fact by trying to find the solution for the n most recent data points using only o(n) memory. The k-center problem is an important optimization problem in which given a graph, we are interested in labeling k vertices of the graph as centers such that the... 

One of the available methods for modeling a geographical area is sampling a series of points whose altitude is measured and the altitude of other points is estimated based on the altitude of sampled points. The use of irregular triangular networks (TIN) is one of the common methods for this estimation. Because the number of sample points is large, it is necessary to reduce them in some applications. This process reduces the number of points. The process of reducing the number of sample points is called simplification. Simplification should be done in such a way as to preserve all the main features of the original space. For this purpose, various methods have been presented, which we will... 

Abstract The problem of competetive facility location can be defined as follows: There are a number of customers in the form of points in space, and two players arrange a number of facilities in the form of points in space, given some limitations, respectively. Each customer’s connection to each facility has a cost for the customer and an advantage for the facility, and each customer wants to be connected to at most one of the facilities which has the lowest cost for him. The goal is to find the strategy of placing the facilities and determining the cost which the facility receives from the customer, in such a way that the player’s profit is maximised.In this thesis, we first sought to... 

The kidney is one of the most complicated organs in terms of structure and physiology, in part because it is highly vascularized. Previous investigations have focused on specific characteristics like length and diameter. There are a few methods like those which are based on image processing techniques, that have been focused on all features as a unique structure. The clear drawback of these approaches is inability to justify growth and changes. Lindenmayer system (L-system) is parallel rewriting method and a type of graph grammars. L-system can justify growth and all characteristic changes and adopt itself to them. Parametric rewriting rules incorporating within physiological laws of the... 

The visibility graph of a simple polygon represents visibility relations between its vertices. Since each vertex in a polygon is visible from the two vertices adjacent to it on the boundary of the polygon, this boundary is analogous to a Hamiltonian cycle in the visibility graph of the polygon. Therefore, visibility graphs are Hamiltonian. Finding this Hamiltonian cycle can be of great help when solving visibility graph recognition problems, in which one should decide whether a given graph is a visibility graph of a simple polygon; and reconstruction problems, which include constructing the polygon corresponding to a given visibility graph. These problems have been solved for the special...