|
Titlul: Minimal enclosing circle Scris de: Andrei Grigorean din Noiembrie 18, 2007, 16:14:46 Un prieten de-ai mei mi-a spus recent o problema care are legatura cu articolul prezentat.
Dandu-se N puncte in plan, sa se demonstreze ca daca enclosing circle-ul pentru oricare 3 puncte are raza <= 1, atunci enclosing circle-ul pentru toate cele N puncte are raza <= 1. Demonstrand cele afirmate mai sus, putem gasi o noua metoda brute-force in O(N^3). Pur si simplu luam oricare 3 puncte, calculam raza enclosing cicle-ului si retinem maximul dintre razele astea. Titlul: Răspuns: Minimal enclosing circle Scris de: Cosmin Negruseri din Noiembrie 18, 2007, 16:26:12 Stai, daca ai 3 puncte colineare, raza celui mai mic cerc e infinit, dar tu ai un cerc ce el contine de diametru egal cu distanta intre cele mai departate doua. Ce nu inteleg?
Edit:mda, tu ziceai de enclosing circle nu cerc circumscris ... O varianta mai inceata, dar mai rapida ca n^4 ar fi sa faci cautare binara pe dimensiunea razei. Titlul: Răspuns: Minimal enclosing circle Scris de: Andrei Grigorean din Decembrie 14, 2007, 14:48:25 Nu incearca nimeni sa rezolve problema prezentata? :(
Titlul: Răspuns: Minimal enclosing circle Scris de: Stefan Istrate din Februarie 20, 2009, 02:14:04 Discutiile pot continua in topicul destinat acestui articol: http://infoarena.ro/forum/index.php?topic=3684.0
|