| EPSRC Reference: |
EP/C01037X/1 |
| Title: |
Computing with arbitrary precision curves |
| Principal Investigator: |
Dr M Konecny |
| Other Investigators: |
|
| Researcher Co-investigators: |
|
| Project Partners: |
|
| Department: |
Sch of Engineering and Applied Science |
| Organisation: |
Aston University |
| Scheme: |
First Grant Scheme |
| Starts: |
01 March 2006 |
Ends: |
31 May 2009 |
Value (£): |
121,495
|
| EPSRC Research Topic Classifications: |
| Information and communication technologies: Fundamentals of Computing |
Mathematical sciences: Logic and Combinatorics |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary |
This project aims to contribute to the theory of computation with smooth objects such as curves or
geometric shapes. Such computation is important to many areas of science and engineering. We will
concentrate on applications in the area of Newton's mechanics and, more specifically, paths of
objects moving in space.
Curves are often approximated in a computer by many small straight segments and their end-points are
given with a fixed precision. In such an approach, there is much scope for errors due to the
difference between the real curve and the segmented approximation. This project contributes to a
different approach to computation with smooth objects. Here, a computation needs to be able to
deliver its results with no positioning errors and to any required precision.
Other researchers have established ways in which curves and geometric shapes can be represented by a
never-ending sequence of more and more precise simpler approximations. This resembles the way in
which a real number can be represented by a never-ending sequence of digits. Such representations
allow the geometric objects to be communicated from one part of the program to another as an
infinite stream of symbols. Let us call this method of error-free communicating `one-way'.
Complicated objects can be also communicated `two-way': the receiving party asks for approximations
of a specific shape and precision. For example, it can ask for an approximation of the projected
path of a given planet on 5th April 2005 which will be at most 1 nanometre wrong at any time during
that day.
This project aims to examine the following hypothesis:
It is more efficient to manipulate complicated objects like curves using two-way communication
than using one-way communication.
For example, when communicating some curve, the recipient may need to find out more about one part
of the curve than the other parts. If the recipient lets the sender know which part of the curve
they need to know and to what precision, the communication should take less time and effort for both
parties. It remains to be established how big a difference it does make in practice and how much
more will such advanced communication cost both parties.
This project will, therefore, precisely describe several methods for solving practical problems
related to curves. Some of them will allow two-way communication of curves to various degrees. In
the end, these methods will be compared to each other in terms of how much time and computer memory
is required to follow them.
It is expected that the new methods of computing with curves developed here will be
a) less prone to errors than methods with fixed precision and
b) more efficient than similar methods with one-way communication.
|
| Final Report Summary |
This project aims to contribute to the theory of computation with smooth objects such as curves or
geometric shapes. Such computation is important to many areas of science and engineering. We will
concentrate on applications in the area of Newton's mechanics and, more specifically, paths of
objects moving in space.
Curves are often approximated in a computer by many small straight segments and their end-points are
given with a fixed precision. In such an approach, there is much scope for errors due to the
difference between the real curve and the segmented approximation. This project contributes to a
different approach to computation with smooth objects. Here, a computation needs to be able to
deliver its results with no positioning errors and to any required precision.
Other researchers have established ways in which curves and geometric shapes can be represented by a
never-ending sequence of more and more precise simpler approximations. This resembles the way in
which a real number can be represented by a never-ending sequence of digits. Such representations
allow the geometric objects to be communicated from one part of the program to another as an
infinite stream of symbols. Let us call this method of error-free communicating `one-way'.
Complicated objects can be also communicated `two-way': the receiving party asks for approximations
of a specific shape and precision. For example, it can ask for an approximation of the projected
path of a given planet on 5th April 2005 which will be at most 1 nanometre wrong at any time during
that day.
This project aims to examine the following hypothesis:
It is more efficient to manipulate complicated objects like curves using two-way communication
than using one-way communication.
For example, when communicating some curve, the recipient may need to find out more about one part
of the curve than the other parts. If the recipient lets the sender know which part of the curve
they need to know and to what precision, the communication should take less time and effort for both
parties. It remains to be established how big a difference it does make in practice and how much
more will such advanced communication cost both parties.
This project will, therefore, precisely describe several methods for solving practical problems
related to curves. Some of them will allow two-way communication of curves to various degrees. In
the end, these methods will be compared to each other in terms of how much time and computer memory
is required to follow them.
It is expected that the new methods of computing with curves developed here will be
a) less prone to errors than methods with fixed precision and
b) more efficient than similar methods with one-way communication.
|
| Further Information: |
|
| Organisation Website: |
http://www.aston.ac.uk |