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

Μαΐου 31, 2013

Γρήγορος υπολογισμός διαμέτρου

Filed under: Άλυτα Προβλήματα — Mihalis Kolountzakis @ 6:42 μμ

Αν έχουμε x_1,\ldots,x_N σημεία σε ένα μετρικό χώρο X, όπου με d(x,y) συμβολίζουμε την απόσταση (μετρική) ανάμεσα στα σημεία x, y \in X, τότε αν θέλουμε να υπολογίσουμε τη διάμετρο του συνόλου A=\{x_1,\ldots,x_N\}

{\mathrm {diam}}(A) = \max\{d(x,y): x,y \in A\}

εκ πρώτης όψεως φαίνεται να χρειάζεται λίγο-πολύ να υπολογίσουμε όλες τις αποστάσεις d(x_i, x_j). Αν υποθέσουμε ότι κάθε υπολογισμός απόστασης παίρνει χρόνο μια μονάδα, τότε ο συνολικός χρόνος που ξοδεύουμε είναι τετραγωνικός, δηλ. της τάξης του N^2.

  1. Αν ο μετρικός μας χώρος είναι ο X={\mathbf R}^k, όπου k είναι μια σταθερά που δεν αλλάζει με το N, και με μετρική την

               d_\infty(x, y)= \max_{j=1,\ldots,k} |x_j-y_j|

    δείξτε ότι η διάμετρος του συνόλου A μπορεί να υπολογιστεί πολύ γρηγορότερα, σε γραμμικό χρόνο \le C_k N, όπου C_k είναι μια σταθερά που δεν εξαρτάται από το N αλλά μόνο από το k.

  2. Το ίδιο αν ο μετρικός χώρος είναι και πάλι το {\mathbf R}^k με μετρική τώρα την

              d_1(x,y) = \sum_{j=1}^k |x_j-y_j|.

Advertisements

3 Σχόλια »

  1. Δεδομένου του οτι η απόσταση στον κάθε άξονα υπολογίζεται ανεξάρτητα από τους άλλους, κάνουμε το εξής : βρίσκουμε την μεγαλύτερη και την μικρότερη τιμή στην κάθε διάσταση χωριστά (χρόνος k * n * c1) και πέρνουμε την μέγιστη διαφορά από αυτές (χρόνος k * c2).

    Μου αρέσει!

    Σχόλιο από Thanos Makris — Σεπτεμβρίου 22, 2013 @ 11:43 πμ

  2. Σωστά για το 1. Για το 2;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 22, 2013 @ 9:07 μμ

  3. Υπόδειξη: Για το 2 χρησιμοποιείστε το 1, αλλά σε μεγαλύτερη διάσταση. Δείξτε ότι μπορείτε να βρείτε μια απεικόνιση T του {\mathbf R}^k σε κάποιο {\mathbf R}^n, με n>k, τέτοια ώστε \|Tx-Ty\|_\infty = \|x-y\|_1 για κάθε x,y \in {\mathbf R}^k.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Δεκέμβριος 21, 2013 @ 6:01 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

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