Grant: Discovery Grants Program - Individual
University of Waterloo
$46,000.00
Geometric Data Structures: A Modern Perspective
FY 2016-17
Summary
Although data structures in computational geometry have been studied for over four decades, recent years have seen groundbreaking new developments for some of its most fundamental problems, including (orthogonal and nonorthogonal) range searching, (approximate) nearest neighbor search, (dynamic) point location, and more. In this proposal, I plan to not only continue studying the fundamental problems of the area, but also investigate new problems arising from modern needs. For example:
* Today's world of ""big data"" makes space-efficient geometric data structures all the more important, in both traditional computational models as well as emerging data streaming and sketching models.
* Various modern-day applications require extending standard geometric data structure problems to different settings (e.g., time-windowed, kinetic, or high-dimensional), or introducing variations on old problems (e.g., range-aggregate queries), all leading to interesting new challenges.
* There have been some surprising recent applications of geometric data structures to non-geometric problems, on strings and text indexing; it will be exciting to find further connections between computational geometry and other areas of algorithms.
The proposal is expected to produce not only new algorithms for specific problems but also new general techniques and deeper understanding of geometric data structures.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2016-03875
Name nom
Chan, Timothy
Department département
Computer Science, David R. Cheriton School of - Computer Science, David R. Cheri
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2016
Award amount
46000
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
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
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
Partie
1
Nb partie
5
Application title
Geometric Data Structures: A Modern Perspective
Keyword
NSERC
Application summary
Although data structures in computational geometry have been studied for over four decades, recent years have seen groundbreaking new developments for some of its most fundamental problems, including (orthogonal and nonorthogonal) range searching, (approximate) nearest neighbor search, (dynamic) point location, and more. In this proposal, I plan to not only continue studying the fundamental problems of the area, but also investigate new problems arising from modern needs. For example:
* Today's world of ""big data"" makes space-efficient geometric data structures all the more important, in both traditional computational models as well as emerging data streaming and sketching models.
* Various modern-day applications require extending standard geometric data structure problems to different settings (e.g., time-windowed, kinetic, or high-dimensional), or introducing variations on old problems (e.g., range-aggregate queries), all leading to interesting new challenges.
* There have been some surprising recent applications of geometric data structures to non-geometric problems, on strings and text indexing; it will be exciting to find further connections between computational geometry and other areas of algorithms.
The proposal is expected to produce not only new algorithms for specific problems but also new general techniques and deeper understanding of geometric data structures.