iXdi - Σύγχρονος προγραμματισμός

μέγιστος αριθμός σημείων που περικλείονται σε δεδομένη περίμετρο

Δεδομένης μιας σειράς συντεταγμένων ορισμένων σημείων και ενός σχοινιού σταθερής περιμέτρου, πώς θα μπορούσα να υπολογίσω τον μέγιστο αριθμό σημείων που μπορεί να περικλείει αυτό το σχοινί; (Εννοώ αλγόριθμους άλλους από την ωμή δύναμη)

π.χ.: δίνεται [[0,1],[0,0],[1,1],[1,0],[100,100]] και σχοινί μήκους 4, τότε αυτό το σχοινί μπορεί να περικλείει τους πρώτους 4 πόντους.

algorithm computational-geometry
29.10.2017

  • Εάν το σχοινί μπορεί να σχηματίσει οποιαδήποτε γεωμετρία, ακούγεται ότι αυτό θα μπορούσε να είναι πολύ ακριβό για τον υπολογισμό. Πείτε ότι υπάρχουν 10 σημεία σε μια γραμμή και το σχοινί σας μπορεί να δημιουργήσει ένα ορθογώνιο γύρω τους. Αλλά σε ένα άλλο σενάριο, τα σημεία είναι διάσπαρτα σε μια ακτίνα που το σχοινί μπορεί να περικλείει με έναν κύκλο. Η προσπάθεια να αποφασίσετε τι σχήμα πρέπει να πάρει το σχοινί για να περικλείσει τον μέγιστο αριθμό σημείων ακούγεται σαν ένα πραγματικά δύσκολο (δηλαδή υπολογιστικά δύσκολο) πρόβλημα. 30.10.2017
  • @yacc σκέφτηκα ότι αυτό μπορεί να γίνει με ωμή βία τουλάχιστον; δεδομένου n σημείου, τότε υπάρχουν (n,1)+(n,2)+...(n,n) τρόποι συλλογής αυτών των σημείων, και για κάθε τρόπο συλλογής, μπορούμε να βρούμε το κυρτό κύτος αυτών των σημείων, επομένως το η περίμετρος αυτής της κυρτής γάστρας, και η κυρτή γάστρα που μας δίνει μια περίμετρο που είναι μικρότερη και πιο κοντά στο μήκος του σχοινιού είναι η απάντηση, υποθέτω; 30.10.2017
  • Α, αλήθεια. Νόμιζα ότι χρειαζόσουν όλα τα πιθανά σχήματα. Μια ιδέα θα μπορούσε να είναι να ταξινομήσετε τα σημεία σχετικά με την κοντινότερη απόστασή τους από οποιοδήποτε άλλο σημείο και να απορρίψετε τα πιο μακρινά. 30.10.2017

Απαντήσεις:


1

Μόλις βρήκα αυτόν τον σύνδεσμο :Η ελάχιστη περίμετρος κυρτή γάστρα ενός υποσυνόλου ενός συνόλου σημείων

η απάντηση με τις περισσότερες ψήφους έδωσε στις πηγές να βρουν την ελάχιστη περιοχή k-gon, οπότε τώρα με τη δυαδική αναζήτηση, η πολυπλοκότητα μπορεί να είναι O(n^4*(logn))

30.10.2017
  • Δεν εννοείς ελάχιστη περίμετρο; 30.10.2017
  • Μια ενδιαφέρουσα προσέγγιση, αλλά μπορεί κανείς να αναρωτηθεί αν πραγματικά διαφέρει από την ωμή βία. Πόσα κυρτά πολύγωνα μπορεί να σχηματίσει κανείς με Ν σημεία; (Δεν έχω την παραμικρή ιδέα). 30.10.2017

    • 2

    Αυτό που ψάχνετε είναι ένα Το πρόβλημα της βόμβας. Ελέγξτε τον σύνδεσμο που παρέχει εξηγήσεις για την προσέγγιση. Επίσης παρόμοια ερώτηση υπάρχει ήδη : Μέγιστος εγκλειστικός κύκλος μιας δεδομένης ακτίνας

    30.10.2017
  • Δεν νομίζω ότι έχουν σχέση. Το σχοινί δεν χρειάζεται να σχηματίσει κύκλο. 30.10.2017
  • Νομίζω ότι η ερώτηση ήταν σύντομη, γι' αυτό θεωρήθηκαν λίγες υποθέσεις, Χρειάζεται κάποια διευκρίνιση, π.χ. Όταν λέτε να επισυνάψετε: Σημαίνει ότι το σχοινί πρέπει να περάσει από κορυφές; ή οι κορυφές μπορούν να καλυφθούν μέσα σε οποιονδήποτε διαμορφωμένο κύκλο; 30.10.2017
  • Το σχοινί ΜΠΟΡΕΙ να περάσει από κορυφές, παρατηρήστε ότι στο παράδειγμα που έφτιαξα, το σχοινί θα πρέπει να περάσει το 00 01 10 11 για να τις περικλείσει. Εν τω μεταξύ, δεν χρειάζεται να περάσει κανένα πόντο, π.χ.: αν αντικαταστήσω τα [0,0], [0,1] ,[1,0], [1,1],[100,100] με [0,1,0,1] ,[0,1,0,9],[0,9,0,1],[0,9,0,9],[100,100] τότε το σχοινί μπορεί να περικλείσει πρώτα 4 σημεία χωρίς να τους περάσει. Αυτό εννοούσα για το «εσωκλείω» στην ερώτηση, συγγνώμη για την ασάφεια 30.10.2017
  • @akshaydhule: για μένα είναι σαφές ότι το σχοινί πρέπει απλώς να περιλαμβάνει το κυρτό κύτος των σημείων και η λύση στο πρόβλημα της βόμβας δεν θα λειτουργήσει. 30.10.2017
  • Σίγουρα @YvesDaoust . Δεν ήταν για μένα και για εσάς, τώρα ακόμα κι εγώ ξέρω ότι δεν θα λειτουργήσει. Ευχαριστώ για τη συμβολή σας. 30.10.2017
  • Επίσης, η μικρότερη κυρτή γάστρα που καλύπτει τα μέγιστα σημεία θα περάσει σίγουρα από κορυφές. Βρείτε λοιπόν μοναδικά ζευγάρια [κύκλος, απόσταση‹len(σχοινί)] και αυτό με μέγιστους πόντους θα δώσει το soln. 30.10.2017
  • Βρήκες λύση; και θα μπορούσατε να εξηγήσετε τι και πώς λειτουργούν τα μοναδικά ζεύγη κύκλων; 21.02.2018
    • Νέα υλικά
    The Perpetual Student: Γιατί ένας Μηχανικός Λογισμικού μαθαίνει πάντα
    Στον ταχέως εξελισσόμενο κόσμο της τεχνολογίας, οι μηχανικοί λογισμικού μαθαίνουν συνεχώς. Ο τομέας της ανάπτυξης λογισμικού είναι δυναμικός, με τα εργαλεία, τις γλώσσες, τα πλαίσια και τις..
    Καθαρισμός δεδομένων, Επιλογή χαρακτηριστικών, Μοντελοποίηση και Ερμηνευσιμότητα
    Ο καθαρισμός δεδομένων, η επιλογή χαρακτηριστικών, η μοντελοποίηση και η ερμηνευτικότητα είναι κρίσιμα βήματα για την ανάπτυξη ενός επιτυχημένου μοντέλου μηχανικής εκμάθησης. Τα ακριβή και..
    Code Smell 210 - Dynamic Properties
    Η τεμπελιά και η μαγεία φέρνουν ελαττώματα TL;DR: Να είστε ξεκάθαροι με τα χαρακτηριστικά σας Προβλήματα Ευανάγνωστο Ορισμός πεδίου εφαρμογής Απαρατήρητα τυπογραφικά λάθη..
    Οπτικοποίηση δεδομένων με γραφήματα Google
    του Ejiro Thankgod Η οπτικοποίηση δεδομένων είναι μια εξαιρετική προσέγγιση για την εμφάνιση δεδομένων και τη συμμετοχή κοινού. Ο ανθρώπινος νους είναι συχνά καλύτερος στο να θυμάται..
    Το όνομά μου είναι Abdul Qudus.abd
    Το όνομά μου είναι Abdul Qudus.abd Είμαι διαδικτυακός συγγραφέας και γράφω άρθρα. Έχω 3ετή εμπειρία στη διαδικτυακή συγγραφή. οπότε θα είμαι ο καλύτερος συγγραφέας στην πλατφόρμα σας. είμαι ο..
    Το Python Selenium Web Scraping σας κατέβασε το 2023; Εκκαθαρίστε την προσωρινή μνήμη και ενισχύστε τα αποτελέσματά σας!
    Η απόξεση ιστού με το Python Selenium είναι ένα εξαιρετικό εργαλείο για την εξαγωγή δεδομένων από ιστοσελίδες. Ωστόσο, περιστασιακά, οι ιστοσελίδες ενδέχεται να αποτύχουν να φορτώσουν ή να..
    Έννοιες JavaScript που πρέπει να γνωρίζετε για να ξεκινήσετε με το React
    Αφού είδα αυτή την ερώτηση να τίθεται αμέτρητες φορές, πιστεύω ότι μπορεί να είναι χρήσιμο σε πολλούς ανθρώπους εκεί έξω να έχουν μια σαφή κατανόηση του τι χρειάζεται να είναι γνωστό στο..