proximity problems

{{Use American English|date = February 2019}}

{{Short description|Distance estimation problems in computational geometry}}

{{Use mdy dates|date = February 2019}}

Proximity problems is a class of problems in computational geometry which involve estimation of distances between geometric objects.

A subset of these problems stated in terms of points only are sometimes referred to as closest point problems,{{cite book|author = J. R. Sack and J. Urrutia (eds.) | year = 2000 | title = Handbook of Computational Geometry | publisher = North Holland | isbn = 0-444-82537-1}} although the term "closest point problem" is also used synonymously to the nearest neighbor search.

A common trait for many of these problems is the possibility to establish the Θ(n log n) lower bound on their computational complexity by reduction from the element uniqueness problem basing on an observation that if there is an efficient algorithm to compute some kind of minimal distance for a set of objects, it is trivial to check whether this distance equals to 0.

Atomic problems

While these problems pose no computational complexity challenge, some of them are notable because of their ubiquity in computer applications of geometry.

  • Distance between a pair of line segments. It cannot be expressed by a single formula, unlike, e.g., the distance from a point to a line. Its calculation requires careful enumeration of possible configurations, especially in 3D and higher dimensions.{{cite journal

|author = V. J. Lumelsky

|title = On fast computation of distance between line segments

|journal = Inf. Process. Lett.

|volume = 21

|year = 1985

|issue = 2

|pages = 55–61

|doi = 10.1016/0020-0190(85)90032-8

}}

Problems on points

Other

References

  • {{cite book | author = Franco P. Preparata and Michael Ian Shamos | title = Computational Geometry - An Introduction | publisher = Springer-Verlag | year = 1985 | id = 1st edition: {{ISBN|0-387-96131-3}}; 2nd printing, corrected and expanded, 1988: {{ISBN|3-540-96131-3}}; Russian translation, 1989: {{ISBN|5-03-001041-6}} | isbn = 0-387-96131-3 | url-access = registration | url = https://archive.org/details/computationalgeo0000prep }} The proximity problems are covered in chapters 6 and 7.

Category:Geometric algorithms