2d and 3d noisy colored point set matching under the bottleneck distance
Santiago Díez Donoso · Dialnet (Universidad de la Rioja) · 2008
Determinar la presencia d'un determinat patro en un conjunt d'objectes es un problema fonamental en geometria computacional, Ens centrem en el cas particular de l''Emparellament de conjunts de punts amb color en presencia de soroll per a moviments rigids sota la distancia bottleneck'. Proposem diversos algorismes per trobar emparellaments entre dos conjunts de punts A, B: Respecte als problemes en dues dimensions, primer resolem el problema generant tots els moviments rigids representatius que porten A a prop d'un subconjunt B' de B. Com que el cost assimptotic d'aquest algorisme es alt, tamb e presentem una versio alternativa amb cost computacional millorat. Aquesta segona versio te, pero, un problema: Totes les solucions que troba son correctes, pero pots 'perdre'n' algunes. Per a millorar encara mes el cost d'ambdos algorismes, presentem un algorisme de preproces de filtratge sense perdua. Hem implementat els algorismes presentats i realitzat experiments usant dades sintetiques aixi com d'altres de provinents del problema real del reconeixement de constel.lacions. Tambe presentem una adaptacio dels nostres algorismes per resoldre el problema practic de 'l'emparellament de conjunts de carreteres' i analitzem el problema relacionat de 'l'emparellament de conjunts de punts amb restriccio de finestra'. Respecte la versio tridimensional del problema, transportem algunes de les idees de la versio 2D. Donem una formulacio teorica aixi com un estudi experimental. Aquest estudi esta fet utilitzant dades reals del 'protein data bank' aixi com dades sintetiques. Tambe ens fixem en les caracteristiques concretes d'un dels nostres problemes de motivacio (deteccio de subestruc ures en proteines) per tal d'obtenir un algorisme mes rapid pel cas restringit. Finalment, presentem aspectes practics tant pel que fa a donar alguns detalls de la im plementacio dels algorismes com a discutir la metodologia d'experimentacio emprada en la realitzacio d'aquesta tesi.