TY - GEN
T1 - Optimal algorithms for some smallest intersection radius problems
AU - Bhattacharya, Binay K.
AU - Jadhav, Sreesh
AU - Mukhopadhayay, Asish
AU - Robert, Jean Marc
N1 - Publisher Copyright:
© 1991 ACM.
PY - 1991/6/1
Y1 - 1991/6/1
N2 - The intersection radius of a set of objects is the radius of the smallest closed disk that intersects all the objects of the set In this paper we have designed optimal algorithms for some intersection radius problems. We first present a linear-time algorithm to determine the smallest intersecting closed disk when the objects to be intersected are hyperplanes in fixed d-dimensional space. This is solved by showing that the intersection radius problem of n hyperplanes in d-dimensional space can be transformed to a linear programming problem in (d+l)-dimensional space involving 2n linear constraints. We then solve the intersection radius problem for line segments in the plane in linear time by showing exactly how a prune-and-search can be carried out in the plane. For this we solved the following subproblems: Subproblem 1: Given a set of n lines and points in the plane compute a smallest radius disk intersecting these objects. Subproblem 2: Given a set of rays in the plane show how these can be converted to a set of points and lines such that the smallest intersecting disk of the transformed lines and points is the same as that of the given set of rays. There exists no known algorithm to solve these intersection radius problems efficiently.
AB - The intersection radius of a set of objects is the radius of the smallest closed disk that intersects all the objects of the set In this paper we have designed optimal algorithms for some intersection radius problems. We first present a linear-time algorithm to determine the smallest intersecting closed disk when the objects to be intersected are hyperplanes in fixed d-dimensional space. This is solved by showing that the intersection radius problem of n hyperplanes in d-dimensional space can be transformed to a linear programming problem in (d+l)-dimensional space involving 2n linear constraints. We then solve the intersection radius problem for line segments in the plane in linear time by showing exactly how a prune-and-search can be carried out in the plane. For this we solved the following subproblems: Subproblem 1: Given a set of n lines and points in the plane compute a smallest radius disk intersecting these objects. Subproblem 2: Given a set of rays in the plane show how these can be converted to a set of points and lines such that the smallest intersecting disk of the transformed lines and points is the same as that of the given set of rays. There exists no known algorithm to solve these intersection radius problems efficiently.
UR - https://www.scopus.com/pages/publications/0346927837
U2 - 10.1145/109648.109657
DO - 10.1145/109648.109657
M3 - Contribution to conference proceedings
AN - SCOPUS:0346927837
SN - 0897914260
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 81
EP - 88
BT - Proceedings of the Annual Symposium on Computational Geometry
PB - Association for Computing Machinery
T2 - 7th Annual Symposium on Computational Geometry, SCG 1991
Y2 - 10 June 1991 through 12 June 1991
ER -