Passer à la navigation principale Passer à la recherche Passer au contenu principal

Optimal algorithms for some smallest intersection radius problems

  • Simon Fraser University
  • Indian Institute of Technology Kanpur
  • McGill University

Résultats de recherche: Chapitre dans un livre, rapport, actes de conférence › Participation à un ouvrage collectif lié à un colloque ou une conférence › Revue par des pairs

3 Citations (Scopus)

Résumé

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.

langue originaleAnglais
titreProceedings of the Annual Symposium on Computational Geometry
EditeurAssociation for Computing Machinery
Pages81-88
Nombre de pages8
ISBN (imprimé)0897914260
Les DOIs
étatPublié - 1 juin 1991
Modification externeOui
Evénement7th Annual Symposium on Computational Geometry, SCG 1991 - North Conway, Etats-Unis
Durée: 10 juin 1991 → 12 juin 1991

Série de publications

NomProceedings of the Annual Symposium on Computational Geometry

Conférence

Conférence7th Annual Symposium on Computational Geometry, SCG 1991
Pays/TerritoireEtats-Unis
La villeNorth Conway
Période10/06/91 → 12/06/91

Classification disciplinaire ASJC Scopus

  • Informatique théorique
  • Géométrie et topologie
  • Mathématiques informatiques

Empreinte digitale

Voici les principaux termes ou expressions associés à « Optimal algorithms for some smallest intersection radius problems ». Ces libellés thématiques sont générés à partir du titre et du résumé de la publication. Ensemble, ils forment une empreinte digitale unique.

Citer cette ressource