Grant: Discovery Grants Program - Individual
University of Windsor
$34,000.00
Problems in Discrete and Computational Geometry
EF 2024-25
Résumé
My research area is discrete and computational geometry. In discrete geometry we investigate properties of geometric objects with the objective of using these properties to design efficient algorithms in the field of computational geometry. Computational geometry is a branch of computer science devoted to the study of algorithms and data structures for geometric problems. The input of a computational geometry problem consists of geometric objects (such as points, lines, circles, etc.) that come from application domains such as wireless networks, computer graphics, and robotics. An algorithm that is proven to be theoretically efficient often fails to be practically useful as it may be too complex to understand and implement or it may only become efficient when the size of the input is unreasonably large. The main goal of my ongoing research is to seek a greater understanding of different geometric structures to design simple algorithms for geometric problems. I provide a sample of the type of problems that I will concentrate on.
Technology used in daily life strongly relies on networks. For instance, one can think of the network of cellphone antennas in Canada. Since antennas have physical locations, this network can be modeled as a geometric graph where antennas are represented by points with connections/edges between any two antennas within each other's transmission range. Designing networks possessing various properties has a rich background. A required property for the cellphone network is that any two antennas should be able to exchange messages, and thus the network must be connected. This introduces the problem of computing a shortest connected network. Another problem is to replace omnidirectional antennas in wireless networks with directional antennas while maintaining network connectivity. Directional antennas are desirable in many ways, for example, they require lower transmission power and cause less interference. I will study these types of problems on geometric networks.
Many structures studied in discrete and computational geometry have a requirement of being non-crossing, i.e., their edges do not cross each other. This is particularly true for sub-structures of complete geometric graphs that involve a minimization criteria, for example, the shortest connected network and shortest connected path. However, when the underlying graph is not complete or when we deal with a maximization criteria the non-crossing property is not guaranteed. Crossings can cause errors, for example, interference between antennas, collision between moving objects, or inconsistencies in the layout of a VLSI circuit. I will focus on computing non-crossing structures in these circumstances.
A main framework that I exploit to solve geometric problems is to first extract various geometric and combinatorial properties involved in the input, and then combine these properties with suitable data structures to design efficient algorithms/solutions for the problem.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2020-04329
Name nom
Biniaz, Ahmad
Department département
School of Computer Science
Organization id
37
Institution établissement
University of Windsor
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2020
Award amount
34000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Problems in Discrete and Computational Geometry
Keywords
computational geometry; discrete geometry; graph algorithms; approximation algorithms; geometric graphs; euclidean spanning trees; geometric matchings; geometric optimization; enumerative lower bounds; non-crossing configurations
Application summary
My research area is discrete and computational geometry. In discrete geometry we investigate properties of geometric objects with the objective of using these properties to design efficient algorithms in the field of computational geometry. Computational geometry is a branch of computer science devoted to the study of algorithms and data structures for geometric problems. The input of a computational geometry problem consists of geometric objects (such as points, lines, circles, etc.) that come from application domains such as wireless networks, computer graphics, and robotics. An algorithm that is proven to be theoretically efficient often fails to be practically useful as it may be too complex to understand and implement or it may only become efficient when the size of the input is unreasonably large. The main goal of my ongoing research is to seek a greater understanding of different geometric structures to design simple algorithms for geometric problems. I provide a sample of the type of problems that I will concentrate on.
Technology used in daily life strongly relies on networks. For instance, one can think of the network of cellphone antennas in Canada. Since antennas have physical locations, this network can be modeled as a geometric graph where antennas are represented by points with connections/edges between any two antennas within each other's transmission range. Designing networks possessing various properties has a rich background. A required property for the cellphone network is that any two antennas should be able to exchange messages, and thus the network must be connected. This introduces the problem of computing a shortest connected network. Another problem is to replace omnidirectional antennas in wireless networks with directional antennas while maintaining network connectivity. Directional antennas are desirable in many ways, for example, they require lower transmission power and cause less interference. I will study these types of problems on geometric networks.
Many structures studied in discrete and computational geometry have a requirement of being non-crossing, i.e., their edges do not cross each other. This is particularly true for sub-structures of complete geometric graphs that involve a minimization criteria, for example, the shortest connected network and shortest connected path. However, when the underlying graph is not complete or when we deal with a maximization criteria the non-crossing property is not guaranteed. Crossings can cause errors, for example, interference between antennas, collision between moving objects, or inconsistencies in the layout of a VLSI circuit. I will focus on computing non-crossing structures in these circumstances.
A main framework that I exploit to solve geometric problems is to first extract various geometric and combinatorial properties involved in the input, and then combine these properties with suitable data structures to design efficient algorithms/solutions for the problem.