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

Bernard Chazelle

doi:10.1007/3-540-15198-2_9

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

Bernard Chazelle

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 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 P₁,…,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²) algorithm for computing the time at which the convex hull of n (algebraically) moving points in E² 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	https://doi.org/10.1007/3-540-15198-2_9
State	Published - 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/Territory	Germany
City	Berlin
Period	3/25/85 → 3/29/85

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-15198-2_9

Cite this

Chazelle, B. (1985). Fast searching in a real algebraic manifold with applications to geometric complexity. In J. Thatcher, H. Ehrig, C. Floyd, & M. Nivat (Eds.), 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

Chazelle, Bernard. / Fast searching in a real algebraic manifold with applications to geometric complexity. 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. editor / James Thatcher ; Hartmut Ehrig ; Christiane Floyd ; Maurice Nivat. Springer Verlag, 1985. pp. 145-156 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{23beeeb176b94f20b3ec7cee74c8da17,

title = "Fast searching in a real algebraic manifold with applications to geometric complexity",

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.",

author = "Bernard Chazelle",

note = "Publisher Copyright: {\textcopyright} 1985, Springer-Verlag.; International Joint Conference on Theory and Practice of Software Development, TAPSOFT 1985 ; Conference date: 25-03-1985 Through 29-03-1985",

year = "1985",

doi = "10.1007/3-540-15198-2_9",

language = "English (US)",

isbn = "9783540151982",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "145--156",

editor = "James Thatcher and Hartmut Ehrig and Christiane Floyd and Maurice Nivat",

booktitle = "Mathematical Foundations of Software Development",

address = "Germany",

}

Chazelle, B 1985, Fast searching in a real algebraic manifold with applications to geometric complexity. in J Thatcher, H Ehrig, C Floyd & M Nivat (eds), 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 185 LNCS, Springer Verlag, pp. 145-156, International Joint Conference on Theory and Practice of Software Development, TAPSOFT 1985, Berlin, Germany, 3/25/85. https://doi.org/10.1007/3-540-15198-2_9

Fast searching in a real algebraic manifold with applications to geometric complexity. / Chazelle, Bernard.
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. ed. / James Thatcher; Hartmut Ehrig; Christiane Floyd; Maurice Nivat. Springer Verlag, 1985. p. 145-156 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 185 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Chazelle, Bernard

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 -

Chazelle B. Fast searching in a real algebraic manifold with applications to geometric complexity. In Thatcher J, Ehrig H, Floyd C, Nivat M, editors, 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. Springer Verlag. 1985. p. 145-156. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-15198-2_9

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

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this