{"id":28,"date":"2022-05-17T14:18:40","date_gmt":"2022-05-17T14:18:40","guid":{"rendered":"https:\/\/dccg.upc.edu\/topping\/?page_id=28"},"modified":"2025-05-16T10:39:59","modified_gmt":"2025-05-16T10:39:59","slug":"topping-seminar","status":"publish","type":"page","link":"https:\/\/dccg.upc.edu\/topping\/topping-seminar\/","title":{"rendered":"TOPPING Seminar"},"content":{"rendered":"\n<h4 class=\"wp-block-heading has-normal-font-size\">Upcoming seminars<\/h4>\n\n\n\n<hr class=\"wp-block-separator has-css-opacity is-style-dots\"\/>\n\n\n\n<h4 class=\"wp-block-heading has-normal-font-size\">Previous seminars<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Friday, September 20, 2024, 12:00-13:00<br><strong>Title<\/strong>: Polycubes with small perimeter defect<br><strong>Speaker<\/strong>: Gill Barequet (Technion &#8212; Israel Inst. of Technology)<br><strong>Abstract<\/strong>:\u00a0Polycubes are connected sets of cells on the d-dimensional cubical lattice, where connectivity is through (d-1)-dimensional facets. The perimeter of a polycube C is the number of empty cells neighboring the cells of C. In this talk, I will explore methods for setting formulae for the number of polycubes of size n whose perimeter deviates by a fixed constant from the maximum possible perimeter.<\/li>\n\n\n\n<li>Thursday, July 10, 2024, 16:00-17:00<br><strong>Title<\/strong>: Construcci\u00f3n del ciclo sim\u00e9trico de longitud 5, usando la construcci\u00f3n de Haj\u00f3s a trav\u00e9s de un algoritmo gen\u00e9tico<br><strong>Speaker<\/strong>: Juan Carlos Garc\u00eda Altamirano (Universidad Aut\u00f3noma Metropolitana &#8211; Cuajimalpa, Mexico)<br><strong>Abstract<\/strong>:\u00a0Una coloraci\u00f3n de v\u00e9rtices de un digrafo es ac\u00edclica si no hay ciclos dirigidos monocrom\u00e1ticos. El n\u00famero dicrom\u00e1tico de un digrafo D es el n\u00famero m\u00ednimo de colores de una coloraci\u00f3n ac\u00edclica de D, denotado por dc(D). Un d\u00edgrafo D es r-cr\u00edtico si dc(D) = r y dc(H) &lt; r para cualquier subdigrafo H de D. En 2020, Bang-Jensen et al., extendieron la conocida construcci\u00f3n de Haj\u00f3s de grafos para digrafos y demostraron que: a partir de copias del digrafo sim\u00e9trico completo con r v\u00e9rtices, D(K_r), se puede construir cualquier digrafo r-cr\u00edtico mediante uniones dirigidas de Haj\u00f3s e identificaciones de v\u00e9rtices no adyacentes. Sin embargo, a los autores les apen\u00f3 mucho no poder construir, ni siquiera, al ciclo sim\u00e9trico D(C_5) a partir de copias de D(K_3), y lo dejaron como problema abierto. En este trabajo resolvemos ese problema adaptando un algoritmo gen\u00e9tico mediante la introducci\u00f3n de operadores innovadores de recombinaci\u00f3n y mutaci\u00f3n de la teor\u00eda de grafos. Dicho algoritmo obtuvo una sucesi\u00f3n de operaciones de Haj\u00f3s que atraves\u00f3 m\u00e1s de 5000 generaciones. En esta charla presentamos la sucesi\u00f3n reducida de 16 operaciones de Haj\u00f3s para construir el ciclo sim\u00e9trico de orden 5 y c\u00f3mo generalizar esta sucesi\u00f3n para obtener cualquier ciclo sim\u00e9trico de longitud impar a partir de copias de D(K_3).<\/li>\n\n\n\n<li>Thursday, May 30, 2024, 15:00-16:00<br><strong>Title<\/strong>: Reconstructing a pseudotree from the distance matrix of its boundary<br><strong>Speaker<\/strong>: I\u00f1aki Pelayo (UPC)<br><strong>Abstract<\/strong>: A vertex v of a connected graph G is said to be a boundary vertex of G if for some other vertex u of G, no neighbor of v is further away from u than v. The boundary \u2202(G) of G is the set of all of its boundary vertices. The distance matrix DG of a graph G = ([n], E) is the square matrix of order n, such that for every i, j \u2208 [n], [D\u02c6G]ij = dG(i, j). The boundary distance matrix D\u02c6G of G is the square matrix of order \u03ba, being \u03ba the order of \u2202(G), such that for every i, j \u2208 \u2202(G), [D\u02c6G]ij = dG(i, j). Given a square matrix B of order n, we show under which conditions B is the distance matrix DT of a tree T. Given a square matrix B\u02c6 of order \u03ba, we prove under which conditions B\u02c6 is the distance matrix D\u02c6T of the set of leaves of a tree T, which is precisely its boundary. We show that if G is either a tree or a unicyclic graph, then G is uniquely determined by the distance matrix D\u02c6G of the boundary of G and we also conjecture that this statement holds for every connected graph G, whenever both the order n and the boundary (and thus also its distance matrix) of G are prefixed.<\/li>\n\n\n\n<li>Thursday, April 25, 2024, 15:00-16:00<br><strong>Title<\/strong>: Isolation in graphs.<br><strong>Speaker<\/strong>: Merc\u00e8 Mora (UPC)<br><strong>Abstract<\/strong>: The concept of isolation in graphs arises when the condition of dominating set is relaxed. Let D be a set of vertices of a graph G and denote by N[D] the set of vertices in D or with a neighbour in D. We say that the set D is dominating in G if V(G)=N[D], where V(G) is the set of vertices of G. Equivalently, D is dominating if V(G)-N[D] is the empty set. The set D is isolating in G if we allow it to have isolated vertices in V(G)-N[D]. Concretely, D is isolating if the subgraph of G induced by the set V(G)-N[D] has no edge. In general, if F is a family of graphs, we say that D is F-isolating if the subgraph of G induced by the set V(G)-N[D] has no member of F as a subgraph. Hence, domination and isolation correspond to F-isolation for the families F={K_1} and F={K_2}, respectively. In this work, we study isolation and F-isolation, when F is the family of stars of a fixed order greater than 2. We establish bounds on the minimum cardinality of a F-isolating set and characterize graphs attaining the given bounds for some families of graphs.<\/li>\n\n\n\n<li>Wednesday, March 6, 2024 15:00-15:30<br><strong>Title<\/strong>: The Complexity of the Lower Envelope of Collections of Various Geometric Shapes<br><strong>Speaker<\/strong>: Carlos Seara (UPC)<br><strong>Abstract<\/strong>: We study the problem of determining the complexity of the lower envelope of a collection of n geometric objects. For collections of rays; unit length line segments; and collections of unit squares to which we apply at most two transformations from translation, rotation, and scaling, we prove a complexity of Theta(n). If all three transformations are applied to unit squares, then we show the complexity becomes Theta(n alpha(n)), where alpha(n) is the slowly growing inverse of Ackermann&#8217;s function. Joint work with Carlos Alegr\u00eda, Anna Br\u00f6tzner, and Christiane Schmidt. <\/li>\n\n\n\n<li>Wednesday, March 6, 2024 15:30-16:00<br>Title: Sibson&#8217;s formula for higher order Voronoi diagrams<br>Speaker: Andrea de las Heras (UPC)<br>Abstract: Let S be a set of n points in general position in R^d. The order-k Voronoi diagram of S, V_k(S), is a subdivision of R^d into cells whose points have the same k nearest points of S. Sibson, in his seminal paper from 1980, &#8220;A vector identity for the Dirichlet tessellation&#8221;, gives a formula to express a point Q of S as a convex combination of other points of S by using ratios of areas of the intersection of cells of V_2(S) and the cell of Q in V_1(S). The natural neighbour interpolation method is based on Sibson&#8217;s formula. We generalize his result to express Q as a convex combination of other points of S by using ratios of areas from Voronoi diagrams of any given order. Joint work with Merce Claverol and Clemens Huemer.<\/li>\n\n\n\n<li>Tuesday, January 23, 2024 15:00-16:30<br><strong>Title<\/strong>: Packing d-dimensional balls into a (d+1)-dimensional container<br><strong>Speaker<\/strong>: Sergio Cabello (University of Ljubljana and IMFM, Slovenia)<br><strong>Abstract<\/strong>: We consider the problems of finding in d+1 dimensions a minimum-volume axis-parallel box, a minimum-volume arbitrarily-oriented box and a minimum-volume convex body into which a given set of d-dimensional unit-radius balls can be packed under translations. We give a constant-factor approximation algorithm for each of these containers. We also show that for n such balls, a container of volume O(n^{1\u22121\/d}) is always sufficient and sometimes necessary. Joint work with Helmut Alt, Otfried Cheong, Ji-won Park and Nadja Seiferth.<\/li>\n\n\n\n<li>Thursday, November 30, 2023 15:00-16:00<br><strong>Title<\/strong>: Rectilinear convex hull of set of objects<br><strong>Speaker<\/strong>: Carlos Seara (UPC)<br><strong>Abstract<\/strong>: We study the problem of computing the rectilinear convex hull of a set of geometric objects. We first consider a set of n line segments. If the segments are not necessarily disjoint, we describe an algorithm that runs in optimal Theta(n log n) time and O(n alpha(n)) space, where \\alpha(n) is the extremely slowly growing inverse of Ackermann&#8217;s function. If instead the line segments form a simple polygonal chain, we describe an algorithm that improves the previous space complexity to Theta(n). We then extend the techniques used in these algorithms to a set of n circles, then the resulting algorithm runs in optimal Theta(n log n) time and Theta(n) space.<\/li>\n\n\n\n<li>Wednesday, May 3, 2023, 14:30-15:30<br><strong>Title<\/strong>: \u00a0Obstacle Avoidance<br><strong>Speaker<\/strong>: Subhash Suri (University of California, Santa Barbara)<br><strong>Abstract<\/strong>: Obstacle-avoiding paths are widely studied in computational geometry and graph theory as design tools in various applications such as motion planning in robotics and monitoring using sensor networks, among others. In this talk we describe recent progress on some obstacle-avoidance questions of the following form: what is the minimum number of obstacles we must remove to reach target point t from start point s, and what is the maximum number of obstacles we can remove while blocking all s-t paths. We also discuss these reachability and blocking questions for multiple s-t pairs and under some conditions design algorithms to find the shortest-length path realizable by the removal of at most k obstacles.<\/li>\n\n\n\n<li>Tuesday, April 26, 2022, 16:00-17:00<br><strong>Title<\/strong>: k-Transmitter Watchman Routes<br><strong>Speaker<\/strong>: Bengt J. Nilsson (Malm\u00f6 University)<br><strong>Abstract<\/strong>: We consider the watchman route problem for a <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/>-transmitter watchman: standing at point <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3bf85f1087e9fbed3a319341134ac1a2_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#112;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"10\" style=\"vertical-align: -4px;\"\/> in a polygon <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-650eb7688af6737ac325425b5c9a5982_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#80;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/>, the watchman can see  <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-524414600795a33163da0a8c5be7878c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#113;&#32;&#92;&#105;&#110;&#32;&#80;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"44\" style=\"vertical-align: -4px;\"\/> if <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-f226120d35126916a86681ddeb03d3f9_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#112;&#113;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"18\" style=\"vertical-align: -4px;\"\/> intersects <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-650eb7688af6737ac325425b5c9a5982_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#80;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> \u2019s boundary at most <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/> times\u2014<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-ac7da57d7f507262338bb5168feb3e06_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#113;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"8\" style=\"vertical-align: -4px;\"\/> is <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/>-visible to <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3bf85f1087e9fbed3a319341134ac1a2_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#112;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"10\" style=\"vertical-align: -4px;\"\/>. Travelling along the <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/>-transmitter watchman route, either all points in <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-650eb7688af6737ac325425b5c9a5982_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#80;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> or a discrete set of points <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-f7ea6db2e8921efb39d92bf1d919259e_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#83;&#32;&#92;&#115;&#117;&#98;&#115;&#101;&#116;&#32;&#80;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"50\" style=\"vertical-align: -1px;\"\/> must be <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/>-visible to the watchman. We aim to minimize the length of the <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/>-transmitter watchman route. We show that even in simple polygons the <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/>-transmitter watchman route problem for <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-f7ea6db2e8921efb39d92bf1d919259e_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#83;&#32;&#92;&#115;&#117;&#98;&#115;&#101;&#116;&#32;&#80;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"50\" style=\"vertical-align: -1px;\"\/> is NP-complete\u2014both if a given starting point for the route is given and if no such point exists. Moreover, we present a polylogarithmic approximation for the <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/>-transmitter watchman route problem for a given starting point and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-f7ea6db2e8921efb39d92bf1d919259e_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#83;&#32;&#92;&#115;&#117;&#98;&#115;&#101;&#116;&#32;&#80;\" title=\"Rendered by QuickLaTeX.com\" height=\"13\" width=\"50\" style=\"vertical-align: -1px;\"\/> with approximation ratio <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-159e987799239a4d5129566e10f3b95e_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#79;&#40;&#92;&#108;&#111;&#103;&#95;&#50;&#123;&#40;&#124;&#83;&#124;&#32;&#92;&#99;&#100;&#111;&#116;&#32;&#110;&#41;&#125;&#94;&#50;&#92;&#108;&#111;&#103;&#123;&#92;&#108;&#111;&#103;&#123;&#40;&#124;&#83;&#124;&#32;&#92;&#99;&#100;&#111;&#116;&#32;&#110;&#41;&#125;&#125;&#94;&#50;&#92;&#108;&#111;&#103;&#123;&#124;&#83;&#124;&#125;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"22\" width=\"299\" style=\"vertical-align: -5px;\"\/> (with <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-e53f341ed9cfba6514b6a6015a02e010_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#108;&#118;&#101;&#114;&#116;&#32;&#80;&#92;&#114;&#118;&#101;&#114;&#116;&#32;&#61;&#32;&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"56\" style=\"vertical-align: -5px;\"\/>).<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-group\"><div class=\"wp-block-group__inner-container is-layout-flow wp-block-group-is-layout-flow\">\n<hr class=\"wp-block-separator has-css-opacity is-style-default\"\/>\n<\/div><\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Tuesday, March 22, 2022, 16:00-17:00<br><strong>Title<\/strong>: Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs<br><strong>Speaker<\/strong>: Javier Tejel (Universidad de Zaragoza)<br><strong>Abstract<\/strong>: Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). We introduce a special kind of simple drawings that we call generalized twisted drawings. A simple drawing is generalized twisted if there is a point <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-41136ed7463f7254f4e6df131f8be490_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#79;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> such that every ray emanating from <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-41136ed7463f7254f4e6df131f8be490_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#79;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> crosses every edge of the drawing at most once and there is a ray emanating from <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-41136ed7463f7254f4e6df131f8be490_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#79;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> which crosses every edge exactly once. Via this new class of simple drawings, we show that every simple drawing of the complete graph with <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-b170995d512c659d8668b4e42e1fef6b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"11\" style=\"vertical-align: 0px;\"\/> vertices contains <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-1bc6f058266e622413df5ee93f5c8e39_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#79;&#109;&#101;&#103;&#97;&#40;&#110;&#94;&#123;&#49;&#47;&#50;&#125;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"21\" width=\"58\" style=\"vertical-align: -5px;\"\/> pairwise disjoint edges and a plane path of length <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-b302825f8eb0de82650d2d42d65914e4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#79;&#109;&#101;&#103;&#97;&#40;&#92;&#102;&#114;&#97;&#99;&#123;&#92;&#108;&#111;&#103;&#32;&#110;&#125;&#123;&#92;&#108;&#111;&#103;&#123;&#92;&#108;&#111;&#103;&#32;&#110;&#125;&#125;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"26\" width=\"78\" style=\"vertical-align: -9px;\"\/>. Both results improve over previously known best lower bounds.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-9d6595d7 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:100%\">\n<hr class=\"wp-block-separator has-css-opacity is-style-default\"\/>\n<\/div>\n<\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Thursday, March 10, 2022, 16:00-16:45. Special seminar session with two short talks.<br><br>&#8212;&#8211; Talk 1 &#8212;&#8211;<br><strong>Title<\/strong>: Spanning ratio of shortest paths in weighted square tessellations<br><strong>Speaker<\/strong>: Guillermo Esteban (Universidad de Alcal\u00e1 and Carleton University)<br><strong>Abstract<\/strong>: Continuous 2-dimensional space is often discretized by considering a grid of weighted square cells. In this work we study how well a weighted tessellation approximates the space, with respect to shortest paths. In particular, we consider a shortest path <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-1772e96294c3767ce3aa1005ce23473b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#83;&#80;&#95;&#119;&#40;&#115;&#44;&#116;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"69\" style=\"vertical-align: -5px;\"\/> which is a shortest path from s to t in the continuous weighted 2D-space, and a shortest grid path <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3a1b2ea8b153afeef64fea2214961764_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#83;&#71;&#80;&#95;&#119;&#40;&#115;&#44;&#116;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"83\" style=\"vertical-align: -5px;\"\/>, which is a shortest path in the tessellated weighted 2D-space. Our main result is that the ratio <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-d55f5a2a9bb16b479ca93c4bf1a6b3d6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#102;&#114;&#97;&#99;&#123;&#83;&#71;&#80;&#95;&#119;&#40;&#115;&#44;&#116;&#41;&#125;&#123;&#83;&#80;&#95;&#119;&#40;&#115;&#44;&#116;&#41;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"29\" width=\"65\" style=\"vertical-align: -10px;\"\/> is at most <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-542753b77cebb7aee07e091d4217c809_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#102;&#114;&#97;&#99;&#123;&#50;&#125;&#123;&#92;&#115;&#113;&#114;&#116;&#123;&#50;&#43;&#92;&#115;&#113;&#114;&#116;&#123;&#50;&#125;&#125;&#125;&#32;&#92;&#97;&#112;&#112;&#114;&#111;&#120;&#32;&#49;&#46;&#48;&#56;\" title=\"Rendered by QuickLaTeX.com\" height=\"31\" width=\"108\" style=\"vertical-align: -15px;\"\/>, irrespective of the weight assignment.<br><br>&#8212;&#8211; Talk 2 &#8212;&#8211;<br><strong>Title<\/strong>: Properties for Voronoi Diagrams of Arbitrary Order on the Sphere<br><strong>Speaker<\/strong>: Andrea de Las Heras (UPC)<br><strong>Abstract<\/strong>: For a given set of points <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-2b60fc262803f27ba3717d8ec4eb656d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#85;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"13\" style=\"vertical-align: 0px;\"\/> on a sphere <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-520cb534cd5b6bed768a61515b57cb7e_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#83;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/>, the order <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/> spherical Voronoi diagram <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-0af0eb3e7e7e68595db977b21876d8c5_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#83;&#86;&#95;&#107;&#40;&#85;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"57\" style=\"vertical-align: -5px;\"\/> decomposes the surface of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-520cb534cd5b6bed768a61515b57cb7e_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#83;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/> into regions whose points have the same <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/> nearest points of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-2b60fc262803f27ba3717d8ec4eb656d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#85;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"13\" style=\"vertical-align: 0px;\"\/>. We study properties for <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-0af0eb3e7e7e68595db977b21876d8c5_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#83;&#86;&#95;&#107;&#40;&#85;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"57\" style=\"vertical-align: -5px;\"\/>, using different tools: the geometry of the sphere, a labeling for the edges of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-0af0eb3e7e7e68595db977b21876d8c5_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#83;&#86;&#95;&#107;&#40;&#85;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"57\" style=\"vertical-align: -5px;\"\/>, and the inversion transformation. Hyeon-Suk Na, Chung-Nim Lee and Otfried Cheong (Comput. Geom., 2002) applied inversions to construct <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-38851e9236b4879b86f766685702bcba_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#83;&#86;&#95;&#49;&#40;&#85;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"57\" style=\"vertical-align: -5px;\"\/>. We generalize their construction for spherical Voronoi diagrams from order 1 to any order <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/>. We use that construction to prove formulas for the numbers of vertices, edges, and faces in <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-0af0eb3e7e7e68595db977b21876d8c5_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#83;&#86;&#95;&#107;&#40;&#85;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"57\" style=\"vertical-align: -5px;\"\/>. Among the properties of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-0af0eb3e7e7e68595db977b21876d8c5_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#83;&#86;&#95;&#107;&#40;&#85;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"57\" style=\"vertical-align: -5px;\"\/>, we also show that <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-0af0eb3e7e7e68595db977b21876d8c5_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#83;&#86;&#95;&#107;&#40;&#85;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"57\" style=\"vertical-align: -5px;\"\/> has a small orientable cycle double cover.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-9d6595d7 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:100%\">\n<hr class=\"wp-block-separator has-css-opacity\"\/>\n<\/div>\n<\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Tuesday, December 21, 2021, 16:00-17:00<br><strong>Title<\/strong>: The edge labeling of higher order Voronoi diagrams<br><strong>Speaker<\/strong>: Alejandra Mart\u00ednez (Universidad de Alcal\u00e1)<br><strong>Abstract<\/strong>: We present an edge labeling of order-<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/> Voronoi diagrams, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-0b563482f1a7e6d93dd7bb765912f8ae_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#86;&#95;&#107;&#40;&#83;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"43\" style=\"vertical-align: -5px;\"\/>, of point sets <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-28a59cf043442133c895454f02b9af0d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#109;&#97;&#116;&#104;&#99;&#97;&#108;&#123;&#83;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/> in the plane, and study properties of the regions defined by them. Among them, we show that <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-0b563482f1a7e6d93dd7bb765912f8ae_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#86;&#95;&#107;&#40;&#83;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"43\" style=\"vertical-align: -5px;\"\/> has a small orientable cycle and path double cover, and we identify configurations that cannot appear in <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-0b563482f1a7e6d93dd7bb765912f8ae_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#86;&#95;&#107;&#40;&#83;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"43\" style=\"vertical-align: -5px;\"\/> for small values of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/>.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-9d6595d7 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:100%\">\n<hr class=\"wp-block-separator has-css-opacity\"\/>\n<\/div>\n<\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Tuesday, November 23, 2021, 16:00-17:00<br><strong>Title<\/strong>: Illuminating a line segment or a line by alpha-floodlights<br><strong>Speaker<\/strong>: Leonidas Palios (University of Ioannina, Greece)<br><strong>Abstract<\/strong>: For a positive angle <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-8f0b6b1a01f8fcc2f95be0364c090397_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#97;&#108;&#112;&#104;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"11\" style=\"vertical-align: 0px;\"\/>, an <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-8f0b6b1a01f8fcc2f95be0364c090397_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#97;&#108;&#112;&#104;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"11\" style=\"vertical-align: 0px;\"\/>-floodlight is a floodlight in the plane with illumination cone angle equal to <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-8f0b6b1a01f8fcc2f95be0364c090397_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#97;&#108;&#112;&#104;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"11\" style=\"vertical-align: 0px;\"\/>. In this talk, we consider the problem in which we are given a set <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-28a59cf043442133c895454f02b9af0d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#109;&#97;&#116;&#104;&#99;&#97;&#108;&#123;&#83;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/> of planar regions with piece-wise linear boundary, a positive angle <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-8f0b6b1a01f8fcc2f95be0364c090397_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#97;&#108;&#112;&#104;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"11\" style=\"vertical-align: 0px;\"\/>, and a line segment or a line <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-66a9f474fc3c52efdfb0ba6a70199ee8_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#76;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/> in the plane, and we want to compute the locations and orientations of the minimum number of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-8f0b6b1a01f8fcc2f95be0364c090397_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#97;&#108;&#112;&#104;&#97;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"11\" style=\"vertical-align: 0px;\"\/>-floodlights positioned at points in <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-28a59cf043442133c895454f02b9af0d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#109;&#97;&#116;&#104;&#99;&#97;&#108;&#123;&#83;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/> which suffice to entirely illuminate <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-66a9f474fc3c52efdfb0ba6a70199ee8_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#76;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/>. We show that the problem can be solved in <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-499801ff71048f802e5d6109cbefb811_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#79;&#40;&#110;&#32;&#92;&#108;&#111;&#103;&#32;&#123;&#110;&#125;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"77\" style=\"vertical-align: -5px;\"\/> time and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-31c2cdca867987ac2a6e27b1434ae748_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#79;&#40;&#110;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"38\" style=\"vertical-align: -5px;\"\/> space, where <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-b170995d512c659d8668b4e42e1fef6b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"11\" style=\"vertical-align: 0px;\"\/> is the total number of vertices of the regions in the set <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-28a59cf043442133c895454f02b9af0d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#109;&#97;&#116;&#104;&#99;&#97;&#108;&#123;&#83;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/>.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-9d6595d7 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:100%\">\n<hr class=\"wp-block-separator has-css-opacity\"\/>\n<\/div>\n<\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Tuesday, October 26, 2021, 16:00-17:00<br><strong>Title<\/strong>: Terrain prickliness: theoretical grounds for high complexity viewsheds<br><strong>Speaker<\/strong>: Rodrigo Silveira (UPC)<br><strong>Abstract<\/strong>: An important task in terrain analysis is computing viewsheds. A viewshed is the union of all the parts of the terrain that are visible from a given viewpoint or set of viewpoints. The complexity of a viewshed can vary significantly depending on the terrain topography and the viewpoint position. In this work we study a new topographic attribute, the &#8220;prickliness&#8221;, that measures the number of local maxima in a terrain from all possible angles of view. We show that the prickliness effectively captures the potential of terrains to have high complexity viewsheds. We present near-optimal algorithms to compute it for TIN terrains, and efficient approximate algorithms for raster DEMs. We validate the usefulness of the prickliness attribute with experiments in a large set of real terrains.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-9d6595d7 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:100%\">\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n<\/div>\n<\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Thursday, July 1, 2021, 16:00-17:00<br><strong>Title<\/strong>: On the intersection graph of the disks with diameters the sides of a convex <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-b170995d512c659d8668b4e42e1fef6b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"11\" style=\"vertical-align: 0px;\"\/>-gon<br><strong>Speaker<\/strong>: Luis Hern\u00e1n Herrera Becerra (Universidad de Santiago de Chile, USACH)<br><strong>Abstract<\/strong>: Given a convex <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-b170995d512c659d8668b4e42e1fef6b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"11\" style=\"vertical-align: 0px;\"\/>-gon, we can draw n disks (called side disks) where each disk has a different side of the polygon as diameter and the midpoint of the side as its center. The intersection graph of such disks is the undirected graph with vertices the n disks and two disks are adjacent if and only if they have a point in common. Such a graph, introduced by Huemer and P\u00e9rez-Lantero in 2016, was proved to be planar and Hamiltonian. In this talk (i) we show further combinatorial properties of this graph. We prove that the treewidth is at most 3, by showing an <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-31c2cdca867987ac2a6e27b1434ae748_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#79;&#40;&#110;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"38\" style=\"vertical-align: -5px;\"\/>-time algorithm that builds a tree decomposition of width at most 3, given the polygon as input. This implies that we can construct the intersection graph of the side disks in <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-31c2cdca867987ac2a6e27b1434ae748_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#79;&#40;&#110;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"38\" style=\"vertical-align: -5px;\"\/> time. (ii) We further study the independence number of this graph, which is the maximum number of pairwise disjoint disks. The planarity condition implies that for every convex <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-b170995d512c659d8668b4e42e1fef6b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"11\" style=\"vertical-align: 0px;\"\/>-gon we can select at least <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-cc34a617f83d281fee7717f5f15f11f9_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#102;&#114;&#97;&#99;&#123;&#110;&#125;&#123;&#52;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"9\" style=\"vertical-align: -6px;\"\/> pairwise disjoint disks, and we prove that for every <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-ec74db968e027428a02164d1492b2849_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;&#92;&#103;&#101;&#113;&#51;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"43\" style=\"vertical-align: -3px;\"\/> there exist convex <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-b170995d512c659d8668b4e42e1fef6b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"11\" style=\"vertical-align: 0px;\"\/>-gons in which we cannot select more than this number. (iii) Finally, we show that our class of graphs includes all outerplanar Hamiltonian graphs except the cycle of length four, and that it is a proper subclass of the planar Hamiltonian graphs.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-9d6595d7 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\">\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n<\/div>\n<\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Thursday, May 27, 2021, 16:00-17:00<br><strong>Speaker<\/strong>: Ana Laura Trujillo (CINVESTAV, Mexico)<br><strong>Title<\/strong>: Laplacian spectrum of token graphs<br><strong>Abstract<\/strong>: Let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-30a79c32f18567063fe44716929e7ced_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#71;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> be a simple graph of order <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-68e2940245f6b908b8fb44957014be33_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;&#92;&#103;&#101;&#113;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"42\" style=\"vertical-align: -3px;\"\/>, and let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/> be an integer with <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3e13825abad0a3647a67d4584c1f42ff_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#49;&#32;&#92;&#103;&#101;&#113;&#32;&#107;&#32;&#92;&#103;&#101;&#113;&#32;&#110;&#45;&#49;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"105\" style=\"vertical-align: -3px;\"\/>. The <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/>-token graph <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-7c726c1c3884533034961ef808a753f3_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#70;&#95;&#107;&#40;&#71;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"47\" style=\"vertical-align: -5px;\"\/> of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-30a79c32f18567063fe44716929e7ced_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#71;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> is the graph whose vertices are all the <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/>-subsets of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-8e59260049a34635edb43878df5e8d0e_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#86;&#40;&#71;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"41\" style=\"vertical-align: -5px;\"\/>, where two of such <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/>-subsets are adjacent in <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-7c726c1c3884533034961ef808a753f3_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#70;&#95;&#107;&#40;&#71;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"47\" style=\"vertical-align: -5px;\"\/> if their symmetric difference is a pair of adjacent vertices of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-30a79c32f18567063fe44716929e7ced_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#71;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/>. Token graphs have been defined at least four times since 1988, and so far, several applications of token graphs to Physics and Coding Theory are known. In this talk we will see some properties of the Laplacian spectrum of token graphs. We will see that for any integers <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-14b463d0ecd5b350ced6cf1d6a12eef3_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#104;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"10\" style=\"vertical-align: 0px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/> with <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-7cf32460d0fba857211c400d74234e28_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#49;&#32;&#92;&#103;&#101;&#113;&#32;&#104;&#32;&#60;&#32;&#107;&#32;&#92;&#103;&#101;&#113;&#32;&#92;&#102;&#114;&#97;&#99;&#123;&#110;&#125;&#123;&#50;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"110\" style=\"vertical-align: -6px;\"\/>, the Laplacian spectrum of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-8ebf94379e7cbc5789879ce3d3134fcd_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#70;&#95;&#104;&#40;&#71;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"47\" style=\"vertical-align: -5px;\"\/> is contained in the Laplacian spectrum of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-7c726c1c3884533034961ef808a753f3_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#70;&#95;&#107;&#40;&#71;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"47\" style=\"vertical-align: -5px;\"\/>. Besides,\u00a0we provide three infinite families of graphs for which the algebraic connectivities of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-30a79c32f18567063fe44716929e7ced_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#71;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-7c726c1c3884533034961ef808a753f3_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#70;&#95;&#107;&#40;&#71;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"47\" style=\"vertical-align: -5px;\"\/> are equal, for any <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/> with <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3e13825abad0a3647a67d4584c1f42ff_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#49;&#32;&#92;&#103;&#101;&#113;&#32;&#107;&#32;&#92;&#103;&#101;&#113;&#32;&#110;&#45;&#49;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"105\" style=\"vertical-align: -3px;\"\/>. Finally,\u00a0we will show a relationship between the Laplacian spectrum of the <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/>-token graph of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-30a79c32f18567063fe44716929e7ced_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#71;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> and the <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/>-token graph of its complement <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-c3cffc220959d9c2278c504d24cc7857_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#111;&#118;&#101;&#114;&#108;&#105;&#110;&#101;&#123;&#71;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"14\" style=\"vertical-align: 0px;\"\/>.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-9d6595d7 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:100%\">\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n<\/div>\n<\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Thursday, May 6, 2021, 16:00-17:00<br><strong>Title<\/strong>: \u00a0Fragile Complexity of Adaptive Algorithms<br><strong>Speaker<\/strong>: Pilar Cano (Universit\u00e9 Libre de Bruxelles)<br><strong>Abstract<\/strong>:\u00a0 The fragile complexity of a comparison-based algorithm is <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-9367678df57519865075cc6d7d8ef0d0_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#102;&#40;&#110;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"35\" style=\"vertical-align: -5px;\"\/> if each input element participates in <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-258a70d8e74f341deb0d1376e40d0260_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#79;&#40;&#102;&#40;&#110;&#41;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"62\" style=\"vertical-align: -5px;\"\/> comparisons. In this work, we explore the fragile complexity of algorithms adaptive to various restrictions on the input, i.e., algorithms with a fragile complexity parameterized by a quantity other than the input size <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-b170995d512c659d8668b4e42e1fef6b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"11\" style=\"vertical-align: 0px;\"\/>. We show that searching for the predecessor in a sorted array has fragile complexity <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-546cbba81e2ac7ceaa7d757581414c07_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#84;&#104;&#101;&#116;&#97;&#40;&#92;&#108;&#111;&#103;&#123;&#107;&#125;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"62\" style=\"vertical-align: -5px;\"\/>, where <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/> is the rank of the query element, both in a randomized and a deterministic setting. For predecessor searches, we also show how to optimally reduce the amortized fragile complexity of the elements in the array. We also prove the following results: Selecting the <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-3422b6bb5c160593658b7c39425d9880_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/>-th smallest element has expected fragile complexity <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-0ea814826f3712223cdfade5dfddaf6c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#79;&#40;&#92;&#108;&#111;&#103;&#123;&#92;&#108;&#111;&#103;&#123;&#107;&#125;&#125;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"88\" style=\"vertical-align: -5px;\"\/> for the element selected. Deterministically finding the minimum element has fragile complexity <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-0a3f05beff7743121d344cbafcc045bd_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#84;&#104;&#101;&#116;&#97;&#40;&#92;&#108;&#111;&#103;&#123;&#40;&#73;&#110;&#118;&#41;&#125;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"95\" style=\"vertical-align: -5px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-c98e870888aa3fe024172576e8e9d17c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#84;&#104;&#101;&#116;&#97;&#40;&#92;&#108;&#111;&#103;&#123;&#40;&#82;&#117;&#110;&#115;&#41;&#125;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"109\" style=\"vertical-align: -5px;\"\/>, where Inv is the number of inversions in a sequence and Runs is the number of increasing runs in a sequence. Deterministically finding the median has fragile complexity <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-adbf91e2821f6956038c85f053698aa4_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#79;&#40;&#92;&#108;&#111;&#103;&#123;&#40;&#82;&#117;&#110;&#115;&#41;&#125;&#32;&#43;&#32;&#92;&#108;&#111;&#103;&#123;&#92;&#108;&#111;&#103;&#123;&#110;&#125;&#125;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"193\" style=\"vertical-align: -5px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-0a3f05beff7743121d344cbafcc045bd_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#84;&#104;&#101;&#116;&#97;&#40;&#92;&#108;&#111;&#103;&#123;&#40;&#73;&#110;&#118;&#41;&#125;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"95\" style=\"vertical-align: -5px;\"\/>. Deterministic sorting has fragile complexity <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-0a3f05beff7743121d344cbafcc045bd_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#84;&#104;&#101;&#116;&#97;&#40;&#92;&#108;&#111;&#103;&#123;&#40;&#73;&#110;&#118;&#41;&#125;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"95\" style=\"vertical-align: -5px;\"\/> but it has fragile complexity <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-7c53d518d02743398b6d9857588e5131_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#84;&#104;&#101;&#116;&#97;&#40;&#92;&#108;&#111;&#103;&#123;&#110;&#125;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"64\" style=\"vertical-align: -5px;\"\/> regardless of the number of runs.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-9d6595d7 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:100%\">\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n<\/div>\n<\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Thursday, April 29, 2021, 16:00-17:00<br><strong>Title<\/strong>: On Maximum-Sum Matchings of Points<br><strong>Speaker<\/strong>: Oscar Chac\u00f3n-Rivera (Universidad de Santiago de Chile)<br><strong>Abstract<\/strong>: Huemer et al. (Discrete Math., 2019) proved that for any two point sets <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-dae6bae3dcdac4629730754352c5e329_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#82;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-770fd1447ccf2fc229801b486b0d8f8a_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> with <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-cac71658ffaa9904774b3d4647e3077d_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#124;&#82;&#124;&#32;&#61;&#32;&#124;&#66;&#124;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"67\" style=\"vertical-align: -5px;\"\/>, the perfect matching that matches points of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-dae6bae3dcdac4629730754352c5e329_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#82;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> with points of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-770fd1447ccf2fc229801b486b0d8f8a_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#66;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/>, and maximizes the total squared Euclidean distance of the matched pairs, has the property that all the disks induced by the matching have a common point. In this work we study the perfect matching that maximizes the total Euclidean distance. First, we prove that this setting does not always ensure the common intersection property of the disks. Second, we extend the study for sets of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-7ca9d3b4ff5edce754df0706e9af8e9c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#50;&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"20\" style=\"vertical-align: 0px;\"\/> uncolored points. As the main result, we prove that in this case all disks of the matching do have a common point. Finally, we comment on pairwise intersection of ellipses induced by the matching.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-9d6595d7 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:100%\">\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n<\/div>\n<\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Thursday, March 25, 2021, 16:00-17:00<br><strong>Title<\/strong>: Algorithmic Geometry with Infinite Computation<br><strong>Speaker<\/strong>: Adri\u00e1n Tobar Nicolau (UPC)<br><strong>Abstract<\/strong>:\u00a0In this talk we present an algorithmic study of problems from computational geometry with countably infinite input, especially countable sets in <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-f9868b4451c5811a288f7fdd10be5558_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#82;&#125;&#94;&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"21\" style=\"vertical-align: 0px;\"\/>. To do so, we use the infinite time Blum-Shub-Smale (ITBSS) machine, which is capable of extending computations to infinite time. We present this framework, explained with several algorithms and a storage system capable of encoding, editing and extracting sequences of real numbers. We study different geometric problems, giving algorithmic solutions to several of them. The accumulation points problem in <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-9364ff6381a2c94a1275e7a1ac1ab35e_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#82;&#125;&#94;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"20\" style=\"vertical-align: 0px;\"\/> is presented and solved for countable sets with finitely many accumulation points. Also, the convex hull problem is studied. We show how to compute the closure of the convex hull of countable bounded sets in <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-f9868b4451c5811a288f7fdd10be5558_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#109;&#97;&#116;&#104;&#98;&#98;&#123;&#82;&#125;&#94;&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"21\" style=\"vertical-align: 0px;\"\/>. The non-crossing perfect matching problem with infinite input is addressed as well.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-9d6595d7 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:100%\">\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n<\/div>\n<\/div>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Thursday, February 25, 2021, 16:00-17:00<br><strong>Title<\/strong>: Rectilinear convex hull of points in 3D<br><strong>Speaker<\/strong>: Carlos Seara (UPC)<br><strong>Abstract<\/strong>: Let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-650eb7688af6737ac325425b5c9a5982_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#80;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> be a set of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-b170995d512c659d8668b4e42e1fef6b_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"11\" style=\"vertical-align: 0px;\"\/> points in the space in general position, and let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-74b2095f972317b624939c57e8d61382_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#82;&#67;&#72;&#40;&#80;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"70\" style=\"vertical-align: -5px;\"\/> be the rectilinear convex hull of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-650eb7688af6737ac325425b5c9a5982_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#80;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/>. In this talk we present an optimal <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-546b1d4fb3b6cef91a21f5a85d056dd2_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#79;&#40;&#110;&#92;&#108;&#111;&#103;&#123;&#110;&#125;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"77\" style=\"vertical-align: -5px;\"\/>-time and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-31c2cdca867987ac2a6e27b1434ae748_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#79;&#40;&#110;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"38\" style=\"vertical-align: -5px;\"\/>-space algorithm to compute <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-74b2095f972317b624939c57e8d61382_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#82;&#67;&#72;&#40;&#80;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"70\" style=\"vertical-align: -5px;\"\/>. We also present an efficient <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-7d3ff7738acf38857ba61e51bfaf6838_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#79;&#40;&#110;&#92;&#108;&#111;&#103;&#94;&#50;&#123;&#110;&#125;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"21\" width=\"85\" style=\"vertical-align: -5px;\"\/>-time and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-546b1d4fb3b6cef91a21f5a85d056dd2_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#79;&#40;&#110;&#92;&#108;&#111;&#103;&#123;&#110;&#125;&#41;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"77\" style=\"vertical-align: -5px;\"\/>-space algorithm to compute and maintain the set of vertices of the rectilinear convex hull of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-650eb7688af6737ac325425b5c9a5982_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#80;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"14\" style=\"vertical-align: 0px;\"\/> as we rotate the coordinate system around the <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/dccg.upc.edu\/topping\/wp-content\/ql-cache\/quicklatex.com-4586e340cb83d5b642972e97a288fec2_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#122;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"9\" style=\"vertical-align: 0px;\"\/>-axis. Finally we study some properties of the rectilinear convex hulls of point sets in the space.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Upcoming seminars Previous seminars<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-28","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/dccg.upc.edu\/topping\/wp-json\/wp\/v2\/pages\/28","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dccg.upc.edu\/topping\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/dccg.upc.edu\/topping\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/dccg.upc.edu\/topping\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dccg.upc.edu\/topping\/wp-json\/wp\/v2\/comments?post=28"}],"version-history":[{"count":31,"href":"https:\/\/dccg.upc.edu\/topping\/wp-json\/wp\/v2\/pages\/28\/revisions"}],"predecessor-version":[{"id":213,"href":"https:\/\/dccg.upc.edu\/topping\/wp-json\/wp\/v2\/pages\/28\/revisions\/213"}],"wp:attachment":[{"href":"https:\/\/dccg.upc.edu\/topping\/wp-json\/wp\/v2\/media?parent=28"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}