 Winter School on Computational Geometry (WSCG)
 Labratory of Algorithm and Computational Geometry (ACG)
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. Regionbased models are of the wellknown 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 regionbased 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 tradeoff 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 tradeoffs that usually exist between the cost and the benefit in decisionmaking problems. Furthered, we study some basic computational geometry problems such as axisaligned bounding box problem, closest and furthest pair problem and line stabber problem under the λgeometry model.
Members:
Publications:.
We study the number of inducing ngons in arrangements of n lines. Inducing ngons is a ngon 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 ngon. Finding the number of these ngons 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 ngons in this class of arrangements is #Pcomplete. 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 structurefunction 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, respectivelyof 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 nonconvex separator, namely an Lshape.
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
welldefined 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 simpleshape 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
userdetermined number of edges.
Members:
Publications:.:
· On Kmodem Visibility and the kmodem 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 kmodems. 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)] kmodems 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 2mgons show the tightness of these bounds on the power of the modem are presented. We also show that a 4modem will be enough to illuminate the whole plane in the presence of a monotone orthogonal polygon. It is shown that a 4modem 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 kmodems to see a simple polygon is shown to be NPComplete via a reduction from 3SAT
Members:
1. Mahsa Soheil Shamaee, Ali Mohades, Marzieh Eskandari, The kmodem 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, 6871. 3. Mahsa Soheil Shamaee, Ali Mohades, Marzieh Eskandari, Computational com plexity of kmodem 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 (JCSEEnglish Issue), 2011. 5. Mahsa Soheil Shamaee, Ali Mohades, Bahram Kouhestani, Marzieh Eskandari, On kmodem 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 kmodem 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:
