Resumen de 2d and 3d noisy colored point set matching under the bottleneck distance

Santiago Díez Donoso

• Determinar la presència d'un determinat patró en un conjunt d'objectes  és un problema fonamental en geometria computacional, Ens centrem en el cas particular de l''Emparellament de conjunts de punts amb color en preséncia de soroll per a moviments rígids sota la distància 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 rígids representatius que porten A a prop d'un subconjunt B' de B. Com que el cost assimptòtic d'aquest algorisme  és alt, tamb é presentem una versió alternativa amb cost computacional millorat. Aquesta segona versió té, però, un problema: Totes les solucions que  troba són correctes, però pots 'perdre'n' algunes. Per a millorar encara més el cost d'ambdós  algorismes, presentem un algorisme de preproces de filtratge sense pèrdua. Hem implementat  els algorismes presentats i realitzat experiments usant dades sintètiques així com d'altres de  provinents del problema real del reconeixement de constel.lacions. També presentem una  adaptaciò dels nostres algorismes per resoldre el problema pràctic de 'l'emparellament de  conjunts de carreteres' i analitzem el problema relacionat de 'l'emparellament de conjunts de punts amb restricció de finestra'.

   Respecte la versió tridimensional del problema, transportem algunes de les idees de la versió  2D. Donem una formulació teòrica així  com un estudi experimental. Aquest estudi està fet   utilitzant dades reals del 'protein data bank' així com dades sintètiques. També ens fixem en les característiques concretes d'un dels nostres problemes de motivació (detecció de subestruc­  ures en proteïnes) per tal d'obtenir un algorisme més ràpid pel cas restringit.

   Finalment, presentem aspectes pràctics tant pel que fa a donar alguns detalls de la im­  plementació dels algorismes com a discutir la metodologia d'experimentació emprada en la  realització d'aquesta tesi.