On the topology of algorithms. I (Q1099953)

From MaRDI portal
Revision as of 15:30, 18 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
On the topology of algorithms. I
scientific article

    Statements

    On the topology of algorithms. I (English)
    0 references
    1987
    0 references
    The author considers the following problem: Poly(d): Given a complex polynomial f of degree d and with leading coefficient 1, find all the roots of f within \(\epsilon >0\). He defines the topological complexity of a problem as the minimum of the numbers of branching nodes of the computation trees describing the algorithms which solve that problem. The following result is derived in this paper: There exists in each dimension d an \(\epsilon (d)>0\) such that for all \(\epsilon <\epsilon (d)\) the topological complexity of the problem Poly(d) is greater than \((\log_ 2 d)^{2/3}.\) The proof uses techniques of algebraic topology. As a first step, it is shown that the topological complexity of Poly(d) is greater or equal the covering number of \(\pi\) : \({\mathbb{C}}^ d-\Delta \to {\mathcal P}_ d- \Sigma\), where \({\mathcal P}_ d\) is the space of all complex polynomials of degree d with leading coefficient fractional cascading, a new searching technique which has been described in a companion paper (see the preceding review). The applications center around a variety of geometric query problems. Examples include intersecting a polygonal path with a line, slanted range search, orthogonal range search, computing locus functions, and others. Some results on the optimality of fractional cascading, and certain extensions of the technique for retrieving additional information are also included.
    0 references
    cohomology ring of braid group
    0 references
    topological complexity
    0 references
    branching nodes
    0 references
    computation trees
    0 references
    algorithms
    0 references
    covering number
    0 references
    fractional cascading
    0 references
    range search
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references