Optimally computing a shortest weakly visible line segment inside a simple polygon

DOI10.1016/S0925-7721(01)00058-XMaRDI QIDQ1614066zbMATH OpenOpenAlexFDO

Authors Giri Narasimhan, Binay Bhattacharya, Gautam K. Das, Asish Mukhopadhyay

Publication date 3 September 2002

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0925-7721(01)00058-x

zbMATH Keywords

linear-time algorithmshortest line segmentsimple polygonstriangulationweak visibility

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

The authors present a linear-time algorithm (which is optimal) for the following problem: Given a simple polygon, either compute a shortest line segment such that every point on the boundary of the polygon is visible from some point on the line segment (weakly internal visible), or report that such a segment does not exist. This algorithm is a significant improvement over another linear-time algorithm presented by some of the authors [\textit{G. Das} and \textit{G. Narasinhan}, Proc. 10th Annual ACM Symp. on Computational Geometry, 259-268 (1994)] since the new algorithm does not use some tools used in the previous one (as Chazelle's linear-time triangulation algorithm) that made the first algorithm impractical.

Recommendations

• COMPUTING A SHORTEST WEAKLY EXTERNALLY VISIBLE LINE SEGMENT FOR A SIMPLE POLYGON
• scientific article; zbMATH DE number 177566
• Finding all weakly-visible chords of a polygon in linear time
• Computing in linear time a chord from which a simple polygon is weakly internally visible
• Optimally Computing the Shortest Weakly Visible Subedge of a Simple Polygon

Cites work

• A linear algorithm for computing the visibility polygon from a point
• A simple algorithm for determining the envelope of a set of lines
• An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
• An Algorithm for Determining Visibility of a Simple Polygon from an Internal Line Segment
• An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT
• An optimal algorithm for detecting weak visibility of a polygon
• An Optimal Algorithm for Finding the Kernel of a Polygon
• COMPUTATIONAL GEOMETRY COLUMN 18
• Computing a shortest watchman path in a simple polygon in polynomial-time
• COMPUTING A SHORTEST WEAKLY EXTERNALLY VISIBLE LINE SEGMENT FOR A SIMPLE POLYGON
• Computing in linear time a chord from which a simple polygon is weakly internally visible
• External visibility
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 753969 (Why is no real title available?)
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• LR-visibility in polygons
• Minimal Sets of Visibility
• Optimally Computing the Shortest Weakly Visible Subedge of a Simple Polygon
• Shortest watchman routes in simple polygons
• THE TWO GUARDS PROBLEM
• Triangulating a simple polygon in linear time
• Two-Guard Walkability of Simple Polygons
• Watchman routes under limited visibility

Cited in

(11)

• Rotationally monotone polygons
• scientific article; zbMATH DE number 123833 (Why is no real title available?)
• An Algorithm for Determining Visibility of a Simple Polygon from an Internal Line Segment
• scientific article; zbMATH DE number 177566 (Why is no real title available?)
• COMPUTING A SHORTEST WEAKLY EXTERNALLY VISIBLE LINE SEGMENT FOR A SIMPLE POLYGON
• scientific article; zbMATH DE number 753969 (Why is no real title available?)
• Optimally Computing the Shortest Weakly Visible Subedge of a Simple Polygon
• Open guard edges and edge guards in simple polygons
• An optimal algorithm for computing visible nearest foreign neighbors among colored line segments
• Finding all weakly-visible chords of a polygon in linear time
• Computing in linear time a chord from which a simple polygon is weakly internally visible

This page was built for publication: Optimally computing a shortest weakly visible line segment inside a simple polygon

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1614066)