Constrained integer approximation to planar line intersection

DOI10.1016/0020-0190(91)90167-GMaRDI QIDQ1183458zbMATH OpenOpenAlexFDO

Authors Maharaj Mukherjee, George Nagy, Shashank K. Mehta

Publication date 28 June 1992

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(91)90167-g

zbMATH Keywords

continued fractionsinteger grid

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

We consider the following problem: given two intersecting straight lines in \(\mathbb{R}^ 2\) with rational slopes and intercepts, and a quadrant formed by these two lines, find the point with integer-valued coordinates in the given quadrant, which is nearest to the point of intersection of the two lines. We present an algorithm that finds the required point in \(O(\log N)\) time.

Recommendations

• scientific article; zbMATH DE number 3910134
• Approximating a real number by a rational number with a limited denominator: a geometric approach
• Seventeen lines and one-hundred-and-one points
• Seventeen lines and one-hundred-and-one points
• On finite-precision representations of geometric objects

Cited in

(5)

• Efficient algorithms for line and curve segment intersection using restricted predicates
• scientific article; zbMATH DE number 3910134 (Why is no real title available?)
• Seventeen lines and one-hundred-and-one points
• Integer approximation of a segment
• Approximating a real number by a rational number with a limited denominator: a geometric approach

This page was built for publication: Constrained integer approximation to planar line intersection

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