Constrained integer approximation to planar line intersection (Q1183458)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Constrained integer approximation to planar line intersection |
scientific article; zbMATH DE number 33304
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Constrained integer approximation to planar line intersection |
scientific article; zbMATH DE number 33304 |
Statements
Constrained integer approximation to planar line intersection (English)
0 references
28 June 1992
0 references
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.
0 references
integer grid
0 references
continued fractions
0 references
