Minimale Anzahl der Kreise mit radius r um die n-Punkte

Was ist die minimale Anzahl von Kreisen mit radius r benötigt, um alle n Punkte?
r und n gegeben werden, die als Eingabe, gefolgt von der n Paare von Ganzzahlen, die die x-y-Koordinaten der n Punkte.
r ist eine reelle Zahl und größer als 0 ist. n < 20.

Kreis deckt einen Punkt, wenn der Punkt liegt innerhalb des Kreises.
Ein Punkt liegt in einem Kreis, falls der Abstand zwischen dem Punkt und dem Kreismittelpunkt kleiner als oder gleich r.

  • Dies ist nicht eine Frage der Programmierung? Wissen Sie, es gibt eine Sache, genannt wettbewerbsfähige Programmierung? Ich versuche, ein problem zu lösen, und ich erkannte, dass ich zur Lösung dieses sub-problem zunächst. Warum denkst du, jeder fragt Sie um Ihre Hausaufgaben zu tun für Sie?
  • Fragen wie diese sind in der Regel akzeptabel, aber es hilft immer, um zu zeigen, einige versuchen zu lösen das problem selbst zuerst. @PhillipSchmidt Das klingt wie eine Programmierung Frage an mich.
  • Ich dachte an eine 2^n * 2^n-Lösung, aber das ist nicht zur Arbeit zu gehen, als n werden kann, 20. Ich denke, es existiert ein n * 2^n oder n^2 * 2^n-Algorithmus, kann aber nicht herausfinden.
  • Die VC-dimension der Platten ist 3, also gibt es O(n^3) unterschiedliche Kreise mit Bezug auf die die angegebenen Punkte...
  • Eisenstat, was soll das bedeuten? O(n^3) verschiedene Kreise? Von wo hast du das?
  • Sauer ' s lemma
  • Danke, aber ich weiß nicht wirklich verstehen, was das bedeutet. Können Sie erklären, wie aufwändig das löst mein problem?
  • Sie haben immer zu Fragen, wenn etwas ausgelassen wird beim kopieren ein problem wie dieses. Die x -, y-Punkte Ganzzahlen scheint nicht zu helfen, aber natürlich würde es helfen, eine Tonne, wenn zum Beispiel die Kreis-Zentren wurden intergral.
  • Fragen auf, SO sollen in der Lage sein, zu beantworten in einem Programmier-Kontext. Siehe hier. Diese Frage wäre wesentlich besser geeignet für Mathematik.SO
  • Ich habe gesehen, 1000er ähnlich (nicht geschlossene) Fragen (es ist "ein software-Algorithmus"). Diese Probleme sind wahrscheinlich 100 mal schwieriger zu lösen, mit der Mathematik als algorithmen, so Mathematik ist wahrscheinlich nicht der richtige Ort. Wenn Sie jemals Lesen ein Buch algorithmen, dann sollten Sie wissen, dass diese Arten von Problemen sind ein großer Teil der Computer-Wissenschaft, und Sie braucht auf jeden Fall ein Ort, der vor allem hier zur Zeit (auch on-topic für informatik, aber Sie sind etwas ungewöhnlich, es). Es kann nicht eine echte Frage, der aktuelle Zustand, aber das bedeutet nicht, es ist off-topic.
  • Ich wäre glücklich mit entweder einigen Aufwand gezeigt, oder den Zusammenhang, um zu zeigen, dass dies nicht nur "bitte mache meine Hausaufgaben'.
  • wow vielen Diskussionen -- jemand darauf, zu versuchen, Ihren code auf dieses Beispiel..r=3 Punkte = {{3, 7}, { -6, -10}, {4, -7}, { -9,2}, { -4,-4}, {3, -1}, {7, -3}, {10, -1}, { -1, -6}, { -1, 3}, { -9, -3}, {9, -4}, { -4, 7}, {2, -7}, { -2, -10}, { -10,6}, {9, -8}, { -5, 5}, {6, 4}, { -4, -7}} Meine Antwort N=9 ..
  • Bekomme ich 10 Kreise.
  • Denken Sie an diese relative, aber einfacheres problem: mit n Punkten in einer Linie, finden Sie die minimale Anzahl der Liniensegmente der Länge l, die alle Punkte.
  • Sie sind bereit, die ein etwas anderes problem, es sollte wohl eine neue Frage. Sie sind ok mit der n<20 Bestimmung???
  • Ich dachte, ich würde bounty hier, weil das ist, wo die Diskussion ist. n < 1000 wäre meine persönliche Bedingung. Eine Lösung für alle n wäre toll, obwohl, ich weiß, das ist ein sehr teures problem.

InformationsquelleAutor user2040997 | 2013-04-08
Schreibe einen Kommentar