Geometria discreta i computacional. Problemes

tn w => ,O - 1- f<C :E w 1- <C :E w e � ::> 1-- (.) z w GEOMETRIA DISCRETA 1 COMPUTACIONAL PROBLEMES Ferran Hurtado Departament de Matematica Aplicada 2 UNIVERSITAT POLITECNICA DE CATALUNYA Blbttoteca o�--- 1 �11111� 111� 11111 m 11��111111�111�111 1400607866 r. - ...J ...J MAT GDC Facultat de Matematiques i Estadística UNIVERSITAT POLITÉCNICA DE CATALUNYA 1 \ \ \ 1 1 1 1 \ 1 1 1 1 1 1 1 1 \ UN\VERSITAT pOLITECNICA DE CATALUNYA BIBLIOTECA EX-LIBRIS Títol: Geometña discreta i computacional. Problemes. Autor: Ferran Hurtado Dipósit Legal: B -42755 -2005 lmprés per: Servis Gnifics Copisteria lmatge S.L. Pau Gargallo, 5 08028 Barcelona Nota introductoria Aquesta col-lecció de problemes no segueix l'ordre de desenvolupament cronologic del pr grama de l'assignatura, sinó que és organitzada per grups conceptuals, els quals no són sempre totalment disjunts. Tampoc no hi ha cap ordenació progressiva en la dificultat. Els problemes que tenen l'indicatiu *ed requereixen l'ús d'estructures de dades no imm diates per resoldre'ls, mentre que l'indicatiu *Ig significa que cal establir lemes geometrics previs no immediats. Barcelona, setembre de 2005 POLÍGONS I POLIGONALS SIMPLES Problema 1.- Donat un n-polígon P (simple, convex), i tenint en compte !'estructura de dades que el descriu, trobeu algorísmicament a) els vertexs d'abscissa extrema; b) les interseccions amb una recta donada; c) les tangents des d'un punt donat; d) el punt més proper a una línia donada. Problema 2.- Sigui C una poligonal tancada de n costats, possiblement no simple. Trobeu un algorisme per decidir si C defineix o no un polígon simple. Problema 3.- Establiu un algorisme per decidir, donats un n-polígon simple Pi un punt q, si q és a !'exterior, sobre la vora o a !'interior de P. Estudieu la possible millora quan P és convex i descrit per una estructura que permeti cerca binaria. Problema 4.- Siguin P un n-polígon convex i Q un m-polígon simple del qual tenim també donada una triangulació del seu interior i de cadascun dels "polígons butxaca" (Figura 1) situats entre Q i la seva envolupant convexa. Demostreu que la intersecció P n Q es pot calcular en temps O(m + n) . ... Figura 1: Un polígon i un dels seus polígons butxaca. 1 Problema 5.- Demostreu que el valor X¡ Yl 1 x2 Y2 1 X3 Y3 1 és l'area del triangle de vertexs A = (xi, y¡), P2 = (x2, Y2) i P3 = (x3, y3) afectada pel signe que tingui el recorregut A --+ P2 --+ P3. Utilitzeu aquest concepte per dissenyar un algorisme que calculi l'area d'un polígon simple P den costats. Problema 6.- Trobeu un algorisme O(n) per triangular un n-polígon estrellat donat un punt del nucli. Problema 7.- Doneu un algorisme lineal per decidir si un polígon simple és estrellat. Problema 8.- Trobeu un algorisme per decidir, donat un polígon simple P, si existeix alguna direcció per a la qual P sigui monoton. Problema 9.- Un polígon isotetic és aquell que té tots els costats horitzontals o verticals. Una piramide isotetica és un polígon isotetic monoton respecte de la vertical tal que el costat horitzontal inferior h (la "base") té longitud igual la suma dels al tres costats horitzontals (dues "escales" des de h al costat superior) (Figura 2). a) Demostreu que tota piramide isotetica pot partir-se amb diagonals en quadrilaters convexos. b) Desenvolupeu un algorisme per trobar tal partició (es pot fer en temps lineal) . ... ..... . .. .. .... . ········ . .. .. ..... . .. ...... . .......... . ······ .. ...... .. . .. .. .. .. .. . .... . .... .. ... ... . ······ ···· .. . ..... .. .... . .... ... ... .. . .. ...... ... . .... .. . ... .. . .. . ... ... .. . ...... . .... .. ... ...... . . .... ... . .. .... . . ·.·.··· ························--- .. . ·.·.•.-:-:-:-:-:-:-:-:-:-: -:-:-:-:-:-:•. ·.·.•.•,•,• -•,•,•- · .·.·.·.·-·-·.·-·-·.·.·.·,•.•,•,•.·.·.·.·.·.·.·.· -·.·.·.·.·.· ....... :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: ,•,•-•,·.·.·.·.•,·,•,•,•,•.·.·.·.·.·.·.·.·.·.·.·.·, ·.·,·.-.·.-. · .·.-.·.-.· .-.•,•,•,• -·.·-·.·.·.·.·. ·.·.·.·.·-·,·,·.·.·.·.·.·.·.·.·.•.•,·-·.-.·,•, ·.· h Figura 2: Piramide isotetica de base h. Problema 10.- Feu un algorisme per partir un polígon isotetic en rectangles emprant segments alineats amb costats del polígon. Obteniu tan poques peces com sigui possible i tan de pressa com sigui possible. La sortida de l'algorisme ha de donar una descripció completa de la partició. 2 Problema 11.- Sigui P una poligonal x-monotona de n vertexs, tots ells d'ordenada positiva, i siguin a i b les abscisses mínima i maxima, respectivament, dels punts de P. S'anomena terreny la porció del pla limitada per l'eix x, les verticals x = a, x = b i la poligonal P. Es diu que P és el perfü del terreny (Figura 3). a) Caracteritzeu el conjunt S de punts dins de la franja a � x � b que són per sobre de Pi "veuen" tot P. Doneu un algorisme per trobar el punt de S d'ordenada mínima. b) Doneu un algorisme per trobar el punt del perfil que permet de construir la torre menys alta tal que des de dalt es veu tot P. x=a x=b y=O Figura 3: Terreny de perfil P. El punt q no veu tot P. Problema 12.- Diem que un polígon P és debilment visible des d'un costat a, quan tot punt Q de P, interior o de la frontera, veu almenys un punt M del costat a (és a dir, que el segment QM no té cap punt exterior a P) (Figura 4). Doneu un algorisme O(n) per triangular polígons debilment visibles des d'un costat donat. Demostreu la correcció de l'algorisme, feu-ne clarament l'analisi del cost, i expliqueu quin paper hi juga exactament la propietat de visibilitat del poligon. a Figura 4: Polígon debilment visible des de a. 3 Problema 35.- Donat un polígon Q convex den vertexs, considerem tots els cercles que cobreixen Q i tenen el centre a la frontera de Q. Trobeu un algorisme per obtenir el punt A de la frontera que permet de fer-ho amb radi mínim. Problema 36.- Sigui S un conjunt de n punts al pla. a) Sigui p un punt interior a conv(S). Proposeu un algorisme que calculi el cercle més gran que passa per p i no conté cap punt de S al seu interior. b) Sigui p un punt exterior a conv(S). Proposeu un algorisme que calculi el cercle més petit que passa per pi conté tots els punts de S. Problema 37.- Donat un conjunt S ={Pi, ... , Pn} de punts del pla en posició general i en un cert sistema de referencia, doneu un algorisme per trobar la recta r que fa mínima la máxima distancia vertical dels punts de S a la recta (Figura 12). Figura 12: Distancies verticals dels punts a una recta. Problema 38.- Siguin B un conjunt de punts "blancs" i N un conjunt de punts "negres" en el pla, amb IBI + INI = n. Suposem que tots els punts de BUN tenen abscissa diferent, i que tant el d'abscissa mínima, p, com el d'abscissa maxima, q, són negres. Doneu un algorisme per trobar un camí poligonal x-monoton 1r de p a q tal que (a) els vertexs de 1r siguin elements de BU N, (b) tots els punts de B siguin al camí o per sobre d'ell, (c) tots els punts de N siguin al camí o per sota d'ell, i (d) 7r sigui el camí més curt d'entre tots els qui compleixen aquestes propietats. Tracteu d'aconseguir O(nlogn). [Indicació: penseu primer els casos amb IBI petit.] 10 CONSTRUCCIONS DIVERSES Problema 39.- Doneu un algorisme o(n2) per trabar, donats n punts diferents del pla, la recta més vertical d'entre les que determinen. Doneu també una fita inferior per al problema. Problema 40.- Trobeu un algorisme O(n) que permeti, donats n punts del pla i un altre, q, decidir si q és fara, dins o a la vara de l'envolupant convexa dels altres. Problema 41.- Demostreu que el problema d'unicitat de nombres reals-donats x1, ... , Xn E R decidir si tots són diferents o nerté complexitat O(n logn) (via Ben-Or). Problema 42.- Sigui L un conjunt de n rectes del pla. Trobeu un algorisme O(nlogn) per calcular el rectangle mínim de costats paraHels als eixos que conté tots els vertexs de l'arranjament A(L) (Figura 13). Figura 13: Rectangle isotetic mínim que conté els vertexs d'un arranjament. Problema 43.- Una quadrisecció d'un conjunt de punts P és un parell de rectes tal que cadascun dels quatre angles oberts que determinen contingui com a maxim f n/ 41 punts. Demostreu que tot conjunt finit admet alguna quadrisecció i doneu un algorisme per trabar-ne una. Problema 44.- Sigui S un conjunt den segments disjunts del pla. Direm que un segment de S és separable en la direcció (1, O) si es pot traslladar horitzontalment (paraHel a sí mateix) cap al +oo de la direcció l'eix x sense coHissionar amb cap dels altres segments. Demostreu que sempre existeix almenys un element de S separable en la direcció (1, O) 11 i dedufo-ne un algorisme per obtenir una ordenació dels elements de S que ens permeti separar-los un rera un altre. Problema 45.- Trobeu un algorisme per decidir, donats n segments verticals s1, ... , sn, si existeix alguna recta transversal a tots (i en cas afirmatiu trobar-ne una). Problema 46.- La metrica L00 es defineix al pla per d((a, b), (e, d)) = max(la -el, Jb - di). a) Descriviu la figura geometrica que és un cercle amb aquesta metrica (és a dir, el lloc de punts a distanciar d'un centre p), i descriviu també la figura geometrica que és la mediatriu entre dos punts pi q, distingint casos segons la seva posició (és adir, el lloc de punts a igual distancia de p que de q). b) Demostreu que la regió de Voronoi d'un punt d'un conjunt amb la metrica L00 és una regió connexa, i caracteritzeu els punts que tenen regió de Voronoi no fitada. Problema 47.- Una recta vertical deixa a !'esquerra n punts blaus i a la dreta n punts vermells, sense que la unió contingui tres punts alineats. Demostreu que és possible em parellar els punts blaus amb els vermells de forma que els segments determinats no es tallin, i doneu un algorisme per construir tal emparellament (Figura 14). o o o o o ! • • oj i• • ! • !• o ¡ • Figura 14: Dos conjunts de punts (esquerra) i un emparellament sense talls (dreta). Problema 48.- El Diagrama de Voronoi llunya d'un conjunt S ={Pi, ... , Pn} de llocs del pla és la descomposició del pla en regions V ¡(Pi), de forma que tots els punts de V ¡(Pi) tenen Pi com a lloc més llunya, és a dir, Q E V ¡(Pi) si, i només si, d(Q, Pj) :S d(Q, Pi), Vj. Demostreu-ne les propietats següents. a) V ¡(Pi) =/= 0 si, i només si, Pi és un vertex de conv(S). b) V ¡ (Pi) és una regió poligonal convexa. c) Les regions V ¡(Pi) no buides són no-fitades. Que se'n dedueix per a 1'1-esquelet del Diagrama? 12 Problema 49.- Donats n segments del pla, possiblement no disjunts, idos punts pi q, trobeu un algorisme per decidir si existeix un punt del plaque veu pi q, és a dir, un punt x tal que els segments xp i xq no tallen cap dels n segments donats (Figura 15). Figura 15: Els punts p i r són simultaniament visibles des de x, pero p i q no són si multaniament visibles des de cap punt. Problema 50.- Donat un conjunt S = {Pi, ... , Pn} de punts del pla en posició general, doneu un algorisme per decidir si S admet una simetria axial. Tracteu d'assolir la millor eficiencia possible. Problema 51.- Siguin Vi B dos conjunt de punts del pla, anomenats vermells i blaus respectivament i amb cardinals nv i nb. Posarem n = nv + nb. Trobeu algorismes tan eficients com pogueu per (a) decidir si existeix un cercle que deixa els vermells a !'interior i els blaus a !'exterior; (b) trobar un semipla que contingui tots els vermells i el mínim nombre possible de blaus. Problema 52.- Es diu que un punt del pla p = (a, b) domina un altre punt q = (e, d) quan a > e i b > d. Donat un conjunt de n punts S, anomenem punts maximals de S els elements de S que no són dominats per cap punt de S. a) Doneu un algorisme o(n2) per trobar els elements maximals de S. b) Demostreu que el problema de l'apartat anterior té complexitat f!(n log n). [Indi cació: podeu relacionar el problema d'unicitat d'enters amb el nombre de punts maximals de S] Problema 53.- Siguin Di, ... , Dn clises disjunts, en general de radi diferent. a) Descriviu la forma geometrica de l'envolupant C = CH(D1 U··· U Dn). Doneu un exemple de configuració en que un dels discos contribueixi amb un nombre lineal de porcions de la frontera de C, i demostreu que malgrat aixo la complexitat de la 13 frontera mai ultrapassa 2n -2. [Indicació: podeu pensar en la contribució del clise més petit i fer una inducció acuradament] b) Doneu un algorisme per construir C. Problema 54.- Siguin B un conjunt de punts bons i D un conjunt de punts dolents en el pla, amb IBI + JDI = n. Es diu que un punt p del pla és acceptable quan compleix les condicions següents: (a) p és més a prop de cadascun dels punts bons que ho és l'origen; (b) p és més lluny de cadascun dels punts dolents que ho és l'origen. Trobeu un algorisme per construir el conjunt format pels punts acceptables [Indicació: podeu construir per separat el conjunt de punts que compleixen (a) i el conjunt de punts que compleixen (b), i després intersecar-los. També hi ha maneres de fer-ho tot de cop.] Problema 55.- Sigui S un conjunt den punts (sites) del pla. Per a cada punt del pla considerem les seves distancies als sites, ordenades de menor a major, i descomponem el pla en regions formades pels punts tals que l'ordre de les distancies és el mateix: quin és el maxim nombre possible de ceHules bidimensionals que es poden obtenir? Problema 56.- Sigui S ={Pi, .. •Pn} un conjunt den punts (sites) al pla. Suposem que per a cert punt x del pla el site més proper és Pi, el segon és P2 i el tercer es p3. a) Demostreu que Pi i p2 són ve:ins Delaunay. b) Demostreu que p3 és veí Voronoi d'almenys un site entre Pi i p2, pero no necessariament de tots dos. Problema 57.- El Diagrama de Voronoi de segon ordre d'un conjunt de punts ("sites") S = {Pi, ... ,Pn} és la descomposició del pla en regions determinades pel parell de punts de S més propers: a) Demostreu que les regions Vj,k no buides son regions poligonals convexes. b) Caracteritzeu les parelles de punts Pj, Pk, tals que Vj,k és no fitada. e) En la doble Figura 16 es veuen cinc sites i les deu mediatrius que defineixen. Dibuixeu-hi en la part superior el Diagrama de Voronoi d'aquests sites, i en la part inferior el seu Diagrama de Voronoi de segon ordre ( descomposicions dins del re quadres). d) Doneu un algorisme per calcular el Diagrama de Voronoi de segon ordre d'un conjunt de punts. [Indicació: inspireu-vos en la realització dels dibuixos de l'apartat anterior.] 14 AD AB CD AD BE AE AE CE AE/ AE CE CE CD r / DE ---------------- AC BD BE AD CE ¿ 1// DE AC �= BD AD Figura 16: Deu sites i llurs mediatrius. 15 Problema 58.- Sigui T un conjunt de n triangles dos a dos disjunts al pla. Descriviu un algorisme que permeti de trabar un conjunt de n - 1 segments que tinguin les propietats següents: •cada segment connecta un triangle amb un altre; •els interiors dels segments no tallen cap triangle; •els triangles i segments formen plegats un conjunt connex. 16 ESTRUCTURES DE DADES I PREPROCESSAMENT Problema 59.- *ed Trobeu un algorisme per calcular l'area de la reunió den rectangles isotetics. Podeu suposar que no hi ha dos costats alineats (Figura 17). Figura 17: Sis rectangles isotetics ( esquerra) i llur unió ( dreta). Problema 60.- Preµruce881fü u11 eunjunt S den punts del pla de tal forma que posteri orment sigui possible saber per a cada recta no vertical que ens donin quants punts de S té per sobre, en temps O(logn). Problema 61.- *ed Siguin S1 un conjunt de n segments disjunts horitzontals i S2 un conjunt de m segments disjunts verticals. Trobeu un algorisme O((n+m) log(n+m)) per comptar el nombre d'interseccions a S1 U S2. Problema 62.- Preprocesseu un conjunt S de n punts del pla de tal forma que poste riorment sigui possible saber per a cada punt q del pla que ens donin el maxim radi deis discos amb centre q sense punts de S a !'interior, en temps O(logn). Problema 63.- Sigui S un conjunt de n punts al pla. Volem processar el conjunt i emmagatzemar una estructura de dades de forma que poguem posteriorment dir en temps o( n), per a qualsevol recta r que ens donin, quants punts de S hi ha per sobre de r i quants per sota. Expliqueu com fer-ho i especifiqueu el temps de preprocessament, el de resposta i la memoria requerida per emmagatzemar }'estructura. 17 ESPAI TRIDIMENSIONAL Problema 64.- Sigui P un politop de JR3 amb n vertexs. Doneu un algorisme per trobar el segment vertical més llarg que s'hi pot inscriure. Problema 65.- Establiu un algorisme per decidir, donats un un políedre P de JR3 amb n vertexs i un punt q, si q és a !'exterior, sobre la vora o a !'interior de P. En el cas que P sigui convex, descriviu un preprocessament per obtenir una estructura que permeti resoldre el problema en temps logarítmic. Problema 66.- Siguin P un politop de JR3 amb n vertexs i C una de les seves cares. Doneu un algorisme per decidir si la posició de P seria estable en posar-lo sobre un pla horitzontal amb cara de contacte C. Problema 67.- Dissenyeu un algorisme per trobar, donats un un politop P de JR3 amb n vertexs i un punt exterior q, el contorn aparent de P tal com es veu des de q (Figura 18). q Figura 18: El contorn aparent C d'un cos Q, vist des de q, és el conjunt de punts de contacte de les tangents a Q des de q. 18