Skip to main navigation Skip to search Skip to main content

Optimal algorithms for some smallest intersection radius problems

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

Research output: Contribution to Book/Report types › Contribution to conference proceedings › peer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the Annual Symposium on Computational Geometry
PublisherAssociation for Computing Machinery
Pages81-88
Number of pages8
ISBN (Print)0897914260
DOIs
Publication statusPublished - 1 Jun 1991
Externally publishedYes
Event7th Annual Symposium on Computational Geometry, SCG 1991 - North Conway, United States
Duration: 10 Jun 1991 → 12 Jun 1991

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Conference

Conference7th Annual Symposium on Computational Geometry, SCG 1991
Country/TerritoryUnited States
CityNorth Conway
Period10/06/91 → 12/06/91

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Optimal algorithms for some smallest intersection radius problems'. These topics are generated from the title and abstract of the publication. Together, they form a unique fingerprint.

Cite this