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

triangulationweak visibilitylinear-time algorithmsimple polygonsshortest line segment

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 753969 (Why is no real title available?)
• A linear algorithm for computing the visibility polygon from a point
• A simple algorithm for determining the envelope of a set of lines
• 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 Finding the Kernel of a Polygon
• An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
• An optimal algorithm for detecting weak visibility of a polygon
• COMPUTATIONAL GEOMETRY COLUMN 18
• COMPUTING A SHORTEST WEAKLY EXTERNALLY VISIBLE LINE SEGMENT FOR A SIMPLE POLYGON
• Computing a shortest watchman path in a simple polygon in polynomial-time
• Computing in linear time a chord from which a simple polygon is weakly internally visible
• External visibility
• LR-visibility in polygons
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple 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

(10)

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

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)