Sharif Digital Repository

We study the problem of preclustering a set $B$ of imprecise points in~$\Reals^d$: we wish to cluster the regions specifying the potential locations of the points such that, no matter where the points are located within their regions, the resulting clustering approximates the optimal clustering for those locations. We consider $k$-center, $k$-median, and $k$-means clustering, and obtain the various results. Then we study the higher order Voronoi Tessellations as an important concept in clustering area. Generalizing Lee’s inductive argument for counting the cells of higher order Voronoi tessellations in $\Reals^2$ to $\Reals^3$, we get precise relations in terms of Morse theoretic quantities... 

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

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

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

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

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

Our bodies are made from billions of individual cells and DNA is the control central of each cell. In addition to linear DNAs, there are circular DNAs in nature. Circular DNAs cause new topological structures such as knots and catenanes. These topological structures form during biological proccesses such as replication. For example during replication, two daughter circular DNAs may link together and form catenanes. Anzymes named topoisomerases can simplify the topology of circular DNAs. Type 2 topoisomerases is used for simplification of catenanes. These anzymes do it with breaking a double-strand DNA and passing through another one. In comparison with DNAs, topoisomerases are very small and... 

In the behavior of many convex optimization problems with random constraints in high dimensions, sudden changes or phase transitions have been observed in terms of the number of constraints. A well-known example of this is the problem of reconstructing a thin vector or a low-order matrix based on a number of random linear observations. In both cases, methods based on convex optimization have been developed, observed, and proved that when the number of observations from a certain threshold becomes more (less), the answer to the problem with a probability of close to one (zero) is correct and the original matrix is reconstructed. Recently, results have been obtained that explain why this... 

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)  

Incoporating Gauge theory to study 4-dimensional manifolds,initiated by works of Donaldson,leading to resolve many problems of 4-dimensional topology.after Donaldson ,Seiberg and Witten introduced a novel Gauge theory that we will introduce and study some application of this theory.at beginning, we will establish Seiberg-Witten equation on these manifolds, following that we investigate moduli space of solutions of Seiberg Witten equations and later we define Seiberg - Witten invariants on these manifolds.at f we probe some applications of Seiberg-Witten invariants in Symplectic Geometry and we will show that Seiberg-Witten invariants are non-zero for Symplectic manifolds with canonical SpinC... 

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

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

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

In this research, we introduce the concept of local spanners for planar point sets with respect to a family of regions and prove the existence of local spanners of small size for some families. For a geometric graph $G$ on a point set $\points$ and a region $R$ belonging to a family $\Re$, we define $G \cap R$ to be the part of the graph $G$ that is inside $R$. An $\Re$-local $t$-spanner is a geometric graph $G$ on $\points$ such that for any region $R$ in $\Re$, the graph $G\cap R$ is a t-spanner with respect to $G_{c}(\points) \cap R$, where $G_{c}(\points)$ is the complete geometric graph on $P$.For any set P of n points and any constant $\eps > 0$, we prove that $P$ admits local $(1 +... 

In present study, bioelectrochemical degradation of oxalate as a substance which its concentration in kidney leads to urolithiasis in a microfluidic microbial fuel cell (MFC) was investigated. In addition, to define a novel application for the microfluidic MFC, measurement and monitoring of oxalate concentration were studied. This application can introduce the system as an implantable medical device for medical usage of urolithiasis and hyperoxaluria diseases. In this work, by designing and fabrication of two MFCs including a large-scale and microfluidic one, and measuring the outlet concentration of oxalate in the large-scale system, the outlet concentration of oxalate at microfluidic MFC... 

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

Tropical algebraic geometry is a fairly new branch in geometry which is called so in honor of Brazilian mathematician Imre Simon who was pioneer of this field.The set equipped with the addition and multiplication is a semifield.Algebraic geometry objects like algebraic varieties can be defined over.Polynomials and rational functions are defined over.The functions that they define are piecewise linear and concave functions and the set of points where they are nonlinear is a tropical variety which is a concave polyhedral. Thus, tropical algebraic geometry is a piecewise linear version of algebraic geometry.Another approach to tropical algebraic geometry comes back to the works of Russian... 

In this thesis, we study the problem of guarding art galleries with sliding cameras and k-transmitter. This problem is a new version of classic art gallery problem, which the goal is covering the entire region with minimum number of guards. In early version of art gallery problem, usually point guards with 360 degree vision were used, but in this thesis we use sliding cameras instead. This new guards specified by an orthogonal segment which entirely settled interior of polygon and can see up to k walls. Based on this two notions (sliding camera and k-transmitter) we say that a guard can see point p, if the intersections number of normal segment through p to corresponding segment of guard...