TY - GEN

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

AU - Chazelle, Bernard

N1 - Funding Information:
This research was supported in part by NSF grants MCS 83-03925 and the Office of Naval
Funding Information:
This research was supported in part by NSF grants MCS 83-03925 and the Office of Naval Research and the Defense Advanced Research Projects Agency under contract N00014-83-K-0146 and ARPA Order No. 4786.
Funding Information:
Research and the Defense Advanced Research Projects Agency under contract N00014-83-K-0146

PY - 1985

Y1 - 1985

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85032035455&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85032035455&partnerID=8YFLogxK

U2 - 10.1007/3-540-15198-2_9

DO - 10.1007/3-540-15198-2_9

M3 - Conference contribution

AN - SCOPUS:85032035455

SN - 9783540151982

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

SP - 145

EP - 156

BT - Mathematical Foundations of Software Development

A2 - Thatcher, James

A2 - Ehrig, Hartmut

A2 - Floyd, Christiane

A2 - Nivat, Maurice

PB - Springer Verlag

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

Y2 - 25 March 1985 through 29 March 1985

ER -