Computing Two-Dimensional Integer Hulls

DOI10.1137/S009753979528977XMaRDI QIDQ4268868zbMATH OpenFDO

Authors Warwick Harvey

Publication date 28 October 1999

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

Full work available at URL https://doi.org/10.1137/S009753979528977X

zbMATH Keywords

continued fractionsinteger convex hulllinear inequalities

Mathematics Subject Classification ID

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

Recommendations

• Computing the integer hull of convex polyhedral sets
• INTEGER analysis of two-dimensional polygonal objects
• scientific article; zbMATH DE number 1182912
• Computing D-convex hulls in the plane
• An efficient and numerically correct algorithm for the 2D convex hull problem
• Computing the convex hull of line intersections
• Using interval arithmetic for determining the structure of convex hulls
• Computing convex hull in a floating point arithmetic
• Computing the integer points of a polyhedron. II: Complexity estimates
• Computing the integer points of a polyhedron

Cited in

(23)

• Intersection cuts for single row corner relaxations
• Computing the integer points of a polyhedron. I: Algorithm
• Note on the complexity of the mixed-integer hull of a polyhedron
• Computing the integer hull of convex polyhedral sets
• How to find the convex hull of all integer points in a polyhedron?
• Euclidean farthest-point Voronoi diagram of a digital edge
• Fast recognition of a digital straight line subsegment: two algorithms of logarithmic time complexity
• An algorithm for the separation of two-row cuts
• A polynomial algorithm for one problem of guillotine cutting
• An asymptotically exact algorithm for the high-multiplicity bin packing problem
• Two-halfspace closure
• Splitting the Control Flow with Boolean Flags
• Efficient lattice width computation in arbitrary dimension
• EFFICIENT ENUMERATION OF GRID POINTS IN A CONVEX POLYGON AND ITS APPLICATION TO INTEGER PROGRAMMING
• Split cuts in the plane
• Point containment in the integer hull of a polyhedron
• Ranking functions for linear-constraint loops
• A note on the computation of the fraction of smallest denominator in between two irreducible fractions
• Computing efficiently the lattice width in any dimension
• The two variable per inequality abstract domain
• Mapping multiple regions to the grid with bounded Hausdorff distance
• Algorithms for multiprocessor scheduling with two job lengths and allocation restrictions
• Approximating a real number by a rational number with a limited denominator: a geometric approach

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

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