{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"institution":[{"id":[{"id":"https:\/\/ror.org\/03mb6wj31","id-type":"ROR","asserted-by":"publisher"},{"id":"https:\/\/www.isni.org\/000000041937028X","id-type":"ISNI","asserted-by":"publisher"},{"id":"https:\/\/www.wikidata.org\/entity\/Q1640731","id-type":"wikidata","asserted-by":"publisher"}],"name":"Universitat Polit\u00e8cnica de Catalunya","acronym":["UPC"]}],"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T05:08:03Z","timestamp":1770527283565,"version":"3.49.0"},"reference-count":0,"publisher":"Universitat Polit\u00e8cnica de Catalunya","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Esta tesis se divide en dos partes. La primera parte contiene el estudio de tres pesos o profundidades, asociados a conjuntos finitos de puntos en el plano: el peso definido por las capas convexas, convex depth (introducido por Hubert (72) y Barnett (76)), la separabilidad lineal, tambi\u00e9n conocido por location, halfspace o Tukey depth (Tukey 75)  y el peso Delaunay (Green 81). De la noci\u00f3n de peso, se obtiene una estratificaci\u00f3n de los conjuntos de puntos en el plano en capas y una partici\u00f3n del plano en regiones o niveles, cuyas fronteras son conocidas por depth contours. Se definen los conceptos de capa y nivel en los tres pesos se\u00f1alados y se estudian sus propiedades y complejidades. Chazelle obtuvo m\u00e9todos para hallar en tiempo \u00f3ptimo las capas convexas, que coinciden con las fronteras de los niveles convexos. En esta tesis, para los pesos de separabilidad lineal y Delaunay, se proporcionan algoritmos de obtenci\u00f3n, tanto de capas como de niveles, y de c\u00e1lculo del peso de un punto nuevo que se incorpore a la nube. De forma independiente, han sido obtenidos para el peso de la separabilidad lineal los algoritmos de construcci\u00f3n de los niveles, location depth contours, y el de c\u00e1lculo del peso de un punto nuevo, por Miller et al. (01).&lt;br\/&gt;  Para los tres pesos mencionados, se analizan \u00e1rboles generadores, poligonizaciones o triangulaciones, con peso m\u00ednimo, donde el peso se ha considerado como la suma de los pesos de las aristas de dichas estructuras. Se obtienen propiedades generales entorno a la caracterizaci\u00f3n de tales estructuras y algoritmos de obtenci\u00f3n para alguna de ellas.&lt;br\/&gt;  Se definen dos pesos relacionados con la separabilidad mediante cu\u00f1as: el peso seg\u00fan dominaci\u00f3n isot\u00e9tica y  la separabilidad &amp;#61537;. En ambos, se dan algoritmos para el c\u00e1lculo de los pesos de los puntos de un conjunto dado. La separabilidad &amp;#61537; est\u00e1 estrechamente relacionada con la enumeraci\u00f3n eficiente de (&amp;#61537;,k)-sets. Se realiza un estudio combinatorio del conjunto de (&amp;#61537;,k)-sets para nubes de puntos en el plano y se describen algoritmos de construcci\u00f3n de todos los (&amp;#61537;,k)-sets en cada uno de los cuatro casos posibles, seg\u00fan sean, &amp;#61537; o k, fijos o variables.&lt;br\/&gt;  En la segunda parte, se tratan diversos problemas de transversalidad. Se obtienen resultados acerca de la caracterizaci\u00f3n de las permutaciones realizables, tanto como pol\u00edgonos simples, como convexos, sobre arreglos de rectas.&lt;br\/&gt; Para colecciones de segmentos en el plano, se definen cu\u00f1a y c\u00edrculo transversales separadores. Se realiza un an\u00e1lisis del orden de estos elementos transversales separadores y se obtienen diversos algoritmos de decisi\u00f3n de existencia de los mismos  y construcci\u00f3n de todos ellos. Para colecciones de c\u00edrculos, tambi\u00e9n se define el c\u00edrculo transversal separador y se obtiene un algoritmo de existencia y construcci\u00f3n de dichos c\u00edrculos para c\u00edrculos con el mismo radio.<\/jats:p>\n                <jats:p>This thesis can be divided into two parts. The first part contains the study of three weights or depths associated to finite point sets in the plane: the convex depth convex hull peeling depth (introduced by Hubert (72) and Barnett (76)), the location depth (also known by halfspace or Tukey depth (Tukey (75)), and the Delaunay depth (Green (81)).&lt;br\/&gt;From any notion of depth, a stratification of the point sets of the plane into layers and a partition of the plane into regions or levels are obtained. The boundaries of the levels are known by depth contours. We define the concepts of layers and levels for all three depths and we study their properties and their complexities. Chazelle obtained methods to find the layers, which are the boundaries of the convex levels, with an optimal time algorithm. We present the algorithms for constructing the layers and levels, in location and Delaunay depths. Also, for both depths, we show algorithms to calculate the depth of a new point joining the cloud. In an independent way, the algorithms to obtain the levels (location depth contours) and to calculate the location depth of a new point, are obtained by Miller et al. (01).&lt;br\/&gt;For each one of the three mentioned depths, we study the geometric structures (spanning trees, polygonizations and triangulations) with minimum weight, where this weight has been considered as t-weight (the addition of the weight of their edges). We obtain general properties about the characterization of such structures and some algorithms to obtain them. We define two depths related with the separability by wedges: the isothetic-domination and the &amp;#61537;-separability which generalizes the location depth. We develop the algorithms in order to obtain the depths of all points of a given set in both cases. The &amp;#61537;-separability (in particular the location depth) is closely related with the efficient enumeration of the (&amp;#61537;,k)-sets. We make a combinatorial study of the (&amp;#61537;,k)-sets for point sets in the plane. We give lower and upper bounds for the maximum number of the (&amp;#61537;,k)-sets and we give algorithms for constructing all them, in each one of the four cases according to the case where &amp;#61537; or k are fixed or variable.&lt;br\/&gt;In the second part, we consider some transversality problems. We obtain results about the characterization of the realizable permutations both as simple and as convex polygons, over arrangements of lines. We also study some transversality problems with wedges and circles. We have defined the separating transversal wedge and the separating transversal circle for sets of segments. We analyze the size of the set of the transversal elements. Furthermore, we obtain some decision algorithms on the existence and construction of all of them. Finally, we define also the separating transversal circle for sets of circles and we obtain an algorithm for sets of circles with the same radius.<\/jats:p>","DOI":"10.5821\/dissertation-2117-94336","type":"dissertation","created":{"date-parts":[[2023,10,9]],"date-time":"2023-10-09T07:35:17Z","timestamp":1696836917000},"approved":{"date-parts":[[2004,7,16]]},"source":"Crossref","is-referenced-by-count":0,"title":["Problemas Geom\u00e9tricos en Morfolog\u00eda Computacional"],"prefix":"10.5821","author":[{"sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Merc\u00e8","family":"Claverol Aguas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"3865","container-title":[],"original-title":[],"deposited":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T06:32:49Z","timestamp":1770445969000},"score":1,"resource":{"primary":{"URL":"https:\/\/hdl.handle.net\/2117\/94336"}},"subtitle":[],"editor":[{"given":"Manuel","family":"Abellanas Oar","sequence":"first","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Fernando Alfredo","family":"Hurtado D\u00edaz","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":0,"URL":"https:\/\/doi.org\/10.5821\/dissertation-2117-94336","relation":{},"subject":[]}}