Abstract
We prove the NP-completeness of the following problem. Given a set of slopes and an integer , is it possible to draw a complete graph on vertices in the plane using only slopes from ? Equivalently, does there exist a set of points in general position such that the slope of every segment between two points of is in ? We then present a polynomial algorithm for this question when , conditional on a conjecture of R.E. Jamison. For , an algorithm in was proposed by Wade and Chu. For this case, our algorithm is linear and does not rely on Jamison's conjecture.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.