Προβλήματα Μαθηματικών

Ιουνίου 15, 2015

Ο ελάχιστος κύκλος που περικλείει κάποια σημεία

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 1:52 πμ

Ας είναι p_1, p_2, \ldots, p_N σημεία του επιπέδου. Δείξτε ότι κύκλος ελαχίστου εμβαδού που τα περιέχει είναι μοναδικός.

enclosing-circle

Advertisements

18 Σχόλια »

  1. Έστω ο κύκλος (Α, ρ) εκείνος με το ελάχιστο εμβαδό που περικλείει όλα τα σημεία.

    Έστω ότι δεν ανήκει κανένα από τα σημεία που περικλείει στον κύκλο τότε υπάρχει ένας κύκλος (Α, ρ-ε) που περικλείει όλα τα σημεία και έχει μικρότερο εμβαδόν, άτοπο επομένως ο κύκλος του ελαχίστου εμβαδού πρέπει να διέρχεται από τουλάχιστον ένα σημείο.

    Έστω ότι ο ίδιος κύκλος διέρχεται από ένα ακριβώς σημείο Β. Τότε μπορώ να πάρω ένα σημείο Γ πάνω στο ΑΒ κ να σχηματίσω καινούριο κύκλο (Γ, ΓΒ) ο οποίος θα περικλείει όλα τα σημεία και θα έχει μικρότερο εμβαδόν από τον αρχικό άτοπο. Άρα ο κύκλος ελαχίστου εμβαδού πρέπει να διέρχεται από τουλάχιστον 2 σημεία.

    Είναι προφανές πως στην περίπτωση που μας ζητείται κύκλος ελαχίστου εμβαδού που περικλείει 2 σημεία Β, Δ, ο κύκλος που προκύπτει θα έχει διάμετρο ΒΔ. (Προκύπτει εύκολα από τριγωνική ανισότητα για την ακτίνα του κύκλου)

    Άρα αν ο κύκλος ελαχίστου εμβαδού διέρχεται από δύο σημεία τότε είναι αυτόματα μοναδικός αφού θα πρέπει να έχει διάμετρο το ευθύγραμμο σχήμα που ορίζουν τα δύο αυτά σημεία ενώ αν ο κύκλος ελαχίστου εμβαδού διέρχεται από 3 ή παραπάνω σημεία τότε είναι μοναδικός (από τη γνωστή ευκλείδεια γεωμετρία!).

    Μου αρέσει!

    Σχόλιο από Charidimos Kiosterakis — Ιουνίου 15, 2015 @ 3:11 πμ

  2. Μιχάλη δεν είναι trivial. Λόγω χρόνου περιγράφω τη λύση (χωρίς απόδειξη) αδρομερώς.
    Βρίσκεις με τη μέγιστη απόσταση μεταξύ 2 σημείων. Αυτή είναι η διάμετρος του κύκλου. Αν είναι δύο τα σημεία που δίνουν τη μέγιστη διάμετρο έχουμε προφανώς έναν κύκλο.
    Αν πολλά τα ζεύγη σημείων με μέγιστη απόσταση τότε κάνουμε το εξής:
    Ανά ζεύγος σημείων (που δίνουν μέγιστη διάμετρο) ορίζουμε το μέσο σημείο τους.
    Κάνουμε την παραπάνω διαδικασία μόνο για αυτά τα νέα σημεία έως ότου έχουμε ένα εν τέλει μέσο σημείο. Αυτό είναι το κέντρο του κύκλου.

    Μου αρέσει!

    Σχόλιο από Yannis Tzitzikas — Ιουνίου 15, 2015 @ 10:18 πμ

  3. 2: «…ενώ αν ο κύκλος ελαχίστου εμβαδού διέρχεται από 3 ή παραπάνω σημεία τότε είναι μοναδικός (από τη γνωστή ευκλείδεια γεωμετρία!)»

    Αυτό δε λέει τίποτα για το πρόβλημά μας.

    3: «…Βρίσκεις με τη μέγιστη απόσταση μεταξύ 2 σημείων. Αυτή είναι η διάμετρος του κύκλου. Αν είναι δύο τα σημεία που δίνουν τη μέγιστη διάμετρο έχουμε προφανώς έναν κύκλο.»

    Δεν είναι αυτός ο κύκλος. Πάρε π.χ. τα 3 σημεία που να σχηματίζουν ένα σχεδόν ισόπλευρο τρίγωνο (με τις τρεις αποστάσεις διαφορετικές αλλά σχεδόν ίσες).

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 15, 2015 @ 12:23 μμ

  4. Αν υπήρχαν δύο τέτοιοι κύκλοι, θα είχαν την ίδια διάμετρο (αλλιώς ο κύκλος μεγαλύτερης διαμέτρου δε θα ήταν κύκλος ελάχιστου εμβαδού) και διαφορετικά κέντρα. Σε αυτή την περίπτωση, αφού και οι δύο κύκλοι περιέχουν όλα τα σημεία, αυτά θα βρίσκονται όλα στην περιοχή τομής τους και επομένως θα μπορούσαμε να τα χωρέσουμε σε έναν κύκλο με διάμετρο το τμήμα που συνδέει τα σημεία τομής τους, δηλαδή τελικά σε έναν κύκλο με διάμετρο μικρότερη των δύο αρχικών κύκλων. Αντίφαση, άρα ο κύκλος είναι μοναδικός.

    Μου αρέσει!

    Σχόλιο από ΘΑΝΑΣΗΣ ΠΑΠΑΔΗΜΗΤΡΙΟΥ — Ιουνίου 15, 2015 @ 12:28 μμ

  5. 4: Σωστό, αυτή είναι η απόδειξη με εις άτοπον απαγωγή. Αν μπορούσες να επισυνάψεις κι ένα σχήμα (μπορεί κανείς εύκολα να κάνει σχήματα online με διάφορα εργαλεία, όπως π.χ. το sketch.io).

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 15, 2015 @ 12:31 μμ

  6. Τί σημαίνει, θα μπορούσαμε να τα χωρέσουμε σε έναν κύκλο με διάμετρο το τμήμα που συνδέει τα σημεία τομής τους; Τα σημεία μέσα στην τομή δεν είναι αναγκαστικά συνευθειακά.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Ιουνίου 15, 2015 @ 12:44 μμ

  7. Ωραίος Θανάση! Nα προσθέσω -ως απότοκο των παραπάνω προσεγγίσεων, το εξής:
    Ο ελάχιστου εμβαδού κύκλος για το σύνολο {p1,p2…,pn} μπορεί να οριστεί από το πολύ 3 σημεία του συνόλου που κείνται ΟΛΑ πάνω στον κύκλο. Αν μπορεί να οριστεί από 2 σημεία,τότε η χορδή που ενώνει αυτά τα 2 σημεία πρέπει να είναι διάμετρος του ελάχιστου κύκλου. Όταν ορίζεται λοιπόν από 3 σημεία, τότε το τρίγωνο που σχηματίζουν αυτά τα σημεία ΔΕΝ είναι αμβλυγώνιο.

    Μου αρέσει!

    Σχόλιο από George Rizopulos — Ιουνίου 15, 2015 @ 1:03 μμ

  8. «που κείνται ΟΛΑ πάνω στην περίμετρου του κύκλου» εννοούσα προφανώς στο 7.

    Μου αρέσει!

    Σχόλιο από George Rizopulos — Ιουνίου 15, 2015 @ 1:05 μμ

  9. Αν τα σημεία δεν είναι συνευθειακά, μπορούμε μάλιστα να τα τοποθετήσουμε με τέτοιο τρόπο στο επίπεδο, ώστε μην υπάρχει καν άνω φράγμα στο μήκος του polygonal path που τα ενώνει. Δεν βλέπω πως χωράνε σε έναν κύκλο με διάμετρο μικρότερη των δύο αρχικών κύκλων. Ευχαριστώ.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Ιουνίου 15, 2015 @ 1:38 μμ

  10. Kωνασταντίνε, τι ακριβώς δεν καταλαβαίνεις από την απόδειξη του Θανάση; Η τομή 2 ίσων κύκλων έχει μια κοινή χορδή. Η κοινή αυτή χορδή είναι πάντα μικρότερη από τη διάμετρο των κύκλων. Αυτή η χορδή αν αποτελέσει διάμετρο ενός κύκλου , αυτός ο κύκλος υπερκαλύπτει πάντα το εμβαδό της τομής. Αλλά αυτός ο κύκλος ,αφού έχει διάμετρο μικρότερη της αρχικής διαμέτρου των 2 κύκλων, είναι μικρότερος. Άρα όχι ο ελάχιστος.

    Μου αρέσει!

    Σχόλιο από George Rizopulos — Ιουνίου 15, 2015 @ 2:19 μμ

  11. Γιώργο, τα σημεία όμως μπορεί να είναι διάσπαρτα και η ευθεία που ενώνει 3 σημεία από το σύνολο για παράδειγμα δεν θα έχει το ελάχιστο δυνατό μήκος.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Ιουνίου 15, 2015 @ 2:40 μμ

  12. Συγνώμη. Τώρα »ήρθα εις εαυτόν».

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Ιουνίου 15, 2015 @ 2:44 μμ

  13. Γεώργιε, το σχόλιο 7 είναι διαφορετική λύση; Μπορείς να την εξηγήσεις πιο λεπτομερώς; Δεν γνωρίζουμε κατά πόσο 2 ή 3 σημεία του συνόλου είναι πάνω στην περιφέρεια του κύκλου με το ελάχιστο εμβαδόν.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Ιουνίου 15, 2015 @ 4:25 μμ

  14. Σίγουρα 2 από τα σημεία του συνόλου πρέπει να περιέχονται μέσα στον κύκλο.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Ιουνίου 15, 2015 @ 11:47 μμ

  15. 14. Διόρθωση: Σίγουρα 2 από τα σημεία του συνόλου πρέπει να περιέχονται πάνω στην περιφέρεια του κύκλου.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Ιουνίου 15, 2015 @ 11:48 μμ

  16. Αν ακριβώς 2 είναι τα σημεία πάνω στην περιφέρεια του κύκλου με ελάχιστο εμβαδόν, τότε είναι αντιδιαμετρικά;

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Ιουνίου 15, 2015 @ 11:51 μμ

  17. Ουσιαστικά ο κύκλος ελαχίστου εμβαδού που περιέχει όλα τα σημεία, περιέχει πάντοτε 2 σημεία του συνόλου πάνω στην περιφέρεια του, που να είναι αντιδιαμετρικά. Αυτά τα δύο καθορίζουν και την εξίσωσή του.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Ιουνίου 16, 2015 @ 12:06 πμ

  18. Το 17. είναι λάθος. Ένα ισόπλευρο τρίγωνο είναι γνωστό αντιπαράδειγμα αφού το κεντροειδές ορίζει τον ζητούμενο κύκλο και κανένα ζεύγος από τα τρία σημεία-κορυφές του τριγώνου δεν είναι αντιδιαμετρικά.

    Μου αρέσει!

    Σχόλιο από Κωνσταντίνος Κουρουζίδης — Ιουνίου 16, 2015 @ 8:16 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: