A Constructive Proof of Tucker's Combinatorial Lemma.

Abstract

Tucker's combinatorial lemma is concerned with certain labelings of the vertices of a triangulation of the n-ball. It can be used as a basis for the proof of antipodal-point theorems in the same way that Sperner's lemma yields Brouwer's theorem. Here we give a constructive proof, which thereby yields algorithms for antipodal-point problems. The method used is based on an algorithm of Reiser. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1980
Accession Number
ADA090797

Entities

People

  • Michael J. Todd
  • Robert M. Freund

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Buildings And Structures
  • California
  • Contracts
  • Governments
  • Military Research
  • Numbers
  • Operations Research
  • Optimization
  • Point Theorem
  • Real Numbers
  • Triangulation
  • United States
  • United States Government
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.