Reference number : GC-2017-Q1-03225, amendment number : , agreement type : G, recipient legal name : Smid, Michiel (Carleton University), recipient country : CA, recipient province : nan, recipient city : Ontario, recipient postal code : nan, program name english : Discovery Grants Program - Individual, program name french : Programme de subventions à la découverte - individuelles, program purpose english : The general theme in this project is the design and analysis of optimization algorithms for geometric problems. The research will concentrate on the following topics: 
Geometric Spanner Networks: How to construct a sparse network that connects a given set of sites such that for any two sites, their shortest-path distance in the network is approximately equal to their straight-line distance. Given such a network, how to use geometric information to compute (exact or approximate) shortest paths between any two given sites, how to compute such a path incrementally using only local information. 
Geometric Graph Augmentation: How to add a small number of links to an existing geometric network, such that the longest distance in the resulting augmented network is minimized. For a given geometric network and given location on it, how to compute the locations in the network that are farthest away. 
Optimal Subgraphs of Geometric Graphs: Given a set of red and blue points, how to compute a shortest (or longest) spanning tree in which each link connects a red point with a blue point. How to compute such a tree if no two links are allowed to cross. 
Geometric Data Structures: How to organize geometric data, such that an informative "summary" of the subset of the data that is contained in a query region can be computed. How to organize geometric data in which each data element belongs to some category, such that the different categories inside a query region can be computed., program purpose french : The general theme in this project is the design and analysis of optimization algorithms for geometric problems. The research will concentrate on the following topics: 
Geometric Spanner Networks: How to construct a sparse network that connects a given set of sites such that for any two sites, their shortest-path distance in the network is approximately equal to their straight-line distance. Given such a network, how to use geometric information to compute (exact or approximate) shortest paths between any two given sites, how to compute such a path incrementally using only local information. 
Geometric Graph Augmentation: How to add a small number of links to an existing geometric network, such that the longest distance in the resulting augmented network is minimized. For a given geometric network and given location on it, how to compute the locations in the network that are farthest away. 
Optimal Subgraphs of Geometric Graphs: Given a set of red and blue points, how to compute a shortest (or longest) spanning tree in which each link connects a red point with a blue point. How to compute such a tree if no two links are allowed to cross. 
Geometric Data Structures: How to organize geometric data, such that an informative "summary" of the subset of the data that is contained in a query region can be computed. How to organize geometric data in which each data element belongs to some category, such that the different categories inside a query region can be computed., agreement title english : Optimization Problems in Computational Geometry, agreement title french : Optimization Problems in Computational Geometry, agreement number : RGPIN, agreement value : 170000.0, agreement start date : 2017-05-10, agreement end date : nan, description english : nan, description french : nan, expected results english : nan, expected results french : nan, additional information english : Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023), additional information french : Subvention ou bourse octroyée s'appliquant à plus d'un exercice financier. (2017-2018 à 2022-2023), owner organization : nserc-crsng, owner organization title : Natural Sciences and Engineering Research Council of Canada | Conseil de recherches en sciences naturelles et en génie du Canada