On the complexity of two circle connecting problems

DOI10.1016/0166-218X(93)90149-IzbMath0801.68081OpenAlexW1975977120WikidataQ128040174 ScholiaQ128040174MaRDI QIDQ1314320

Nen-Fu Huang

Publication date: 29 November 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)90149-i

zbMATH Keywords

approximation algorithmconnectivitycomputational geometryNP-hardnessgeometric location problemdivide- and-conquer

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• An O(N log N) minimal spanning tree algorithm for N points in the plane
• Constrained Delaunay triangulations
• A study on two geometric location problems
• Voronoi diagrams with barriers and the shortest diagonal problem
• Optimal packing and covering in the plane are NP-complete
• On the Complexity of Some Common Geometric Location Problems
• Two algorithms for constructing a Delaunay triangulation
• On the complexity of two circle strongly connecting problems
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of two circle connecting problems