Subdivision Algorithm for Computing the Minimum Distance Between Two Algebraic Curves

Authors

Jiadai Qi, College of Science, Zhejiang University of Technology, Hangzhou 310023, China;
Huahao Shou, College of Science, Zhejiang University of Technology, Hangzhou 310023, China;

Abstract

Abstract: Since it is difficult to compute the minimum distance between two algebraic curves by traditional methods when the expressions of the algebraic curves are complicated, a subdivision algorithm is proposed. Quadtree data structure was used to subdivide the two algebraic curves into two sets of pixels. Interval arithmetic was used to compute the minimum distance interval between these two sets of pixels. The center of this interval is the approximation of the minimum distance between the two algebraic curves. The error is less than a half of this interval. Compared with traditional methods, this method can obtain the approximation of the minimum distance between two algebraic curves at any precision, as well as the error estimation at the same time.

Recommended Citation

Qi, Jiadai and Shou, Huahao (2020) "Subdivision Algorithm for Computing the Minimum Distance Between Two Algebraic Curves," Journal of System Simulation: Vol. 28: Iss. 10, Article 27.
Available at: https://dc-china-simulation.researchcommons.org/journal/vol28/iss10/27

First Page

2485

Revised Date

2016-07-11

DOI Link

https://doi.org/

Last Page

2490

CLC

TP391.7

Recommended Citation

Qi Jiadai, Shou Huahao. Subdivision Algorithm for Computing the Minimum Distance Between Two Algebraic Curves[J]. Journal of System Simulation, 2016, 28(10): 2485-2490.