A linear time algorithm for computing the shortest line segment from which a polygon is weakly externally visible

Binary K. Bhattacharya, Asish Mukhopadhyay, Godfried T. Toussaint

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A simple polygon P is said to be weakly externally visible from a line segment if the line segment is outside P and if for every point x on the boundary of P there is a point y on the line segment such that the interior of the line segment xy does not intersect the interior of P. In this paper a linear time algorithm is proposed for computing the shortest line segment from which a simple polygon is weakly externally visible. This is done by a suitable generalization of a linear time algorithm which solves the same problem for a convex polygon.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings
EditorsFrank Dehne, Jorg-Rudiger Sack, Nicola Santoro
PublisherSpringer Verlag
Pages412-424
Number of pages13
ISBN (Print)9783540475668
DOIs
StatePublished - 1991
Event2nd Workshop on Algorithms and Data Structures, WADS 1991 - Ottawa, Canada
Duration: Aug 14 1991Aug 16 1991

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume519 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd Workshop on Algorithms and Data Structures, WADS 1991
CountryCanada
CityOttawa
Period8/14/918/16/91

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A linear time algorithm for computing the shortest line segment from which a polygon is weakly externally visible'. Together they form a unique fingerprint.

  • Cite this

    Bhattacharya, B. K., Mukhopadhyay, A., & Toussaint, G. T. (1991). A linear time algorithm for computing the shortest line segment from which a polygon is weakly externally visible. In F. Dehne, J-R. Sack, & N. Santoro (Eds.), Algorithms and Data Structures - 2nd Workshop, WADS 1991, Proceedings (pp. 412-424). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 519 LNCS). Springer Verlag. https://doi.org/10.1007/BFb0028280