### Abstract

This paper generalizes the multidimensional searching scheme of Dobkin and Lipton [SIAM J. Comput. 5(2), pp. 181–186, 1976] for the case of arbitrary (as opposed to linear) real algebraic varieties. Let d,r be two positive constants and let P_{1},…,P_{n} be n rational r-variate polynomials of degree ≤d. Our main result is an O(n^{2r + 6}) data structure for computing the predicate [∃i (1≤i≤n)|P_{i}(x)=0] in O(log n) time, for any x∈E^{r}. The method is intimately based on a decomposition technique due to Collins [Proc. 2nd GI Conf. on Automata Theory and Formal Languages, pp. 134–183, 1975]. The algorithm can be used to solve problems in computational geometry via a locus approach. We illustrate this point by deriving an o(n^{2}) algorithm for computing the time at which the convex hull of n (algebraically) moving points in E^{2} reaches a steady state.

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

Title of host publication | Mathematical Foundations of Software Development |

Subtitle of host publication | Proceedings of the International Joint Conference on Theory and Practice of Software Development, TAPSOFT - Colloquium on Trees in Algebra and Programming CAAP 1985 |

Editors | James Thatcher, Hartmut Ehrig, Christiane Floyd, Maurice Nivat |

Publisher | Springer Verlag |

Pages | 145-156 |

Number of pages | 12 |

ISBN (Print) | 9783540151982 |

DOIs | |

State | Published - Jan 1 1985 |

Externally published | Yes |

Event | International Joint Conference on Theory and Practice of Software Development, TAPSOFT 1985 - Berlin, Germany Duration: Mar 25 1985 → Mar 29 1985 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 185 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | International Joint Conference on Theory and Practice of Software Development, TAPSOFT 1985 |
---|---|

Country | Germany |

City | Berlin |

Period | 3/25/85 → 3/29/85 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Fast searching in a real algebraic manifold with applications to geometric complexity'. Together they form a unique fingerprint.

## Cite this

*Mathematical Foundations of Software Development: Proceedings of the International Joint Conference on Theory and Practice of Software Development, TAPSOFT - Colloquium on Trees in Algebra and Programming CAAP 1985*(pp. 145-156). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 185 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-15198-2_9