### Abstract

We give the first complete subdivision algorithm for the intersection of two Bezier curves F, G, possibly with tangential intersections. Our approach to robust subdivision algorithms is based on geometric separation bounds, and using a criterion for detecting non-crossing intersection of curves. Our algorithm is adaptive, being based only on exact bigfloat computations. In particular, we avoid manipulation of algebraic numbers and resultant computations. It is designed to be competitive with current algorithms on "nice" inputs. All standard algorithms assume F, G to be relatively prime - our algorithm needs a generalization of this.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06 |

Pages | 217-226 |

Number of pages | 10 |

State | Published - 2006 |

Event | 22nd Annual Symposium on Computational Geometry 2006, SCG'06 - Sedona, AZ, United States Duration: Jun 5 2006 → Jun 7 2006 |

### Publication series

Name | Proceedings of the Annual Symposium on Computational Geometry |
---|---|

Volume | 2006 |

### Other

Other | 22nd Annual Symposium on Computational Geometry 2006, SCG'06 |
---|---|

Country | United States |

City | Sedona, AZ |

Period | 6/5/06 → 6/7/06 |

### Keywords

- Bezier curves
- Computational geometry
- Curve intersection
- Exact geometric computation
- Robust numerical algorithms
- Subdivision method

### ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics

## Fingerprint Dive into the research topics of 'Complete subdivision algorithms, I: Intersection of Bezier curves'. Together they form a unique fingerprint.

## Cite this

Yap, C. K. (2006). Complete subdivision algorithms, I: Intersection of Bezier curves. In

*Proceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06*(pp. 217-226). (Proceedings of the Annual Symposium on Computational Geometry; Vol. 2006).