Hamiltonian triangulations and circumscribing polygons of disjoint line segments

DOI10.1016/0925-7721(92)90018-NzbMATH Open0761.52005MaRDI QIDQ1200910FDOQ1200910

Authors: Andranik Mirzaian 

Publication date: 16 January 1993

Published in: Computational Geometry (Search for Journal in Brave)

Recommendations

• scientific article; zbMATH DE number 866021
• On circumscribing polygons for line segments
• Circumscribing polygons and polygonizations for disjoint line segments
• Topics on line segments and polygons
• Segment endpoint visibility graphs are Hamiltonian

zbMATH Keywords

algorithm\(n\) disjoint line segments in the planecircumscribing polygon

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Paths and cycles (05C38) Convex sets in (2) dimensions (including convex curves) (52A10)

Cites Work

• An efficient algorithm for determining the convex hull of a finite planar set
• Title not available (Why is that?)
• Title not available (Why is that?)
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Triangulating a simple polygon in linear time
• The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
• Geometry Helps in Matching
• A Theorem on Planar Graphs
• Hamiltonian cycles in planar triangulations with no separating triangles
• Computing Simple Circuits from a Set of Line Segments is NP-Complete
• Computing simple circuits from a set of line segments
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• A linear-time algorithm for finding a minimum spanning pseudoforest
• Traveling salesman cycles are not always subgraphs of Voronoi duals
• Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations

Cited In (17)

• Graham triangulations and triangulations with a center are Hamiltonean
• On the visibility graph of convex translates
• On the perfect matching of disjoint compact sets by noncrossing line segments in \(\mathbb R^n\)
• Compatible spanning trees
• Circumscribing polygons and polygonizations for disjoint line segments
• Hamiltonian-connectedness of triangulations with few separating triangles
• Non-Hamiltonian triangulations with distant separating triangles
• Two segment classes with Hamiltonian visibility graphs
• Title not available (Why is that?)
• The visibility graph of congruent discs is Hamiltonian
• On a counterexample to a conjecture of Mirzaian
• Segment endpoint visibility graphs are Hamiltonian
• On an estimate of the size of the maximum matching for a family of disjoint compact convex sets in the plane
• On circumscribing polygons for line segments
• Arc diagrams, flip distances, and Hamiltonian triangulations
• Compatible geometric matchings
• On hamiltonian triangulations in simple polygons (Extended Abstract)

This page was built for publication: Hamiltonian triangulations and circumscribing polygons of disjoint line segments

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