?url_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rft.title=Ajuste+de+particiones+planas+mediante+diagramas%0D%0Ade+Voronoi+discretos&rft.creator=Garc%C3%ADa+Bernal%2C+Daniel&rft.contributor=Abellanas+Oar%2C+Manuel&rft.subject=Mathematics&rft.description=La+geometr%C3%ADa+computacional+se+centra+en+el+dise%C3%B1o+y+an%C3%A1lisis+de+algoritmos%0D%0Apara+problemas+geom%C3%A9tricos.+En+la+%C3%BAltima+decada%2C+esta+disciplina+ha+atra%C3%ADdo%0D%0Aun+enorme+inter%C3%A9s.+Pero+ha+sido+en+los+%C3%BAltimos+a~nos+cuando+se+ha+incrementado%0D%0Ael+inter%C3%A9s+en+una+estructura+geom%C3%A9trica%2C+concretamente+los+diagramas%0D%0Ade+Voronoi.+No+solo+por+sus+caracter%C3%ADsticas+y+propiedades+matem%C3%A1ticas%2C+sino%0D%0Atambi%C3%A9n+por+aparecer+ampliamente+relacionados+con+fen%C3%B3menos+y+procesos%0D%0Af%C3%ADsicos+que+se+dan+en+la+naturaleza.%0D%0ALos+diagramas+de+Voronoi+se+construyen+a+partir+de+una+simple+idea%2C+dado%0D%0Aun+n%C3%BAmero+de+puntos+en+el+plano%2C+el+diagrama+de+Voronoi+divide+el+plano+seg%C3%BAn%0D%0Ala+regla+del+vecino+m%C3%A1s+cercano%3A+cada+punto+se+asocia+con+la+regi%C3%B3n+del+plano%0D%0Am%C3%A1s+cercano+a+%C3%A9l.%0D%0AEn+este+trabajo%2C+el+objetivo+consistir%C3%A1+en+estudiar+el+proceso+inverso%2C+llamado%0D%0AProblema+del+Voronoi+inverso+(PVI).+El+PVI+trata+de%2C+a+partir+de%0D%0Auna+partici%C3%B3n+de+un+plano+dado%2C+que+es%2C+o+que+se+asemeja%2C+a+un+diagrama+de%0D%0AVoronoi%2C+obtener+los+puntos+generadores+de+este%2C+y+si+no%2C+aquellos+de+aquel%0D%0Adiagrama+de+Voronoi+que+m%C3%A1s+se+asemeje.%0D%0APara+resolver+esto%2C+se+desarrollar%C3%A1n+una+serie+de+m%C3%A9todos+heur%C3%ADsticos%2C+como%0D%0Ael+m%C3%A9todo+del+Descenso+m%C3%A1s+pronunciado+y+el+m%C3%A9todo+del+recocido+simulado%2C+en%0D%0Ac%C3%B3digo+Python%2C+con+el+fin+de+obtener+una+soluci%C3%B3n+%C3%B3ptima%2C+para+posteriormente%0D%0Apoder+realizar+un+an%C3%A1lisis+y+estudio+de+las+soluciones+obtenidas.+Este+estudio%0D%0Ase+realizar%C3%A1+en+el+%C3%A1mbito+discreto%2C+ya+que+las+particiones+a+estudiar+vendr%C3%A1n%0D%0Adadas+en+formato+de+imagen%2C+es+decir%2C+una+matriz+mxn+de+p%C3%ADxeles.+Esto%0D%0Aconllevar%C3%A1+a+desarrollar+un+Generador+de+diagramas+de+Voronoi+modificados%2C%0D%0Aque+se+dise%C3%B1ar%C3%A1+en+la+parte+de+preproceso+de+la+aplicaci%C3%B3n%2C+que+permitir%C3%A1%0D%0Aobtener+distintas+particiones+en+formato+de+imagen+para+poder+poner+a+prueba%0D%0Ala+aplicaci%C3%B3n+desarrollada.---ABSTRACT---Computational+geometry+is+concerned+with+the+design+and+analysis+of+algorithms%0D%0Afor+geometrical+problems.+Computational+geometry+has+attracted%0D%0Aenormous+research+interest+in+the+past+decade.+But+it+has+been+in+the+last%0D%0Ayears+when+the+interest+towards+the+geometric+stucture%2C+called+Voronoi+diagrams.%0D%0Ahas+increased.+Those+diagrams+recevie+so+much+attention+due+to+their%0D%0Amathematical+properties+and+their+appearance+in+diferent+phenomena+and%0D%0Aprocess+in+the+nature.%0D%0AConstructing+a+Voronoi+diagram+just+needs+a+simple+idea.+Given+a+certain%0D%0Anumber+of+points+in+the+plane%2C+their+Voronoi+diagram+divides+the+plane+according%0D%0Ato+the+nearest-neighbor+rule%3A+Each+point+is+associated+with+the+region%0D%0Aof+the+plane+closest+to+it.%0D%0AIn+this+project%2C+the+objective+will+be+to+study+the+inverse+process%2C+called%0D%0AInverse+Voronoi+problem+(IVP).+The+IVP+consists+of+obtaining+the+generators%0D%0Apoints+of+a+Voronoi+diagram+which+matches%2C+or+it+is+similar%2C+to+a+given%0D%0Apartition.%0D%0AIn+order+to+resolve+this+problem%2C+it+will+have+to+developed+a+number+of%0D%0Aheuristic+methods%2C+such+as%3A+Method+of+steepest+descent+and+simmulated+annealing%3B%0D%0Ain+Python+code%2C+so+that+an+optimal+solution+can+be+obtained%2C+to+later%2C%0D%0Aperform+an+analysis+and+study+of+those+solutions.+This+study+will+be+developed%0D%0Ain+a+discrete+scope%2C+because+the+partitions+will+be+given+in+the+format+of+an%0D%0Aimage%2C+in+other+words%2C+a+matrix+mxn+of+pixels.+It+will+carry+the+development%0D%0Aof+a+modify+Voronoi+diagrams+Generator%2C+designed+in+preprocessign+phase+of%0D%0Athe+application%2C+that+will+permit+to+get+several+partitions+in+the+format+of+an%0D%0Aimage+in+order+to+test+the+application.&rft.publisher=E.T.S.+de+Ingenieros+Inform%C3%83%C2%A1ticos+(UPM)&rft.rights=https%3A%2F%2Fcreativecommons.org%2Flicenses%2Fby-nc-nd%2F3.0%2Fes%2F&rft.date=2017-06&rft.type=info%3Aeu-repo%2Fsemantics%2FbachelorThesis&rft.type=Final+Project&rft.type=NonPeerReviewed&rft.format=application%2Fpdf&rft.language=spa&rft.rights=info%3Aeu-repo%2Fsemantics%2FopenAccess&rft.identifier=https%3A%2F%2Foa.upm.es%2F47124%2F