On the complexity of two circle connecting problems

DOI10.1016/0166-218X(93)90149-IMaRDI QIDQ1314320zbMATH OpenOpenAlexWikidataFDO

Authors 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 algorithmcomputational geometryconnectivityNP-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)

Recommendations

• scientific article; zbMATH DE number 1286344
• Barrier coverage problem in 2D
• On the Complexity of Some Common Geometric Location Problems

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A study on two geometric location problems
• An O(N log N) minimal spanning tree algorithm for N points in the plane
• Constrained Delaunay triangulations
• On the Complexity of Some Common Geometric Location Problems
• On the complexity of two circle strongly connecting problems
• Optimal packing and covering in the plane are NP-complete
• Two algorithms for constructing a Delaunay triangulation
• Voronoi diagrams with barriers and the shortest diagonal problem

Cited in

(3)

• Complexity of the repeaters allocating problem
• Graham's problem on shortest networks for points on a circle
• Computational complexity for the problem of optimal intersection of straight line segments by disks

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

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