Categories
My Activities
- Winter School on Computational Geometry (WSCG)
- Labratory of Algorithm and Computational Geometry (ACG)
Projects >
|
Computational Geometry is a vast area of research focusing on designing algorithms for geometric problems. Despite the fact that these geometric problems come from the real world applications and the solutions proposed should work well in practice, the solutions proposed in computational geometry are based on the unrealistic assumption that the input data and computations involved are precise. Consequently, these algorithms fail to work in presence of real world imprecision. Therefore, there has emerged a growing interest in designing models that can take the imprecision into account. Region-based models are of the well-known models proposed, in which imprecision of each input point is a predefined region. In this thesis, we propose a new model for handling imprecision in the input data of a geometric problem. The proposed model, which is called λ-geometry, is a generalization of region-based models with the advantage that it can handle dynamic imprecision as well. The dynamic view in the model of λ-geometry can be seen as a trade-off between costs and benefits associated with the imprecision level λ. Thus, the model of λ-geometry with λ changing continuously is a useful tool for decision making in order to find the optimal level of the precision. The model of λ-geometry finds application in formulating the trade-offs that usually exist between the cost and the benefit in decision-making problems. Furthered, we study some basic computational geometry problems such as axis-aligned bounding box problem, closest and furthest pair problem and line stabber problem under the λ-geometry model.
Members:
Publications:.
We study the number of inducing n-gons in arrangements of n lines. Inducing n-gons is a n-gon which each line of the arrangement contains exactly one side of it. It is introduced by Bose et al. in2003, and after him there are some algorithms to prove that every simple arrangement of lines contains at least one inducing n-gon. Finding the number of these n-gons or at least establishing a lower/upper bound on the number of them is proposed by Ackerman et al. in 2009. We define arrangements of collinear segments and it is shown that counting the number of inducing n-gons in this class of arrangements is #P-complete. Publications:.
Biogeometry is an emerging scientific discipline at the interface between computational geometry, biochemistry and biophysics, statistics, and chemistry that brings together specialists in the above disciplines to develop new computational techniques and paradigms for representing, storing, searching, simulating, analyzing, and visualizing biological structures. Biogeometry embraces ideas from a wide range of areas of computer science and mathematics, including algorithms, geometry, topology, graphics, robotics, and databases to address some of the most fundamental biological problems such as structure-function relationships for biological molecules. … Members:
Publications: Publications:.
· Coverage and separability problems
Covering problem is one of the most
important and practical problems in
Computational Geometry, that has attracted
comprehensive attention in recent years.The problem statement is as follows:
Given a set of n points in the
Euclidean real plane and a geometric shape as the
covers,in this stage, an optimization problem shows
up as these cases:
separability problems:Given two colored point sets and ---the red and the blue point set, respectively---of total size in the plane, and a geometric shape called a separator, in a separability problem the goal is to decide whether one can place the separator such that it separates sets and completely. If such a placement is possible one often also wants to compute all such placements or the placement minimizing some cost function. There has been a fair amount of work on different kinds of separators. We study the problem of separating dichromatic point sets by means of a non-convex separator, namely an L-shape.
Members:
Publications:
Shape reconstruction is one of the most
challenging and crucial problems in several
computer science fields. In general, the
purpose of this problem is reconstructing a
well-defined structure (e.g. graphs,
polygons, parametric curves, etc) from some
sample points which are taken from an
unknown original shape. This problem can be
discussed in any dimension, but due to its
widespread applications, it is discussed in
two and three dimensions in literature.
Our goal in this project is presenting an
algorithm whose output is a simple polygon
and works well on both input types, dot
pattern and boundary sample. It
is called simple-shape due to its output
type and is based on observation of human
beings shape reconstruction process. We
combine some factors, which are important to
human beings, to build a balanced single
criterion and propose a simple, flexible and
robust algorithm. Also the algorithm can be
used to produce a polygon with
user-determined number of edges.
Members:
Publications:.:
· On K-modem Visibility and the k-modem art gallery problem We study a generalization of the classical problem of illumination of polygons. Instead of modeling a light source, we model a wireless device whose radio signal can penetrate a given number k of walls. We call these objects k-modems. We study the combinatorial and computational complexity aspects of the modem illumination problems. It is shown that every monotone polygon on n vertices can be illuminated with [n/(2k + 2)] k-modems and this bound is tight. We also show that any orthogonal polygon on 2m vertices, with or without hole, can be illuminated with a (m - 4)-modem for odd m and with a (m - 3)-modem for even m. The examples of generic 2m-gons show the tightness of these bounds on the power of the modem are presented. We also show that a 4-modem will be enough to illuminate the whole plane in the presence of a monotone orthogonal polygon. It is shown that a 4-modem is sometimes necessary. We also study the computational complexity of the k- modem art gallery problem. Specifically, the problem of determining the minimum number of the vertex k-modems to see a simple polygon is shown to be NP-Complete via a reduction from 3SAT
Members:
1. Mahsa Soheil Shamaee, Ali Mohades, Marzieh Eskandari, The k-modem art gallery problem, accepted in World Conference on Information Technology , 2010. 2. Mahsa Soheil Shamaee, Ali Mohades, Marzieh Eskandari, The illumination of polygonal regions with modems, in Proceedings of the Second Conference on Contemporary Issues in Computer and Information Science, 2011, 68-71. 3. Mahsa Soheil Shamaee, Ali Mohades, Marzieh Eskandari, Computational com plexity of k-modem are gallery problem, submitted in Discrete and computational geometry, 2011. 4. Mahsa Soheil Shamaee, Ali Mohades, Marzieh Eskandari, The illumination of polygonal regions with modems, submitted in CSI Journal on Computer Science and Engineering (JCSE-English Issue), 2011. 5. Mahsa Soheil Shamaee, Ali Mohades, Bahram Kouhestani, Marzieh Eskandari, On k-modem visibility , accepted in 2nd World Conference on Information Technology,2011. 6. Bahram Kouhestani, Farnaz Sheikhi, Mahsa Soheil Shamaee, Ali Mohades, Guarding a Terrain by a Single k-modem Watchtower, submitted in First CSUT Conference on Computer, Communication and Information Technologies (CSCCIT) , 2011.
· VisibilityWe consider a method of decomposing a simple polygon with some mirror segments that allows the preprocessing of the polygon to efficiently answer visibility queries of various form in an out put sensitive manner. Now we con compute visibility polygon of a query point in a simple polygon with one mirror segment in time O(n) Members:
Members:
Publications:
|
