Fast searching in a real algebraic manifold with applications to geometric complexity

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

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 P1,…,Pn be n rational r-variate polynomials of degree ≤d. Our main result is an O(n2r + 6) data structure for computing the predicate [∃i (1≤i≤n)|Pi(x)=0] in O(log n) time, for any x∈Er. 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(n2) algorithm for computing the time at which the convex hull of n (algebraically) moving points in E2 reaches a steady state.

Original languageEnglish (US)
Title of host publicationMathematical Foundations of Software Development
Subtitle of host publicationProceedings of the International Joint Conference on Theory and Practice of Software Development, TAPSOFT - Colloquium on Trees in Algebra and Programming CAAP 1985
EditorsJames Thatcher, Hartmut Ehrig, Christiane Floyd, Maurice Nivat
PublisherSpringer Verlag
Pages145-156
Number of pages12
ISBN (Print)9783540151982
DOIs
StatePublished - Jan 1 1985
Externally publishedYes
EventInternational Joint Conference on Theory and Practice of Software Development, TAPSOFT 1985 - Berlin, Germany
Duration: Mar 25 1985Mar 29 1985

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume185 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherInternational Joint Conference on Theory and Practice of Software Development, TAPSOFT 1985
CountryGermany
CityBerlin
Period3/25/853/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