Hamiltonian triangulations and circumscribing polygons of disjoint line segments
type: Item
instance of: scholarly article
title: Hamiltonian triangulations and circumscribing polygons of disjoint line segments
zbMATH Open document ID: 0761.52005
DOI: 10.1016/0925-7721(92)90018-N
author: Andranik Mirzaian
published in: Computational Geometry
publication date: 1993-01-16T00:00:00Z
review text: Let a set of \(n\) disjoint line segments in the plane be given. If all segments have at least one end point on the boundary of the convex hull of the segments, then it is shown that there is a circumscribing polygon \(P\), i.e. a simple polygon having all endpoints as its vertices such that each segment is an edge or an interval diagonal of \(P\). There is an algorithm that gives this polygon in \(0(n\log n)\) time. The conjecture that \(P\) exists without the convex hull assumption is disproved in the paper reviewed below.
Mathematics Subject Classification ID: 52A10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 95896
zbMATH Keywords: \(n\) disjoint line segments in the plane
zbMATH Keywords: circumscribing polygon
zbMATH Keywords: algorithm
reviewed by: Erhard Heil
MaRDI profile type: Publication
cites work: A linear-time algorithm for computing the Voronoi diagram of a convex polygon
cites work: A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
cites work: Triangulating a simple polygon in linear time
cites work: The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
cites work: Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations
cites work: Hamiltonian cycles in planar triangulations with no separating triangles
cites work: Q3772828
cites work: A linear-time algorithm for finding a minimum spanning pseudoforest
cites work: An efficient algorithm for determining the convex hull of a finite planar set
cites work: Traveling salesman cycles are not always subgraphs of Voronoi duals
cites work: Q3992847
cites work: Computing Simple Circuits from a Set of Line Segments is NP-Complete
cites work: Computing simple circuits from a set of line segments
cites work: A Theorem on Planar Graphs
cites work: Geometry Helps in Matching
description: scientific article; zbMATH DE number 95896