Grant: Discovery Grants Program - Individual
Simon Fraser University
$35,000.00
Complexity issues in geometric and combinatorial arrangements
EF 2010-11
Résumé
One major research direction of this proposal is the study of arrangements of simple geometric objects, such as lines, segments, disks, triangles, etc. and find out what makes them simple or complex, when can they avoid certain patterns and answer many similar questions.
A simple example is the study of the complexity of the union of geometric regions. The union of n line segments can partition the plane into a quadratic number of disconnected regions, but the complement of the union of n discs is consist of just a linear number of regions and the boundary can be described in linear time (linear complexity). Long and narrow triangles behave like segments, while ""fat"" triangles behave like circular disks with regard to the complexity of their union. I propose to conduct research in three and higher dimensions where there exist some partial results on the subject but the situation is much less understood than in the planar case.
Another problem I propose to study is the conflict-free coloring problem. Assume a few radio stations (with known reception ranges) are used to broadcast a station and one wants to assign frequencies to these stations. A user can only receive a station if he is within the reception range of that station but outside the range of all other stations that broadcast on the same frequency. What is the minimum number of frequencies that must be used if we want each user within the range of some station to be able to receive some station? What is the worst case number of frequencies needed as a function of the broadcast stations? The answer depends on the geometric shape of the broadcast regions. It is well understood for circular (disk) regions and somewhat well for axis-parallel rectangles, but a lot of further study is needed to tackle the problem for other types of regions.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
329257-2009
Name nom
Tardos, Gabor
Department département
Computing Science
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2010
Competition year année de concours
2009
Award amount
35000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2703
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Complexity
Research subject fr
Complexité
Partie
2
Nb partie
5
Application title
Complexity issues in geometric and combinatorial arrangements
Keyword
NSERC
Application summary
One major research direction of this proposal is the study of arrangements of simple geometric objects, such as lines, segments, disks, triangles, etc. and find out what makes them simple or complex, when can they avoid certain patterns and answer many similar questions.
A simple example is the study of the complexity of the union of geometric regions. The union of n line segments can partition the plane into a quadratic number of disconnected regions, but the complement of the union of n discs is consist of just a linear number of regions and the boundary can be described in linear time (linear complexity). Long and narrow triangles behave like segments, while ""fat"" triangles behave like circular disks with regard to the complexity of their union. I propose to conduct research in three and higher dimensions where there exist some partial results on the subject but the situation is much less understood than in the planar case.
Another problem I propose to study is the conflict-free coloring problem. Assume a few radio stations (with known reception ranges) are used to broadcast a station and one wants to assign frequencies to these stations. A user can only receive a station if he is within the reception range of that station but outside the range of all other stations that broadcast on the same frequency. What is the minimum number of frequencies that must be used if we want each user within the range of some station to be able to receive some station? What is the worst case number of frequencies needed as a function of the broadcast stations? The answer depends on the geometric shape of the broadcast regions. It is well understood for circular (disk) regions and somewhat well for axis-parallel rectangles, but a lot of further study is needed to tackle the problem for other types of regions.