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

Μαΐου 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

Blog στο WordPress.com.

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