Solving related two- and three-dimensional linear programming problems in logarithmic time (Q1091934)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Solving related two- and three-dimensional linear programming problems in logarithmic time |
scientific article; zbMATH DE number 4012310
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Solving related two- and three-dimensional linear programming problems in logarithmic time |
scientific article; zbMATH DE number 4012310 |
Statements
Solving related two- and three-dimensional linear programming problems in logarithmic time (English)
0 references
1987
0 references
Given n linear inequalities in three variables, we show how to construct a corresponding spherical subdivision using great circle arcs in time O(n log n) and space O(n). This subdivision in turn allows us to compute the point in space satisfying all inequalities and maximizing any desired linear objective function in time O(log n).
0 references
linear inequalities
0 references
spherical subdivision
0 references
0 references
0.89154756
0 references
0.8849338
0 references
0.88329226
0 references
0.8821801
0 references
0.8816655
0 references
0.8816655
0 references
0.87841094
0 references
