Geometric Algorithms for Linear Programming

Hiroshi IMAI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E76-A   No.3   pp.259-264
Publication Date: 1993/03/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: INVITED PAPER (Special Section on the 5th Karuizawa Workshop on Circuits and Systems)
Category: 
Keyword: 
computational geometry,  linear programming,  prune-and-search,  randomization,  

Full Text: PDF>>
Buy this Article



Summary: 
Two computational-geometric approaches to linear programming are surveyed. One is based on the prune-and-search paradigm and the other utilizes randomization. These two techniques are quite useful to solve geometric problems efficiently, and have many other applications, some of which are also mentioned.