Sharif Digital Repository

In this thesis, we considered several types of the visibility problem. These problems include computing the visibility polygon of a point observer inside a polygonal domain, maintaining visibility polygon of a moving point observer, visibility coherence in space, maintaining visibility polygon of a moving segment observer and visibility dependent simplification. Furthermore, we considered these problems in both offline and streaming settings. These problems arise in different practical areas, such as computer graphics, machine vision, robotics, motion planning, geographic information systems (GIS) and computational geometry. We obtained effective theoretical results as well as superior... 

Planar visibility computing is defined as determining the region of the plane that is visible from a specific observer. This concept has many applications in computer graphics, robotic and computer games. In this thesis we consider two visibility problems: the visibility testing problem which checks the inter-visibility of two objects and the visibility counting problem which counts the number of visible objects from an observer. For these problems we propose new algorithms which have some improvements compare to the previous ones  

A basic technique in data reduction is to approximate a collection of data by another collection of smaller size. Then, the resulted data are easier to be processed or maintained. An example of such large scale data is the ordered sequence of n points describing a path or a region boundary. We are given a sequence of points p , p , ..., p , and we consider the 1 2 n problem of approximating these points by a path with k < n line segments which error of this path is not greater than special value. Various criterions are defined to compute the path simplification error.This problem can be used in GIS, Image Processing and Computer Graphics problems. In this thesis, we consider special case... 

Finding a path between two specified points is one of the most common problem in computational geometry. The minimum-link path problem is in this category. The minimum-link path between two points is the path between these points with the minimum number of segments. Minimum-link paths have application in areas such as computer graphic, geographic information systems, robotics, image processing, cryptography and VLSI.In this thesis we study variations of the minimum link path problem. Specifically we consider the constrained minimum-link paths in which the path must passes through some given
regions. We detected a flaw in a previously presented algorithm and propose a method to fix this... 

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... 

In the competitive facility location problem, two service providers fight over winning consumers by establishing a series of well-located facilities on the line. The consumers seek their required services from the facility which is closest to them. The order in which service providers locate and build their facilities is as follows: the first service provider establishes k facilities after which the second service provider locates another k facilities and this goes on for m rounds. The payoff of each service provider equals the number of consumers that choose that provider’s facilities to seek service from. In this dissertation, we address different types of this problem and try to analyze... 

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, path planning in unknown environment is considered. It is assumed that the robot’s sensors are the only tools to collect information from the scene. Volume of the information gathered from the environment depends on the capability of the sensor. So, a detour from the optimal path is unavoidable. In this research, the basic robot is equipped with a minimal sensing system that only detects the iscontinuities in depth information (gaps). We present some online search strategies that guide such a robot to navigate unknown streets from a start point s to reach a target point t. Then, we empower the robot by adding a compass to patrol more general classes of polygons. We present... 

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... 

In this thesis, we present different algorithms for path simplification. We first study this problem under area measures. We present an approximation algorithm for sum-area measure and an optimal algorithm for diff-area measure. Both of these algorithms can be applied on general paths. Moreover, we study the homotopic path simplification. We present a general framework for path simplification which work for desired error measure. We first present a strongly homotopic simplification algorithm for x-monotone paths. Also, we study the strongly homotopic simplification for general paths. We present a geometric tree data structure and present an algorithm based on this data structure.... 

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,... 

In this thesis, we investigate some problems in Sublinear field. We designed an algorithm that approximate the minimum distance of a shape to be a disk. In the first algorithm, we assumed that its input is a matrix and 1s in the matrix represent black pixels and 0s in the matrix represent white pixels. Also, we designed another algorithm that its input is a data structure contains the positions of a convex shape and we can sample uniformly from its pixels. In this problem similar to the first problem we must approximate the minimum distance of a shape to be a disk. Finally, we designed an algorithm for counting disks in a matrix. The input is a matrix that it contains some disks which have... 

Visibility graph is a graph that comprises information about visibility of a set of objects in 2 or 3-dimensional space. By constructing this graph with respect to conditions of environment one can answer questions like minimum Euclidean distance. Inverse of this procedure is required too; i.e. knowing geometrical structure of objects and information about their visibility we want to guess their location in space and, as the saying goes, reconstruct the environment. For example some methods to reconstruct specific polygons knowing which vertices each vertex sees is proposed. In this dissertation we try to reconstruct a 2-dimensional environment that only has two x-monotone paths (chains)  

TIN (Triangulated Irregular Network) is a Data Structure for storing and manipulating surfaces like maps in GIS applications or 3D models in game engines or Vector Fields . A TIN contains a set of triangulated vertices (which has irregular distribution) and each vertex shows a point in space . We trying to find the smallest possible set (optimal solution) of vertices from input surface (which given as a TIN) to approximate input surface with epsilon error which is given as input. also, surface simplification problem is a member of NP-Hard class. The hardness of problem makes it infeasible to find an optimal solution in polynomial time. So we try finding an approximate algorithm for this... 

A triangulated irregular network (TIN) is a data structure that is usually used for representing and storing a geographic surface. TIN is a set of points and some segments between them that are distributed in space such that projection of segments on the plane is a triangulation for projection of points. Visibility graph of points is a graph in which there is a vertex correspond to each point of TIN and there is an edge between two vertexes if corresponding points can see each other. TIN’s visibility graph has many applications; for example, finding some points in a geographic surface that they can see all of the surface together, they are good places for radars.in first section of this... 

Finding optimize tours on a given sequence of objects has applications in robitic. A tour on a given sequence of objects is a path that touchs or cuts each of them, in order. In STOC′03 it is shown that finding such a shortest path for a sequence of convex polygons is polynomial solvable and it is NP-hard for non-convex polygons with intersections. The complexity of the problem for disjoint polygons is asked as the importest open peoblem. In 2008 an approximation algorithm is presented for this problem. We show that the problem is NP-hard in each Lp norm, even if each polygon consists of two unit line segments. Also, in 2003 the problem, with obstacles has been proposed as a future work. An... 

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... 

If we consider a point set on the plane as the vertices and straight-line segments between them as the edges of a graph, and weight of each edge is equal to its Euclidean length, from this kind of graphs, triangulation is the graph with maximum number of the edges. In a triangulation, dilation of any two vertices is equal to the ratio of their shortest path length to their Euclidean distance, and dilation of the triangulation is defined as the maximum dilation of any pair of its vertices. Dilation is a characteristic that shows how much a triangulation approximates a complete graph. In the minimum dilation triangulation problem, the objective is to find a triangulation of a given set of... 

This thesis is concerned with a fundamental problem in computational geometry. This problem inspects covering a space with a set of points provided that each point of the space is visible to at least one point from the selected subset. Applications of these problems are in the areas such as geographic information systems (GIS), robotics,computer graphics and the military.The investigated space is a planar rectangular region which is partitioned into smaller rectangles by connected edges. The objective of this study is to find an optimized corridor; i.e., a connected subset of edges which contains at least one point from each rectangle. For the minimum diameter corridor problem, an exact...