Prof. Ali Mohades - Board of ACG Group

 

  • Imprecise data

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:

  • Mansoor Davoodi
  • Farnaz  Sheikhi
  • Payam khanteimoory
  • Hajaghaee
  • Bany Assady
  • Frouzesh

Publications:.

  1. M. Davoodi, P. Khanteimouri, F. Sheikhi, A. Mohades, Data Imprecision under λ-Geometry: Finding the Largest Axis-Aligned Bounding Box, EuroCG, pp. 135-139, 2011.

  2. J. Ahmad, A. Mohades, M. Davoodi, F. Sheikhi, Convex Hull Of Imprecise Points Modeled By Segments In The Plane, In 26th European Workshop on Computational Geometry, pp. 193-197, 2010.

    

  • Inducing n- gons

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

  1. M. Davoodi, P. Khanteimouri, F. Sheikhi, A. Mohades, Data Imprecision under λ-Geometry: Finding the Largest Axis-Aligned Bounding Box, EuroCG, pp. 135-139, 2011.

  2. M. Abedin, A. Mohades, M. Eskandari. On Inducing $n$-gons, In the 23rd Canadian Conference on Computational Geometry, 13(6): 495-501, 2011.

  3. M. Abedin, A. Mohades, M. Eskandari. Bounds on the Number of Inducing n-gons in Specific Arrangements, In the 2nd International Conference on Contemporary Issues in Computer and Information Sciences, 174-177, 2011.

  4.  M. Abedin, A. Mohades, M. Eskandari. (2011). On Inducing n-gons, In the International Journal of Computational Geometry and Applications, (submitted)

 

  • BIOGEOMETRY: APPLICATIONS OF COMPUTATIONAL GEOMETRY TO MOLECULAR STRUCTURE

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:

  •  Hadi Banaee
  •  Leila Ghanbari
  •  Bahram Kouhestani
  •  Sedigheh Mahdavi

Publications:

Publications:.

  1. Gene Expression Similarity with Polygonal Chain Alignme. The 2nd International Conference on Contemporary Issues in Computer and Information Sciences - CICIS 2011(Best Paper Award)
  2. Gene Expression Similarity with Polygonal Chain Alignment.  CIENTIA IRANICA International Journal of Science and Technology (Submitted.)

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:

  1. The size of the geometric shape: Covering all given points with the numbers of copies of given object such that the area of the biggest cover is as small as possible.
  2. The number of points covered: The size of the covers are fixed and the goal is to locate them in a way that the number of points covered is maximized/minimized (due to problem statement).

 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:

  • Farnaz  Sheikhi
  • Marzieh Eskandari
  • Payam khanteimoory
  • Mansoor Davoodi
  • Ali Najafee

Publications:

  1. F. Sheikhi, M. de Berg, A. Mohades, and M. Davoodi. Finding monochromatic L-shapes in bichromatic point sets. In Proc. of the 22nd Canadian Conference on Computational Geometry, 269-272, 2010.   
  2.  F. Sheikhi, A. Mohades, and M. Davoodi. An improved algorithm for finding monochromatic L-shapes in bichromatic point sets. In Proc. of the Contemporary Issues in Computer and Information Sciences, 36-39, Zanjan, Iran, 2011.

     

  •  Polygonal Shape Reconstruction

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:

  1. Amin Gheibi
  2. Mansour Davoodi
  3. Ahmad Javad
  4. Fatemeh Panahi
  5. Mohammad MohammadPour Aghdam
  6. Mohammad Asgaripour

Publications:.:

  1. “Polygonal Shape Reconstruction in the Plane” (simple-shape), A.Gheibi, M.Davoodi, A.Javad, F.Panahi, M.Aghdam, M.Asgaripour, A.Mohades, IET Computer Vision Journal, 2011, Vol. 5, Iss. 2, pp. 97–106

    

 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,
  2. Bahram Kouhestani,
  3. Farnaz Sheikhi,
  4. Marzieh Eskandari,

    Publications:

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.

         Visibility

We 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:

  • Maedeh Sadat Tahaei
  • Dr. Bahram Sadeghi Bigham
  • Roghayeh Alemy

Publications:

  1. “Polygonal Shape Reconstruction in the Plane” (simple-shape), A.Gheibi, M.Davoodi, A.Javad, F.Panahi, M.Aghdam, M.Asgaripour, A.Mohades, IET Computer Vision Journal (submitted, August 2009).