Computing Two-Dimensional Integer Hulls

DOI10.1137/S009753979528977XzbMath1020.52015MaRDI QIDQ4268868

Warwick Harvey

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

continued fractionslinear inequalitiesinteger convex hull

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Continued fractions (11A55) Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05)

Related Items

Intersection cuts for single row corner relaxations ⋮ Mapping multiple regions to the grid with bounded Hausdorff distance ⋮ Algorithms for multiprocessor scheduling with two job lengths and allocation restrictions ⋮ Two-halfspace closure ⋮ Computing efficiently the lattice width in any dimension ⋮ Splitting the Control Flow with Boolean Flags ⋮ An algorithm for the separation of two-row cuts ⋮ The two variable per inequality abstract domain ⋮ Split Cuts in the Plane ⋮ A polynomial algorithm for one problem of guillotine cutting ⋮ Euclidean farthest-point Voronoi diagram of a digital edge ⋮ Fast recognition of a digital straight line subsegment: two algorithms of logarithmic time complexity ⋮ Approximating a real number by a rational number with a limited denominator: a geometric approach ⋮ A note on the computation of the fraction of smallest denominator in between two irreducible fractions ⋮ Efficient Lattice Width Computation in Arbitrary Dimension ⋮ Ranking Functions for Linear-Constraint Loops ⋮ An asymptotically exact algorithm for the high-multiplicity bin packing problem

This page was built for publication: Computing Two-Dimensional Integer Hulls