COMPUTATIONAL and ALGORITHMIC REPRESENTATIONS of GEOMETRIC OBJECTS (CARGO)

A program to foster collaborations involving mathematical scientists, computer scientists, and other researchers and practitioners in an emerging interdisciplinary area


Program Solicitation

NSF 01-111



DIRECTORATE FOR COMPUTER AND INFORMATION SCIENCE AND ENGINEERING
      DIVISION OF COMPUTER-COMMUNICATIONS RESEARCH
DIRECTORATE FOR MATHEMATICAL AND PHYSICAL SCIENCES
      DIVISION OF MATHEMATICAL SCIENCES



FULL PROPOSAL DEADLINE(S): September 4, 2001

 




DARPAlogo  DARPA

NSF Logo  NATIONAL SCIENCE FOUNDATION





Small NSF logo

   The National Science Foundation promotes and advances scientific progress in the United States by competitively awarding grants and cooperative agreements for research and education in the sciences, mathematics, and engineering.

   To get the latest information about program deadlines, to download copies of NSF publications, and to access abstracts of awards, visit the NSF Web Site at:

https://www.nsf.gov

  • Location:
4201 Wilson Blvd. Arlington, VA 22230
  • For General Information (NSF Information Center):
(703) 292-5111
  • TDD (for the hearing-impaired):
(703) 292-5090
  • To Order Publications or Forms:
Send an e-mail to: pubs@nsf.gov
or telephone: (301) 947-2722
  • To Locate NSF Employees:
(703) 292-5111
























SUMMARY OF PROGRAM REQUIREMENTS



GENERAL INFORMATION

Program Title: COMPUTATIONAL and ALGORITHMIC REPRESENTATIONS of GEOMETRIC OBJECTS (CARGO)

Synopsis of Program: The Division of Computer and Communications Research (C-CR)and the Division of Mathematical Sciences (DMS) of the National Science Foundation (NSF) and the Defense Sciences Office of the Defense Advanced Projects Research Agency (DARPA) plan to support research and development teams focusing on mathematical and computational innovations relevant to representation and computational manipulation of geometrical objects. These awards will be administered by NSF. Areas of specific interest include:

- Computational Topology and Geometry
- Computational and Geometric Cartography, including Spatial Statistics
- Geometric aspects of Graphics and Computer-Aided Design (CAD)

We particularly encourage proposals for efforts involving collaborations of experts in the mathematical and computational sciences with other scientists, engineers, and practitioners representing diverse application areas.

Proposals for incremental improvements or ongoing efforts will not be selected for funding.

Cognizant Program Officer(s):

Applicable Catalog of Federal Domestic Assistance (CFDA) Number(s):

ELIGIBILITY INFORMATION

AWARD INFORMATION

PROPOSAL PREPARATION AND SUBMISSION INSTRUCTIONS

A. Proposal Preparation Instructions

B. Budgetary Information

C. Deadline/Target Dates

D. FastLane Requirements

PROPOSAL REVIEW INFORMATION

AWARD ADMINISTRATION INFORMATION












TABLE OF CONTENTS



SUMMARY OF PROGRAM REQUIREMENTS

  1. INTRODUCTION
  2. PROGRAM DESCRIPTION
  3. ELIGIBILITY INFORMATION
  4. AWARD INFORMATION
  5. PROPOSAL PREPARATION AND SUBMISSION INSTRUCTIONS
    1. Proposal Preparation Instructions
    2. Budgetary Information
    3. Deadline/Target Dates
    4. FastLane Requirements
  6. PROPOSAL REVIEW INFORMATION
    1. NSF Proposal Review Process
    2. Review Protocol and Associated Customer Service Standard
  7. AWARD ADMINISTRATION INFORMATION
    1. Notification of the Award
    2. Award Conditions
    3. Reporting Requirements
  8. CONTACTS FOR ADDITIONAL INFORMATION
  9. OTHER PROGRAMS OF INTEREST






I. INTRODUCTION

Computational geometry has proven to be both a rich and highly productive area of mathematical and computational science research, with numerous applications in such fields as computer graphics, robotics, and computer-aided design. To date, most of the activity has been focused on discrete problems and has made extensive use of combinatorial techniques to address these problems. There is a need to extend the current body of work in computational geometry, where objects are typically represented by point sets, polygons, or polyhedra, to include continuous domains, curved surfaces, and higher dimensional objects. Such extensions are expected to bring computational geometry into contact with many areas in classical geometric topology, just as the mainstream computational geometry led to connections with combinatorial geometry.

Many of the extensions sought impinge upon the newly emerging area of computational topology, in which foundational research has begun separately within the topology, computational geometry, computer graphics, and other communities of mathematical and computational science researchers. Each of these fields has developed its own approach to investigating problems in shape representation, manipulation, and analysis. So far, algorithms are typically specific to certain data representations and underlying topological questions common to all the approaches have not received adequate attention. In addition to the intrinsic mathematical value of this new vein of research, there is reason to expect that computational topology can lead to well-founded and robust algorithms for computer-aided design, graphics and visualization, and terrain analysis that offer substantial advantages over current algorithms that are largely limited to discrete geometric computations which approximate underlying problems involving smooth or piecewise smooth objects. Additionally, there is a need to introduce spatial statistics into computational representations of geometrical and topological objects, to account for uncertainty in data and computational errors. This has not been extensively explored and exhibits great potential.

This solicitation aims both to replace currently isolated research niches in computational topology with a cohesive research community, to harness the potential of this area of research in a wide spectrum of applications, and to impact the research community by enlarging the pool of principal investigators.

II. PROGRAM DESCRIPTION

APPLICATION DOMAINS

Research in the areas outlined above is expected to have significant impact across numerous application domains, including engineering design, modeling of physical systems, and several aspects of computational and geometric cartography.

The efficiency and reliability of modern CAD systems, as well as the compatibility of CAD models with downstream applications (e.g., stress analysis and computational fluid dynamics), are severely limited by the persistent lack of robust algorithms for computing surface intersections and trimmed surfaces. The resolution of these problems, which can have tremendous economic impact by reducing product design and verification cycles, is expected to require interdisciplinary expertise from topology, algebraic and differential geometry, numerical analysis, computational algebra, and the engineering application contexts. The issue of guaranteed "topological consistency" must be a central guiding principle in the development of innovative new algorithms and approaches to these fundamental CAD problems. Bringing collaborative teams of mathematicians, computer scientists, and engineers together to explore the development and application of Computational Topology in the context of CAD is a great opportunity for providing coherence and basis to this important technology.

The major problem in computational and geometric cartography is developing representations that preserve large complexes of long-range and non-linear elevation data relationships, such as drainage networks. Traditional representations (e.g., linear combinations of basis functions) generally do not respect such relationships and are hence inadequate for many problems of interest. To pass to the next level of sophistication will most likely require topological input. For example, metrics that capture such relationships are important in connection with the development of interpolation and compression methods that preserve essential derived properties, such as drainage and visibility, which may be more crucial than minimizing elevation errors.

The problem of topological consistency, in the context of terrain analysis, is also present in the generation of the combined obstacle overlay for mobility analysis. Overlay data related to terrain features (e.g., vegetation, transportation routes, hydrology, drainage) are acquired by various means. Thus they lack topological consistency in addition to possessing inherent error. These characteristics of the data raise several avenues of investigation, including analysis of output versus input accuracy, the computational benefits of employing "just good enough" algorithms, and the manifestation of errors in input data at different levels of a hierarchical representation structure. Robust solutions, tolerant of data errors, although possibly suboptimal, are desirable. Here, analysis of error propagation in spatial networks of differing resolution and accuracy is of great computational benefit. Useful solutions will execute quickly on large data sets and will typically employ compact data structures that are easy to implement and test, consume less bandwidth, and are amenable to parallel implementation.


TEAMING

An ideal team would include expertise in the mathematical sciences, computer science, computational science, and engineering, and would have connections to industry or government laboratories. An underlying awareness of real-world needs (which may arise from industrial or defense applications) and the ultimate impact of the proposed activity on such needs will be a central criterion in proposal evaluation. Expertise in computational science, algebra, topology, all areas of geometry, spatial statistics, compiler design, and computer graphics could benefit such teams.

We particularly encourage proposals for efforts involving collaborations of experts in the mathematical and computational sciences with other scientists, engineers, and practitioners representing diverse application areas. Proposals for incremental improvements or ongoing efforts will not be selected for funding.

Potential participants seeking collaborators are encouraged to see the 'Team Building' information below.


PROPOSAL CONTENTS

Proposals should address the major technical themes outlined above in integrated and mathematically rigorous fashion and in contexts consistent with the goals of this effort. In addition to offering substantial scientific innovation, proposals should also address model problems, demonstrations, validation, and technology transfer relevant to industrial and/or defense applications of these innovations.

Integration of research and education is of increasing importance across all NSF programs. Proposals should present a plan describing how the proposed effort will contribute to this objective.


TEAM BUILDING

There may be individual researchers, or small groups, or potential industrial collaborators who may be able to contribute effectively to parts of this activity but who might wish assistance in forming teams. The following mechanism is designed to accommodate such individuals:

1. Any such individual, or group, should prepare an e-mail message, straight ASCII text (unformatted, NOT TeX or any word processor) that will be intended for potential collaborators in the following format:

To: CARGO@NSF.GOV

Subject: (1 Line, describes area of expertise or competence); example:

Subject: Computational algorithm design,
Subject: Materials Science, experience in casting thin vanilla filmed flubber alloys
Subject: Lg Scale Simulation, Algorithm Design with experience in distributed architectures

Body of Message: Not more than 120 lines, 75 characters per line, to include

Brief CV
References to relevant publications (if appropriate)
Pointers to web pages or other information, if desired.
A somewhat more detailed description of what the sender(s) can contribute to the effort, and what sorts of collaborators they are looking for.

2. Send this message to the email address as given NO LATER THAN June 22, 2001. We will acknowledge each message. We will truncate messages longer than 120 lines.

3. We will send a set of ALL the received email messages, unedited, to the addressees who submitted mail messages to CARGO@NSF.GOV; this will be mailed out electronically the week of June 25. We will be essentially acting as a vehicle for distributing messages to "each other" without interfering in any way. Neither NSF nor DARPA will in any way edit nor attempt to verify the accuracy or credentials of any of the mail messages or the senders.

4. Recipients of this information will be free to contact and interact with each other as they wish.


III. ELIGIBILITY INFORMATION

The categories of proposers identified in the Grant Proposal Guide are eligible to submit proposals under this program announcement/solicitation.

IV. AWARD INFORMATION

It is anticipated that the total amount available will be about $4,000,000 in FY2002. Estimated program budget, number of awards and average award size/duration are subject to the availability of funds.

Two types of projects are anticipated:

1. Incubation grants: Standard awards of up to $100K for one or two years to develop collaborations of mathematical scientists, computer scientists, and application experts relevant to the objectives of the CARGO program. It is estimated there will be 5 to 10 incubation grants.

2. Team grants: Continuing awards of up to three years at $200-$300K per year to support teams of investigators. It is estimated there will be 4 to 7 team grants. By July 1, 2003, NSF and DARPA will determine, based on site visits and/or progress reports, and subject to availability of DARPA funds, whether the NSF "Team Grant" awards made will expire at the end of two years, or whether the NSF awards will be extended to three years. Site visits will be conducted by representatives from NSF, DARPA, or both.

V. PROPOSAL PREPARATION AND SUBMISSION INSTRUCTIONS

A. Proposal Preparation Instructions

Full Proposal:

Proposals submitted in response to this program announcement/solicitation should be prepared and submitted in accordance with the general guidelines contained in the NSF Grant Proposal Guide (GPG). The complete text of the GPG is available electronically on the NSF Web Site at: https://www.nsf.gov/cgi-bin/getpub?nsf012. Paper copies of the GPG may be obtained from the NSF Publications Clearinghouse, telephone (301) 947-2722 or by e-mail from pubs@nsf.gov.

Proposers are reminded to identify the program solicitation number (NSF 01-111) in the program announcement/solicitation block on the NSF Form 1207, Cover Sheet For Proposal to the National Science Foundation. Compliance with this requirement is critical to determining the relevant proposal processing guidelines. Failure to submit this information may delay processing.

B. Budgetary Information

Cost sharing is not required in proposals submitted under this Program Solicitation.

C. Deadline/Target Dates

Proposals must be submitted by the following date(s):


Full Proposals by 5:00 PM local time: September 4, 2001

D. FastLane Requirements

Proposers are required to prepare and submit all proposals for this Program Solicitation through the FastLane system. Detailed instructions for proposal preparation and submission via FastLane are available at: http://www.fastlane.nsf.gov/a1/newstan.htm. For FastLane user support, call 1-800-673-6188 or e-mail fastlane@nsf.gov.

Submission of Signed Cover Sheets. The Authorized Organizational Representative (AOR) must electronically sign the proposal Cover Sheet to submit the required proposal certifications (see Chapter II, Section C of the Grant Proposal Guide for a listing of the certifications). The AOR must provide the required certifications within five working days following the electronic submission of the proposal. Further instructions regarding this process are available on the FastLane website at: http://www.fastlane.nsf.gov.

VI. PROPOSAL REVIEW INFORMATION

A. NSF Proposal Review Process

Reviews of proposals submitted to NSF are solicited from peers with expertise in the substantive area of the proposed research or education project. These reviewers are selected by Program Officers charged with the oversight of the review process. NSF invites the proposer to suggest at the time of submission, the names of appropriate or inappropriate reviewers. Care is taken to ensure that reviewers have no conflicts with the proposer. Special efforts are made to recruit reviewers from non-academic institutions, minority-serving institutions, or adjacent disciplines to that principally addressed in the proposal.

Proposals will be reviewed against the following general review criteria established by the National Science Board. Following each criterion are potential considerations that the reviewer may employ in the evaluation. These are suggestions and not all will apply to any given proposal. Each reviewer will be asked to address only those that are relevant to the proposal and for which he/she is qualified to make judgements.

Principal Investigators should address the following elements in their proposal to provide reviewers with the information necessary to respond fully to both of the above-described NSF merit review criteria. NSF staff will give these elements careful consideration in making funding decisions.

A summary rating and accompanying narrative will be completed and signed by each reviewer. In all cases, reviews are treated as confidential documents. Verbatim copies of reviews, excluding the names of the reviewers, are sent to the Principal Investigator/Project Director by the Program Director. In addition, the proposer will receive an explanation of the decision to award or decline funding.

B. Review Protocol and Associated Customer Service Standard

All proposals are carefully reviewed by at least three other persons outside NSF who are experts in the particular field represented by the proposal. Proposals submitted in response to this announcement/solicitation will be reviewed by at least three other persons outsie NSF who are experts in the areas of research represented by the proposal. Proposals will be reviewed by mail and/or panel review, as well as site visits.

Reviewers will be asked to formulate a recommendation to either support or decline each proposal. The Program Officer assigned to manage the proposal's review will consider the advice of reviewers and will formulate a recommendation.

In most cases, proposers will be contacted by the Program Officer after his or her recommendation to award or decline funding has been approved by the Division Director. This informal notification is not a guarantee of an eventual award.

NSF is striving to be able to tell applicants whether their proposals have been declined or recommended for funding within six months for 70 percent of proposals. The time interval begins on the date of receipt. The interval ends when the Division Director accepts the Program Officer's recommendation.

In all cases, after programmatic approval has been obtained, the proposals recommended for funding will be forwarded to the Division of Grants and Agreements for review of business, financial, and policy implications and the processing and issuance of a grant or other agreement. Proposers are cautioned that only a Grants and Agreements Officer may make commitments, obligations or awards on behalf of NSF or authorize the expenditure of funds. No commitment on the part of NSF should be inferred from technical or budgetary discussions with a NSF Program Officer. A Principal Investigator or organization that makes financial or personnel commitments in the absence of a grant or cooperative agreement signed by the NSF Grants and Agreements Officer does so at its own risk.

VII. AWARD ADMINISTRATION INFORMATION

A. Notification of the Award

Notification of the award is made to the submitting organization by a Grants Officer in the Division of Grants and Agreements. Organizations whose proposals are declined will be advised as promptly as possible by the cognizant NSF Program Division administering the program. Verbatim copies of reviews, not including the identity of the reviewer, will be provided automatically to the Principal Investigator. (See section VI.A. for additional information on the review process.)

B. Award Conditions

An NSF award consists of: (1) the award letter, which includes any special provisions applicable to the award and any numbered amendments thereto; (2) the budget, which indicates the amounts, by categories of expense, on which NSF has based its support (or otherwise communicates any specific approvals or disapprovals of proposed expenditures); (3) the proposal referenced in the award letter; (4) the applicable award conditions, such as Grant General Conditions (NSF-GC-1)* or Federal Demonstration Partnership (FDP) Terms and Conditions * and (5) any announcement or other NSF issuance that may be incorporated by reference in the award letter. Cooperative agreement awards also are administered in accordance with NSF Cooperative Agreement Terms and Conditions (CA-1). Electronic mail notification is the preferred way to transmit NSF awards to organizations that have electronic mail capabilities and have requested such notification from the Division of Grants and Agreements.

*These documents may be accessed electronically on NSF's Web site at https://www.nsf.gov/home/grants/grants_gac.htm. Paper copies may be obtained from the NSF Publications Clearinghouse, telephone (301) 947-2722 or by e-mail from pubs@nsf.gov.

More comprehensive information on NSF Award Conditions is contained in the NSF Grant Policy Manual (GPM) Chapter II, available electronically on the NSF Web site at https://www.nsf.gov/cgi-bin/getpub?gpm. The GPM is also for sale through the Superintendent of Documents, Government Printing Office (GPO), Washington, DC 20402. The telephone number at GPO for subscription information is (202) 512-1800. The GPM may be ordered through the GPO Web site at http://www.gpo.gov.

Special Award Conditions
Year 3 of the Team Grants are contingent upon a successful site visit and/or progress report.

C. Reporting Requirements

For all multi-year grants (including both standard and continuing grants), the PI must submit an annual project report to the cognizant Program Officer at least 90 days before the end of the current budget period.

Within 90 days after the expiration of an award, the PI also is required to submit a final project report. Approximately 30 days before expiration, NSF will send a notice to remind the PI of the requirement to file the final project report. Failure to provide final technical reports delays NSF review and processing of pending proposals for that PI. PIs should examine the formats of the required reports in advance to assure availability of required data.

NSF has implemented an electronic project reporting system, available through FastLane. This system permits electronic submission and updating of project reports, including information on project participants (individual and organizational), activities and findings, publications, and other specific products and contributions. PIs will not be required to re-enter information previously provided, either with a proposal or in earlier updates using the electronic system.

VIII. CONTACTS FOR ADDITIONAL INFORMATION

General inquiries regarding  COMPUTATIONAL and ALGORITHMIC REPRESENTATIONS of GEOMETRIC OBJECTS  should be made to:For questions related to the use of FastLane, contact:

IX. OTHER PROGRAMS OF INTEREST

The NSF Guide to Programs is a compilation of funding for research and education in science, mathematics, and engineering. The NSF Guide to Programs is available electronically at https://www.nsf.gov/cgi-bin/getpub?gp. General descriptions of NSF programs, research areas, and eligibility information for proposal submission are provided in each chapter.

Many NSF programs offer announcements or solicitations concerning specific proposal requirements. To obtain additional information about these requirements, contact the appropriate NSF program offices. Any changes in NSF's fiscal year programs occurring after press time for the Guide to Programs will be announced in the NSF E-Bulletin, which is updated daily on the NSF web site at https://www.nsf.gov/home/ebulletin, and in individual program announcements/solicitations. Subscribers can also sign up for NSF's Custom News Service (https://www.nsf.gov/home/cns/start.htm) to be notified of new funding opportunities that become available.

ABOUT THE NATIONAL SCIENCE FOUNDATION

The National Science Foundation (NSF) funds research and education in most fields of science and engineering. Awardees are wholly responsible for conducting their project activities and preparing the results for publication. Thus, the Foundation does not assume responsibility for such findings or their interpretation.

NSF welcomes proposals from all qualified scientists, engineers and educators. The Foundation strongly encourages women, minorities and persons with disabilities to compete fully in its programs. In accordance with Federal statutes, regulations and NSF policies, no person on grounds of race, color, age, sex, national origin or disability shall be excluded from participation in, be denied the benefits of, or be subjected to discrimination under any program or activity receiving financial assistance from NSF (unless otherwise specified in the eligibility requirements for a particular program).

Facilitation Awards for Scientists and Engineers with Disabilities (FASED) provide funding for special assistance or equipment to enable persons with disabilities (investigators and other staff, including student research assistants) to work on NSF-supported projects. See the program announcement/solicitation for further information.

The National Science Foundation has Telephonic Device for the Deaf (TDD) and Federal Information Relay Service (FIRS) capabilities that enable individuals with hearing impairments to communicate with the Foundation about NSF programs, employment or general information. TDD may be accessed at (703) 292-5090, FIRS at 1-800-877-8339.

The National Science Foundation is committed to making all of the information we publish easy to understand. If you have a suggestion about how to improve the clarity of this document or other NSF-published materials, please contact us at plainlanguage@nsf.gov.

PRIVACY ACT AND PUBLIC BURDEN STATEMENTS

The information requested on proposal forms and project reports is solicited under the authority of the National Science Foundation Act of 1950, as amended. The information on proposal forms will be used in connection with the selection of qualified proposals; project reports submitted by awardees will be used for program evaluation and reporting within the Executive Branch and to Congress. The information requested may be disclosed to qualified reviewers and staff assistants as part of the proposal review process; to applicant institutions/grantees to provide or obtain data regarding the proposal review process, award decisions, or the administration of awards; to government contractors, experts, volunteers and researchers and educators as necessary to complete assigned work; to other government agencies needing information as part of the review process or in order to coordinate programs; and to another Federal agency, court or party in a court or Federal administrative proceeding if the government is a party. Information about Principal Investigators may be added to the Reviewer file and used to select potential candidates to serve as peer reviewers or advisory committee members. See Systems of Records, NSF-50, "Principal Investigator/Proposal File and Associated Records," 63 Federal Register 267 (January 5, 1998), and NSF-51, "Reviewer/Proposal File and Associated Records," 63 Federal Register 268 (January 5, 1998). Submission of the information is voluntary. Failure to provide full and complete information, however, may reduce the possibility of receiving an award.

Pursuant to 5 CFR 1320.5(b), an agency may not conduct or sponsor, and a person is not required to respond to an information collection unless it displays a valid OMB control number. The OMB control number for this collection is 3145-0058. Public reporting burden for this collection of information is estimated to average 120 hours per response, including the time for reviewing instructions. Send comments regarding this burden estimate and any other aspect of this collection of information, including suggestions for reducing this burden, to: Suzanne Plimpton, Reports Clearance Officer, Information Dissemination Branch, Division of Administrative Services, National Science Foundation, Arlington, VA 22230, or to Office of Information and Regulatory Affairs of OMB, Attention: Desk Officer for National Science Foundation (3145-0058), 725 17th Street, N.W. Room 10235, Washington, D.C. 20503.


OMB control number: 3145-0058.