𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Timothy M Chan

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
228 KB
Volume
27
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

We present a deterministic algorithm for solving two-dimensional convex pro-Ε½ . grams with a linear objective function. The algorithm requires O k log k primitive operations for k constraints; if a feasible point is given, the bound reduces to Ε½ . O k log krlog log k . As a consequence, we can decide whether k convex n-gons Ε½ Γ„ 4 . in the plane have a common intersection in O k log n min log k, log log n worstcase time. Furthermore, we can solve the three-dimensional online programming Ε½ 3 . problem in o log n worst-case time per operation.

πŸ“œ SIMILAR VOLUMES

Stochastic linear programs with simple r
Stochastic linear programs with simple recourse: The equivalent deterministic convex program for the normal, exponential, and erlang cases
✍ Behram J. Hansotia πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 579 KB

We consider here stochastic linear programs with simple recourse when all the elements of the technology matrix and the resource vector have certain specific distributions. The distributions considered are the Normal, Exponential and Erlang. For the first two instances we extend the equivalent deter

UNSTRUCTURED GRID GENERATION AND A SIMPL
UNSTRUCTURED GRID GENERATION AND A SIMPLE TRIANGULATION ALGORITHM FOR ARBITRARY 2-D GEOMETRIES USING OBJECT ORIENTED PROGRAMMING
✍ B. K. KARAMETE; T. TOKDEMΔ°R; M. GER πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 413 KB πŸ‘ 3 views

This paper describes the logic of a dynamic algorithm for a general 2D Delaunay triangulation of arbitrarily prescribed interior and boundary nodes. The complexity of the geometry is completely arbitrary. The scheme is free of specific restrictions on the input of the geometrical data. The scheme ge

A Fast and Robust Algorithm for 2D/3D Pa
A Fast and Robust Algorithm for 2D/3D Panorama Ultrasound Data
✍ Otmar Scherzer; Armin Schoisswohl πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 873 KB

T his paper presents a fast and robust algorithm for generating compound panorama images from partially (spatially) overlapping data sets. This method results in optimizing a nonlinear functional. We propose a multiscale approach for the solution of the optimization problem that is based on a multir