Deterministic Algorithms for 2-d Convex Programming and 3-d Online Linear Programming

DOI10.1006/JAGM.1997.0914MaRDI QIDQ4209278zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan

Publication date 24 November 1998

Published in Journal of Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1006/jagm.1997.0914

zbMATH Keywords

linear objective functiontwo-dimensional convex programs

Mathematics Subject Classification ID

Convex programming (90C25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Abstract computational complexity for mathematical programming problems (90C60) Parallel algorithms in computer science (68W10)

Recommendations

• Small-dimensional linear programming and convex hulls made easy
• Dynamic Three-Dimensional Linear Programming
• Linear Time Algorithms for Two- and Three-Variable Linear Programs

Cited in

(7)

• Efficient algorithms and implementations for optimizing the sum of linear fractional functions, with applications
• Approximating points by a piecewise linear function
• A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions
• Rearranging a sequence of points onto a line
• Intersecting disks using two congruent disks
• An optimal online algorithm for halfplane intersection
• Deterministic algorithms for unique sink orientations of grids

This page was built for publication: Deterministic Algorithms for 2-d Convex Programming and 3-d Online Linear Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4209278)