Search

A set of n segments in the plane may form a Euclidean TSP tour, a tree, or a matching, among others. Optimal TSP tours as well as minimum spanning trees and perfect matchings have no crossing segments, but several heuristics and approximation algorithms may produce solutions with crossings. If two segments cross, then we can reduce the total length with the following flip operation. We remove a pair of crossing segments, and insert a pair of non-crossing segments, while keeping the same vertex degrees. In this paper, we consider the number of flips performed under different assumptions, using a new unifying framework that applies to tours, trees, matchings, and other types of (multi)graphs. Within this framework, we prove several new bounds that are sensitive to whether some endpoints are in convex position or not., Comment: 36 pages, 22 figures. Preliminary versions of these results appeared in WALCOM 2023, WALCOM 2024, and the PhD dissertation of Bastien Rivier. arXiv admin note: substantial text overlap with arXiv:2307.00853

A \emph{conforming partition} of a rectilinear $ n $-gon\bastien{I change from ``a polygon'', otherwise $ n $ is not defined.} $ P $ is a partition of $ P $ into rectangles without using Steiner points (i.e., all corners of all rectangles must lie on\bastien{Maybe add: the boundary of} $ P $). The stabbing number of such a partition is the maximum number of rectangles intersected by an axis-aligned segment lying in the interior of $ P $. In this paper, we examine the problem of computing conforming partitions with low stabbing number. We show that computing a conforming partition with stabbing number at most~$ 4 $ is $ NP $-hard, which strengthens a previously known hardness result [Durocher \& Mehrabi, Theor. Comput. Sci. 689: 157-168 (2017)] and eliminates the possibility for fixed-parameter-tractable algorithms parameterized by the stabbing number unless $ P = NP $. In contrast, we give (i) an $ O ( n \log n ) $-time\bastien{Reviewer request: changed from "linearithmic".} algorithm to decide whether a conforming partition with stabbing number~$ 2 $ exists, (ii) a fixed-parameter-tractable algorithm parameterized by both the stabbing number and treewidth of the pixelation of the polygon, and (iii) a fixed-parameter-tractable algorithm parameterized by the stabbing number for simple polygons in general position., Comment: 29 pages, 17 figures, accepted to WALCOM 2025

Given a finite set $ S $ of points, we consider the following reconfiguration graph. The vertices are the plane spanning paths of $ S $ and there is an edge between two vertices if the two corresponding paths differ by two edges (one removed, one added). Since 2007, this graph is conjectured to be connected but no proof has been found. In this paper, we prove several results to support the conjecture. Mainly, we show that if all but one point of $ S $ are in convex position, then the graph is connected with diameter at most $ 2 | S | $ and that for $ | S | \geq 3 $ every connected component has at least $ 3 $ vertices., Comment: 12 pages, 7 figures

We revisit the two-armed bandit (TAB) problem where both arms are driven by diffusive stochastic processes with a common instantaneous reward. We focus on situations where the Radon-Nikodym derivative between the transition probability densities of the first arm with respect to the second is explicitly known. We calculate how the corresponding Gittins' indices behave under such a change of probability measure. This general framework is used to solve the optimal allocation of a TAB problem where the first arm is driven by a pure Brownian motion and the second is driven by a centered super-diffusive non-Gaussian process with variance quadratically growing in time. The probability spread due to the super-diffusion introduces an extra risk into the allocation problem. This drastically affects the optimal decision rule. Our modeling illustrates the interplay between the notions of risk and volatility.

For the Erd\H{o}s-R\'enyi graph of size $N$ with mean degree $(1+o(1))\frac{\log N}{t+1}\leq d\leq(1-o(1))\frac{\log N}{t}$ where $t\in\mathbb{N}^{*}$, with high probability the smallest non zero eigenvalue of the Laplacian is equal to $2-2\cos(\pi(2t+1)^{-1})+o(1)$. This eigenvalue arises from a small subgraph isomorphic to a line of size $t$ linked to the giant connected component by only one edge., Comment: 22 pages, 4 figures

Semantic segmentation is crucial in remote sensing, where high-resolution satellite images are segmented into meaningful regions. Recent advancements in deep learning have significantly improved satellite image segmentation. However, most of these methods are typically trained in fully supervised settings that require high-quality pixel-level annotations, which are expensive and time-consuming to obtain. In this work, we present a weakly supervised learning algorithm to train semantic segmentation algorithms that only rely on query point annotations instead of full mask labels. Our proposed approach performs accurate semantic segmentation and improves efficiency by significantly reducing the cost and time required for manual annotation. Specifically, we generate superpixels and extend the query point labels into those superpixels that group similar meaningful semantics. Then, we train semantic segmentation models supervised with images partially labeled with the superpixel pseudo-labels. We benchmark our weakly supervised training approach on an aerial image dataset and different semantic segmentation architectures, showing that we can reach competitive performance compared to fully supervised training while reducing the annotation effort. The code of our proposed approach is publicly available at: https://github.com/santiago2205/LSSQPS., Comment: Paper Accepted at ICIP 2024 (Oral Presentation)

A (multi)set of segments in the plane may form a TSP tour, a matching, a tree, or any multigraph. If two segments cross, then we can reduce the total length with the following flip operation. We remove a pair of crossing segments, and insert a pair of non-crossing segments, while keeping the same vertex degrees. The goal of this paper is to devise efficient strategies to flip the segments in order to obtain crossing-free segments after a small number of flips. Linear and near-linear bounds on the number of flips were only known for segments with endpoints in convex position. We generalize these results, proving linear and near-linear bounds for cases with endpoints that are not in convex position. Our results are proved in a general setting that applies to multiple problems, using multigraphs and the distinction between removal and insertion choices when performing a flip., Comment: 19 pages, 10 figures

A set of segments in the plane may form a Euclidean TSP tour or a matching, among others. Optimal TSP tours as well as minimum weight perfect matchings have no crossing segments, but several heuristics and approximation algorithms may produce solutions with crossings. To improve such solutions, we can successively apply a flip operation that replaces a pair of crossing segments by non-crossing ones. This paper considers the maximum number D(n) of flips performed on n segments. First, we present reductions relating D(n) for different sets of segments (TSP tours, monochromatic matchings, red-blue matchings, and multigraphs). Second, we show that if all except t points are in convex position, then D(n) = O(tn^2), providing a smooth transition between the convex O(n^2) bound and the general O(n^3) bound. Last, we show that if instead of counting the total number of flips, we only count the number of distinct flips, then the cubic upper bound improves to O(n^{8/3})., Comment: 9 pages, 4 figures, appears in Walcom'23

Given a matching between n red points and n blue points by line segments in the plane, we consider the problem of obtaining a crossing-free matching through flip operations that replace two crossing segments by two non-crossing ones. We first show that (i) it is NP-hard to alpha-approximate the shortest flip sequence, for any constant alpha. Second, we show that when the red points are colinear, (ii) given a matching, a flip sequence of length at most n(n-1)/2 always exists, and (iii) the number of flips in any sequence never exceeds (n(n-1)/2) (n+4)/6. Finally, we present (iv) a lower bounding flip sequence with roughly 1.5 n(n-1)/2 flips, which shows that the n(n-1)/2 flips attained in the convex case are not the maximum, and (v) a convex matching from which any flip sequence has roughly 1.5 n flips. The last four results, based on novel analyses, improve the constants of state-of-the-art bounds., Comment: 28 pages, 27 figures, accepted at EuroCG 2022, at CORE 2022 (ICALP Workshop), at LATIN 2022, and at CGTA 2022 (EuroCG 2022 special issue)

Phyllotaxis describes the arrangement of florets, scales or leaves in composite flowers or plants (daisy, aster, sunflower, pinecone, pineapple). As a structure, it is a geometrical foam, the most homogeneous and densest covering of a large disk by Voronoi cells (the florets), constructed by a simple algorithm: Points placed regularly on a generative spiral constitute a spiral lattice, and phyllotaxis is the tiling by the Voronoi cells of the spiral lattice. Locally, neighboring cells are organized as three whorls or parastichies, labeled with successive Fibonacci numbers. The structure is encoded as the sequence of the shapes (number of sides) of the successive Voronoi cells on the generative spiral. We show that sequence and organization are independent of the position of the initial point on the generative spiral, that is invariant under disappearance ($T2$) of the first Voronoi cell or, conversely, under creation of a first cell, that is under growth. This independence shows how a foam is able to respond to a shear stress, notably through grain boundaries that are layers of square cells slightly truncated into heptagons, pentagons and hexagons, meeting at four-corner vertices, critical points of $T1$ elementary topological transformations.

A close packed organization with circular symmetry of a large number of small discs on a plane is obtained when the centres of the discs are distributed according to the algorithm of phyllotaxis. We study here the distributions obtained on surfaces of constant Gaussian curvatures, positive for the sphere or negative for the hyperbolic plane. We examine how the properties of homogeneity, isotropy and self-similarity typical of the distribution on the plane, and resulting from the presence of circular grain boundaries with quasicrystalline sequences, are affected by the curvature of the bearing surface. The quasicrystalline sequences of the grain boundaries appear indeed to be structural invariants, but the widths of the grains they separate vary differently with the curvature of the surface. The self similarity of the whole organization observed on the plane is therefore lost on the hyperbolic plane and the sphere. The evolutions of the local order within the grains show no differences except on the equatorial belt of the sphere where the isotropy is decreased owing to the symmetry of this finite surface around its equator.

With hundreds of exoplanets detected, it is necessary to revisit giant planets accretion models to explain their mass distribution. In particular, formation of sub-jovian planets remains unclear, given the short timescale for the runaway accretion of massive atmospheres. However, gas needs to pass through a circum-planetary disc. If the latter has a low viscosity (as expected if planets form in "dead zones"), it might act as a bottleneck for gas accretion. We investigate what the minimum accretion rate is for a planet under the limit assumption that the circum-planetary disc is totally inviscid, and the transport of angular momentum occurs solely because of the gravitational perturbations from the star. To estimate the accretion rate, we present a steady-state model of an inviscid circum-planetary disc, with vertical gas inflow and external torque from the star. Hydrodynamical simulations of a circum-planetary disc were conducted in 2D, in a planetocentric frame, with the star as an external perturber in order to measure the torque exerted by the star on the disc. The disc shows a two-armed spiral wave caused by stellar tides, propagating all the way in from the outer edge of the disc towards the planet. The stellar torque is small and corresponds to a doubling time for a Jupiter mass planet of the order of 5 Myrs. Given the limit assumptions, this is clearly a lower bound of the real accretion rate. This result shows that gas accretion onto a giant planet can be regulated by circum-planetary discs. This suggests that the diversity of masses of extra-solar planets may be the result of different viscosities in these discs., Comment: Accepted for publication in Astronomy and Astrophysics. 7 pages, 2 figures

Phyllotaxis, the search for the most homogeneous and dense organizations of small disks inside a large circular domain, was first developed to analyze arrangements of leaves or florets in plants. Then it has become an object of study not only in botany, but also in mathematics, computer simulations and physics. Although the mathematical solution is now well known, an algorithm setting out the centers of the small disks on a Fermat spiral, the very nature of this organization and its properties of symmetry remain to be examined. The purpose of this paper is to describe a phyllotactic organization of points through its Voronoi cells and Delaunay triangulation and to refer to the concept of defects developed in condensed matter physics. The topological constraint of circular symmetry introduces an original inflation-deflation symmetry taking the place of the translational and rotational symmetries of classical crystallography.

In the peripheral nervous system, utrophin and the short dystrophin isoform (Dp116) are co-localized at the outermost layer of the myelin sheath of nerve fibers; together with the dystroglycan complex. In peripheral nerve, matrix metalloproteinase (MMP) creates a 30 kDa fragment of beta-dystroglycan, leading to a disruption of the link between the extracellular matrix and the cell membrane. Here we asked if the processing of the beta-dystroglycan could influence the anchorage of Dp116 or/and utrophin in normal and mdx Schwann cell membrane. We showed that MMP-9 was more activated in mdx nerve than in wild-type one. This activation leads to an accumulation of the 30 kDa beta-dystroglycan isoform and have an impact on the anchorage of Dp116 and utrophin isoforms in mdx Schwann cells membrane. Our results showed that Dp116 had greater affinity to the full length form of beta-dystroglycan than the 30 kDa form. Moreover, we showed for the first time that the short isoform of utrophin (Up71) was over-expressed in mdx Schwann cells compared to wild-type. In addition, this utrophin isoform (Up71) seems to have greater affinity to the 30 kDa beta-dystroglycan which could explain a more stabilization of this 30 kDa at the membrane compartment. Our results highlight the potential participation of the short utrophin isoform and the cleaved form of beta-dystroglycan in mdx Schwann cell membrane architecture.

We present the first space-filling bearing in three dimensions. It is shown that a packing which contains only loops with even number of spheres can be constructed in a self-similar way and that it can act as a three dimensional bearing in which spheres can rotate without slip and with negligible torsion friction., Comment: 4 pages, 4 figures, accepted for Physical Review Letters

Geometrically, foams or covalent graphs can be decomposed into successive layers or strata. Disorder of the underlying structure imposes a characteristic roughening of the layers. Our main results are hysteresis and convergence in the layer sequences. 1) If the direction of construction is reversed, the layers are different in the up and down sequences (irreversibility); nevertheless, under suitable but non-restrictive conditions, the layers come back, exactly, to the initial profile, a hysteresis phenomenon. 2) Layer sequences based on different initial conditions (e.g. different starting cells) converge, at least in the cylindrical geometry. Jogs in layers may be represented as pairs of opposite dislocations, moving erratically due to the disorder of the underlying structure and ending up annihilating when colliding., Comment: 9 pages, 5 figures (9 .eps files)

We analyze the structure of two dimensional disordered cellular systems generated by extensive computer simulations. These cellular structures are studied as topological trees rooted on a central cell or as closed shells arranged concentrically around a germ cell. We single out the most significant parameters that characterize statistically the organization of these patterns. Universality and specificity in disordered cellular structures are discussed., Comment: 18 Pages LaTeX, 16 Postscript figures

We investigate two and three-dimensional shell-structured-inflatable froths, which can be constructed by a recursion procedure adding successive layers of cells around a germ cell. We prove that any froth can be reduced into a system of concentric shells. There is only a restricted set of local configurations for which the recursive inflation transformation is not applicable. These configurations are inclusions between successive layers and can be treated as vertices and edges decorations of a shell-structure-inflatable skeleton. The recursion procedure is described by a logistic map, which provides a natural classification into Euclidean, hyperbolic and elliptic froths. Froths tiling manifolds with different curvature can be classified simply by distinguishing between those with a bounded or unbounded number of elements per shell, without any a-priori knowledge on their curvature. A new result, associated with maximal orientational entropy, is obtained on topological properties of natural cellular systems. The topological characteristics of all experimentally known tetrahedrally close-packed structures are retrieved., Comment: 20 Pages Tex, 11 Postscript figures, 1 Postscript table