FoxCalculators - Δωρεάν υπολογιστές στο διαδίκτυο!

Κάντε δεξί κλικ: Διαγραφή σημείου

Αριστερό κλικ: Προσθήκη σημείου ή μετακίνηση. Μπορείτε επίσης να σύρετε το σημείο.

Το πρόβλημα του μικρότερου κύκλου ή το ελάχιστο πρόβλημα κάλυψης είναι ένα μαθηματικό πρόβλημα του υπολογισμού του μικρότερου κύκλου που περιέχει όλα ένα δεδομένο σύνολο σημείων στο ευκλείδειο επίπεδο. Το αντίστοιχο πρόβλημα στον Ν-διαστατικό χώρο, το μικρότερο πρόβλημα οριοθέτησης-σφαίρας, είναι να υπολογίσουμε τη μικρότερη n-σφαίρα που περιέχει όλα ένα δεδομένο σύνολο σημείων. [1] Το μικρό πρόβλημα του κύκλου προτάθηκε αρχικά από τον αγγλικό μαθηματικό James Joseph Sylvester το 1857.

Το μικρό πρόβλημα κύκλου στο αεροπλάνο είναι ένα παράδειγμα προβλήματος θέσης εγκατάστασης (το 1-κέντρο πρόβλημα) στο οποίο πρέπει να επιλεγεί η θέση μιας νέας εγκατάστασης για την παροχή υπηρεσιών σε διάφορους πελάτες, ελαχιστοποιώντας την πιο απομακρυσμένη απόσταση που οποιοσδήποτε πελάτης πρέπει να ταξιδεύουν για να φτάσουν στη νέα εγκατάσταση. Τόσο το μικρότερο πρόβλημα κύκλου στο επίπεδο και το μικρότερο πρόβλημα σφαίρας οριοθέτησης σε οποιοδήποτε υψηλότερο χώρο διαστασιακού χώρου με οριοθετημένη διάσταση, μπορεί να λυθεί σε γραμμικό χρόνο.

Οι περισσότερες από τις γεωμετρικές προσεγγίσεις για το πρόβλημα αναζητούν πόντους που βρίσκονται στο όριο του ελάχιστου κύκλου και βασίζονται στα ακόλουθα απλά γεγονότα:

Ο ελάχιστος κύκλος κάλυψης είναι μοναδικός.

Ο ελάχιστος κύκλος κάλυψης ενός συνόλου S μπορεί να προσδιοριστεί με τα περισσότερα τρία σημεία σε S που βρίσκονται στο όριο του κύκλου. Εάν προσδιορίζεται μόνο από δύο σημεία, τότε ο τομέας γραμμής που συνδέει αυτά τα δύο σημεία πρέπει να είναι μια διάμετρος του ελάχιστου κύκλου. Εάν καθορίζεται από τρία σημεία, τότε το τρίγωνο που αποτελείται από αυτά τα τρία σημεία δεν είναι αμβλύ.