Solving related two- and three-dimensional linear programming problems in logarithmic time (Q1091934): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
| (7 intermediate revisions by 6 users not shown) | |||
| Property / author | |||
| Property / author: Leonidas J. Guibas / rank | |||
| Property / author | |||
| Property / author: Leonidas J. Guibas / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0304-3975(87)90101-0 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2043237616 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Optimal Point Location in a Monotone Subdivision / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Optimal Search in Planar Subdivisions / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Finding the intersection of n half-spaces in time O(n log n) / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3992847 / rank | |||
Normal rank | |||
| links / mardi / name | links / mardi / name | ||
Latest revision as of 10:50, 18 June 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Solving related two- and three-dimensional linear programming problems in logarithmic time |
scientific article |
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
