Theory and Applications of Point Configurations and Graphs (TOPPING)

Website of the TOPPING project

TOPPING Seminar

Upcoming seminars

Previous seminars

Friday, September 20, 2024, 12:00-13:00
Title: Polycubes with small perimeter defect
Speaker: Gill Barequet (Technion — Israel Inst. of Technology)
Abstract: Polycubes 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.
Thursday, July 10, 2024, 16:00-17:00
Title: Construcción del ciclo simétrico de longitud 5, usando la construcción de Hajós a través de un algoritmo genético
Speaker: Juan Carlos García Altamirano (Universidad Autónoma Metropolitana – Cuajimalpa, Mexico)
Abstract: Una coloración de vértices de un digrafo es acíclica si no hay ciclos dirigidos monocromáticos. El número dicromático de un digrafo D es el número mínimo de colores de una coloración acíclica de D, denotado por dc(D). Un dígrafo D es r-crítico si dc(D) = r y dc(H) < r para cualquier subdigrafo H de D. En 2020, Bang-Jensen et al., extendieron la conocida construcción de Hajós de grafos para digrafos y demostraron que: a partir de copias del digrafo simétrico completo con r vértices, D(K_r), se puede construir cualquier digrafo r-crítico mediante uniones dirigidas de Hajós e identificaciones de vértices no adyacentes. Sin embargo, a los autores les apenó mucho no poder construir, ni siquiera, al ciclo simétrico 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ético mediante la introducción de operadores innovadores de recombinación y mutación de la teoría de grafos. Dicho algoritmo obtuvo una sucesión de operaciones de Hajós que atravesó más de 5000 generaciones. En esta charla presentamos la sucesión reducida de 16 operaciones de Hajós para construir el ciclo simétrico de orden 5 y cómo generalizar esta sucesión para obtener cualquier ciclo simétrico de longitud impar a partir de copias de D(K_3).
Thursday, May 30, 2024, 15:00-16:00
Title: Reconstructing a pseudotree from the distance matrix of its boundary
Speaker: Iñaki Pelayo (UPC)
Abstract: 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 ∂(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 ∈ [n], [DˆG]ij = dG(i, j). The boundary distance matrix DˆG of G is the square matrix of order κ, being κ the order of ∂(G), such that for every i, j ∈ ∂(G), [DˆG]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ˆ of order κ, we prove under which conditions Bˆ is the distance matrix DˆT 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ˆG 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.
Thursday, April 25, 2024, 15:00-16:00
Title: Isolation in graphs.
Speaker: Mercè Mora (UPC)
Abstract: 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.
Wednesday, March 6, 2024 15:00-15:30
Title: The Complexity of the Lower Envelope of Collections of Various Geometric Shapes
Speaker: Carlos Seara (UPC)
Abstract: 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’s function. Joint work with Carlos Alegría, Anna Brötzner, and Christiane Schmidt.
Wednesday, March 6, 2024 15:30-16:00
Title: Sibson’s formula for higher order Voronoi diagrams
Speaker: Andrea de las Heras (UPC)
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, “A vector identity for the Dirichlet tessellation”, 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’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.
Tuesday, January 23, 2024 15:00-16:30
Title: Packing d-dimensional balls into a (d+1)-dimensional container
Speaker: Sergio Cabello (University of Ljubljana and IMFM, Slovenia)
Abstract: 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−1/d}) is always sufficient and sometimes necessary. Joint work with Helmut Alt, Otfried Cheong, Ji-won Park and Nadja Seiferth.
Thursday, November 30, 2023 15:00-16:00
Title: Rectilinear convex hull of set of objects
Speaker: Carlos Seara (UPC)
Abstract: 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’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.
Wednesday, May 3, 2023, 14:30-15:30
Title: Obstacle Avoidance
Speaker: Subhash Suri (University of California, Santa Barbara)
Abstract: 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.
Tuesday, April 26, 2022, 16:00-17:00
Title: k-Transmitter Watchman Routes
Speaker: Bengt J. Nilsson (Malmö University)
Abstract: We consider the watchman route problem for a $k$ -transmitter watchman: standing at point $p$ in a polygon $P$ , the watchman can see $q \in P$ if $pq$ intersects $P$ ’s boundary at most $k$ times— $q$ is $k$ -visible to $p$ . Travelling along the $k$ -transmitter watchman route, either all points in $P$ or a discrete set of points $S \subset P$ must be $k$ -visible to the watchman. We aim to minimize the length of the $k$ -transmitter watchman route. We show that even in simple polygons the $k$ -transmitter watchman route problem for $S \subset P$ is NP-complete—both if a given starting point for the route is given and if no such point exists. Moreover, we present a polylogarithmic approximation for the $k$ -transmitter watchman route problem for a given starting point and $S \subset P$ with approximation ratio $O(\log_2{(|S| \cdot n)}^2\log{\log{(|S| \cdot n)}}^2\log{|S|})$ (with $\lvert P\rvert = n$ ).

Tuesday, March 22, 2022, 16:00-17:00
Title: Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs
Speaker: Javier Tejel (Universidad de Zaragoza)
Abstract: 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 $O$ such that every ray emanating from $O$ crosses every edge of the drawing at most once and there is a ray emanating from $O$ which crosses every edge exactly once. Via this new class of simple drawings, we show that every simple drawing of the complete graph with $n$ vertices contains $\Omega(n^{1/2})$ pairwise disjoint edges and a plane path of length $\Omega(\frac{\log n}{\log{\log n}})$ . Both results improve over previously known best lower bounds.

Thursday, March 10, 2022, 16:00-16:45. Special seminar session with two short talks.

—– Talk 1 —–
Title: Spanning ratio of shortest paths in weighted square tessellations
Speaker: Guillermo Esteban (Universidad de Alcalá and Carleton University)
Abstract: 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 $SP_w(s,t)$ which is a shortest path from s to t in the continuous weighted 2D-space, and a shortest grid path $SGP_w(s,t)$ , which is a shortest path in the tessellated weighted 2D-space. Our main result is that the ratio $\frac{SGP_w(s,t)}{SP_w(s,t)}$ is at most $\frac{2}{\sqrt{2+\sqrt{2}}} \approx 1.08$ , irrespective of the weight assignment.

—– Talk 2 —–
Title: Properties for Voronoi Diagrams of Arbitrary Order on the Sphere
Speaker: Andrea de Las Heras (UPC)
Abstract: For a given set of points $U$ on a sphere $S$ , the order $k$ spherical Voronoi diagram $SV_k(U)$ decomposes the surface of $S$ into regions whose points have the same $k$ nearest points of $U$ . We study properties for $SV_k(U)$ , using different tools: the geometry of the sphere, a labeling for the edges of $SV_k(U)$ , and the inversion transformation. Hyeon-Suk Na, Chung-Nim Lee and Otfried Cheong (Comput. Geom., 2002) applied inversions to construct $SV_1(U)$ . We generalize their construction for spherical Voronoi diagrams from order 1 to any order $k$ . We use that construction to prove formulas for the numbers of vertices, edges, and faces in $SV_k(U)$ . Among the properties of $SV_k(U)$ , we also show that $SV_k(U)$ has a small orientable cycle double cover.

Tuesday, December 21, 2021, 16:00-17:00
Title: The edge labeling of higher order Voronoi diagrams
Speaker: Alejandra Martínez (Universidad de Alcalá)
Abstract: We present an edge labeling of order- $k$ Voronoi diagrams, $V_k(S)$ , of point sets $\mathcal{S}$ in the plane, and study properties of the regions defined by them. Among them, we show that $V_k(S)$ has a small orientable cycle and path double cover, and we identify configurations that cannot appear in $V_k(S)$ for small values of $k$ .

Tuesday, November 23, 2021, 16:00-17:00
Title: Illuminating a line segment or a line by alpha-floodlights
Speaker: Leonidas Palios (University of Ioannina, Greece)
Abstract: For a positive angle $\alpha$ , an $\alpha$ -floodlight is a floodlight in the plane with illumination cone angle equal to $\alpha$ . In this talk, we consider the problem in which we are given a set $\mathcal{S}$ of planar regions with piece-wise linear boundary, a positive angle $\alpha$ , and a line segment or a line $L$ in the plane, and we want to compute the locations and orientations of the minimum number of $\alpha$ -floodlights positioned at points in $\mathcal{S}$ which suffice to entirely illuminate $L$ . We show that the problem can be solved in $O(n \log {n})$ time and $O(n)$ space, where $n$ is the total number of vertices of the regions in the set $\mathcal{S}$ .

Tuesday, October 26, 2021, 16:00-17:00
Title: Terrain prickliness: theoretical grounds for high complexity viewsheds
Speaker: Rodrigo Silveira (UPC)
Abstract: 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 “prickliness”, 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.

Thursday, July 1, 2021, 16:00-17:00
Title: On the intersection graph of the disks with diameters the sides of a convex $n$ -gon
Speaker: Luis Hernán Herrera Becerra (Universidad de Santiago de Chile, USACH)
Abstract: Given a convex $n$ -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érez-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 $O(n)$ -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 $O(n)$ 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 $n$ -gon we can select at least $\frac{n}{4}$ pairwise disjoint disks, and we prove that for every $n\geq3$ there exist convex $n$ -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.

Thursday, May 27, 2021, 16:00-17:00
Speaker: Ana Laura Trujillo (CINVESTAV, Mexico)
Title: Laplacian spectrum of token graphs
Abstract: Let $G$ be a simple graph of order $n\geq2$ , and let $k$ be an integer with $1 \geq k \geq n-1$ . The $k$ -token graph $F_k(G)$ of $G$ is the graph whose vertices are all the $k$ -subsets of $V(G)$ , where two of such $k$ -subsets are adjacent in $F_k(G)$ if their symmetric difference is a pair of adjacent vertices of $G$ . 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 $h$ and $k$ with $1 \geq h < k \geq \frac{n}{2}$ , the Laplacian spectrum of $F_h(G)$ is contained in the Laplacian spectrum of $F_k(G)$ . Besides, we provide three infinite families of graphs for which the algebraic connectivities of $G$ and $F_k(G)$ are equal, for any $k$ with $1 \geq k \geq n-1$ . Finally, we will show a relationship between the Laplacian spectrum of the $k$ -token graph of $G$ and the $k$ -token graph of its complement $\overline{G}$ .

Thursday, May 6, 2021, 16:00-17:00
Title: Fragile Complexity of Adaptive Algorithms
Speaker: Pilar Cano (Université Libre de Bruxelles)
Abstract: The fragile complexity of a comparison-based algorithm is $f(n)$ if each input element participates in $O(f(n))$ 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 $n$ . We show that searching for the predecessor in a sorted array has fragile complexity $\Theta(\log{k})$ , where $k$ 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 $k$ -th smallest element has expected fragile complexity $O(\log{\log{k}})$ for the element selected. Deterministically finding the minimum element has fragile complexity $\Theta(\log{(Inv)})$ and $\Theta(\log{(Runs)})$ , 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 $O(\log{(Runs)} + \log{\log{n}})$ and $\Theta(\log{(Inv)})$ . Deterministic sorting has fragile complexity $\Theta(\log{(Inv)})$ but it has fragile complexity $\Theta(\log{n})$ regardless of the number of runs.

Thursday, April 29, 2021, 16:00-17:00
Title: On Maximum-Sum Matchings of Points
Speaker: Oscar Chacón-Rivera (Universidad de Santiago de Chile)
Abstract: Huemer et al. (Discrete Math., 2019) proved that for any two point sets $R$ and $B$ with $|R| = |B|$ , the perfect matching that matches points of $R$ with points of $B$ , 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 $2n$ 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.

Thursday, March 25, 2021, 16:00-17:00
Title: Algorithmic Geometry with Infinite Computation
Speaker: Adrián Tobar Nicolau (UPC)
Abstract: In this talk we present an algorithmic study of problems from computational geometry with countably infinite input, especially countable sets in $\mathbb{R}^n$ . 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 $\mathbb{R}^2$ 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 $\mathbb{R}^n$ . The non-crossing perfect matching problem with infinite input is addressed as well.

Thursday, February 25, 2021, 16:00-17:00
Title: Rectilinear convex hull of points in 3D
Speaker: Carlos Seara (UPC)
Abstract: Let $P$ be a set of $n$ points in the space in general position, and let $RCH(P)$ be the rectilinear convex hull of $P$ . In this talk we present an optimal $O(n\log{n})$ -time and $O(n)$ -space algorithm to compute $RCH(P)$ . We also present an efficient $O(n\log^2{n})$ -time and $O(n\log{n})$ -space algorithm to compute and maintain the set of vertices of the rectilinear convex hull of $P$ as we rotate the coordinate system around the $z$ -axis. Finally we study some properties of the rectilinear convex hulls of point sets in the space.