Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

• People
  • Personnel
  • Guests
  • Alumni
• Reports
  • Current Report
  • Report for 2023
  • Report for 2022
  • Previous Reports
• Research
  • Grants
  • Dissertations
  • Master/Bachelor Theses
  • Current Publications
  • Previous Publications
• Mittagsseminar
• Courses
• Thesis Topics
• Events
  • Workshops
    • Current
    • Previous
  • Social
    • SOLA
    • GREBGE
• 

Towards The Peak - Problem Section

The Fibonacci-Seesaw Also Works

presented by Emo Welzl

The Fibonacci-Seesaw algorithm for finding the sink in a unique sink orientation too can be adapted such that it ether finds a sink or a certificate.

Let $\phi$ be an orientation of the d-dimensional cube $\cal C$. Choose two antipodal 0-dimensional subcubes ${\cal C}_a^{(0)}$ and ${\cal C}_b^{(0)}$, i.e. two antipodal vertices v_a⁽⁰⁾ and v_b⁽⁰⁾. For both ${\cal C}_a^{(0)}$ and ${\cal C}_b^{(0)}$ we know the sink. The idea is to inductively grow both antipodal subcubes until we get the whole cube.

Suppose we have two antipodal subcubes ${\cal C}_a^{(k)}$ and ${\cal C}_b^{(k)}$ with sinks v_a^(k) and v_b^(k). Either the outmaps of v_a^(k) and v_b^(k) are the same with respect to $\phi$ and we have found a certificate that $\phi$ has not the unique sink property, or there is a direction i for which one of the edge in v_a^(k) and v_b^(k) is ingoing and the other is outgoing. We get ${\cal C}_a^{(k+1)}$ and ${\cal C}_b^{(k+1)}$ by adding the direction i. For one of the new subcubes, say ${\cal C}_a^{(k+1)}$, the vertex v_a^(k+1)=v_a^(k) stays a sink. For the other subcube ${\cal C}_b^{(k+1)}$ we have to search for a new sink. We will do this in the facet of ${\cal C}_b^{(k+1)}$ opposite to ${\cal C}_b^{(k)}$. This search will take D(k) steps. Either we find a certificate in this small subcube and are done or we find a sink v. If vis not a sink in ${\cal C}_b^{(k+1)}$ together with v_b^(k) we have a certificate. Otherwise v_b^(k+1)=v and we can go on.

Imprint Disclaimer Copyright