Computing Roadmaps of General Semi-Algebraic Sets | Zendy

John Canny | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Computing Roadmaps of General Semi-Algebraic Sets

Author(s) -

John Canny

Publication year - 1993

Publication title -

the computer journal

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.319

H-Index - 64

eISSN - 1460-2067

pISSN - 0010-4620

DOI - 10.1093/comjnl/36.5.504

Subject(s) - algebraic extension , algebraic number , extension (predicate logic) , embedding , field (mathematics) , set (abstract data type) , path (computing) , basis (linear algebra) , mathematics , algebraic operation , computer science , algebra over a field , discrete mathematics , algorithm , pure mathematics , artificial intelligence , geometry , mathematical analysis , differential algebraic equation , ordinary differential equation , programming language , differential equation

In this paper we study the problem of determining whether two points lie in the same connected component of a semi-algebraic set S. Although we are mostly concerned with sets S⊆R k , our algorithm can also decide if points in an arbitrary set S⊆R k can be joined by a semi-algebraic path, for any real closed field R. Our algorithm computer a one-dimensional semi-algebraic subset R(S) of S (actually of an embedding of S in a space R k for a certain real extension field R of the given field R). R(S) is called the roadmap of S. The basis of this work is the eoadmap algorithm described in [3, 4] which worked only for compact, regularly stratified sets

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research