Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I think you might find papers on unit disk graphs informative but discouraging. For instance, <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.3113&amp;rep=rep1&amp;type=pdf" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.3113&amp;rep=rep1&amp;type=pdf</a> states that the maximum independent set problem on unit disk graphs in NP-complete, even if the disk representation is known. A unit disk graph is the graph you get by placing points in the plane and forming links between every pair of points at most a unit distance apart. </p> <p>So I think that if you could solve your problem in polynomial time you could run it on a unit disk graph for different values of K until you find a value at which the smallest distance between two chosen points was just over one, and I think this would be a maximum independent set on the unit disk graph, which would be solving an NP-complete problem in polynomial time.</p> <p>(Just about to jump on a bicycle so this is a bit rushed, but searching for papers on unit disk graphs might at least turn up some useful search terms)</p> <p>Here's an attempt to explain it piece by piece:</p> <p>Here is another attempt to relate the two problems.</p> <p>For maximum independent set see <a href="http://en.wikipedia.org/wiki/Maximum_independent_set#Finding_maximum_independent_sets" rel="nofollow">http://en.wikipedia.org/wiki/Maximum_independent_set#Finding_maximum_independent_sets</a>. A decision problem version of this is "Are there K vertices in this graph such that no two are joined by an edge?" If you can solve this you can certainly find a maximum independent set by finding the largest K by asking this question for different K and then finding the K nodes by asking the question on versions of the graph with one or more nodes deleted.</p> <p>I state without proof that finding the maximum independent set in a unit disk graph is NP-complete. Another reference for this is <a href="http://web.sau.edu/lilliskevinm/wirelessbib/ClarkColbournJohnson.pdf" rel="nofollow">http://web.sau.edu/lilliskevinm/wirelessbib/ClarkColbournJohnson.pdf</a>.</p> <p>A decision version of your problem is "Do there exist K points with distance at least D between any two points?" Again, you can solve this in polynomial time iff you can solve your original problem in polynomial time - play around until you find the largest D that gives answer yes, and then delete points and see what happens.</p> <p>A unit disk graph has an edge exactly when the distance between two points is 1 or less. So if you could solve the decision version of your original problem you could solve the decision version of the unit disk graph problem just by setting D = 1 and solving your problem.</p> <p>So I think I have constructed a series of links showing that if you could solve your problem you could solve an NP-complete problem by turning it into your problem, which causes me to think that your problem is hard.</p>
    singulars
    1. This table or related slice is empty.
    1. POBest subsample in the Maxmin distance sense
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USmcdowella
    1. USmcdowella
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThat's a quite interesting approach, indeed a bit discouraging. If find it mentally difficult to check if your argument is correct, though :(
      singulars
      1. PO
      1. USYves Daoust
    2. COI've tried adding a section going over my argument step by step
      singulars
      1. PO
      1. USmcdowella
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload