| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | August 20, 2009 |
| Latest Amendment Date: | August 20, 2009 |
| Award Number: | 0915984 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Dmitri Maslov
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 1, 2009 |
| End Date: | August 31, 2013 (Estimated) |
| Total Intended Award Amount: | $410,000.00 |
| Total Awarded Amount to Date: | $410,000.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
506 S WRIGHT ST URBANA IL US 61801-3620 (217)333-2187 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
506 S WRIGHT ST URBANA IL US 61801-3620 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | COMPUTATIONAL GEOMETRY |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
Computational geometry is the branch of theoretical computer science devoted to the design, analysis, and implementation of geometric algorithms and data structures. Computational geometry has deep roots in reality: Geometric problems arise naturally in any computational field that simulates or interacts with the physical world---computer graphics, robotics, geographic information systems, computer aided-design, and molecular modeling, to name a few---as well as in more abstract domains such as combinatorial geometry and algebraic topology.
This research focuses on fundamental problems in computational geometry. These problems include set-cover, hitting set, independent set, and other related problems. These problems have numerous applications from wireless networking to optimization.
The main theme of this research is to combine ``classical'' Computational Geometry techniques (like cuttings, epsilon-nets, etc) together with techniques used in Operation Research (Linear Programming, rounding techniques, etc).
This research aims to greatly improve our understanding of the structure of these fundamental problems. The research may lead to improved approximation algorithms for these problems.
The algorithms and insights obtained from the technical work will benefit computer science and related disciplines where geometric algorithms are widely used. This research has potential to broaden the scope of Computational Geometry by introducing new techniques into the field.
A book partially based on the research in this award will be published in the near future. This will make the developed techniques available to wide audience consisting of students and researchers from several disciplines include engineering, mathematics, and the natural and social sciences.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
Please report errors in award information by writing to: awardsearch@nsf.gov.
