@article{22480,
  abstract     = {Background:
The spatial distribution of tree canopies influences ecological functions and residents’ exposure to green spaces. Although several studies have examined green space configuration at neighborhood scales, evidence on tree canopy configuration at the municipal scale, an operational unit for urban planning, remains limited.
Methods:
We conducted a nationwide ecological study of 2,136 Swiss municipalities. Tree canopy coverage (PLAND), aggregation (AI, reflecting how tightly green patches are grouped together), patch density (PD, a measure of fragmentation), and area-weighted mean shape index (SHAPE_AM, a measure of shape complexity) were derived from 1-m canopy maps within municipality-specific populated areas. Natural-cause, cardiovascular, and cancer mortality (2017–2019) were obtained from the Swiss National Cohort. Fully adjusted negative binomial regression models estimated associations between canopy metric and mortality for each IQR increase in the metrics.
Results:
Holding configuration constant, each IQR increase in canopy coverage (∼18%) was associated with a 3.6% [B: −0.036; 95% CI: −0.078 – 0.005] reduction in cardiovascular mortality. Higher aggregation corresponded to a 4.3% [B: 0.043; 95% CI: 0.026–0.061], an 8.9% [B: 0.089; 95% CI: 0.059–0.119], and a 2.1% [B: 0.021; 95% CI: 0–0.042] higher number of natural-cause, cardiovascular, and cancer deaths respectively. Higher fragmentation was associated with a 3.3% [B: 0.033; 95% CI: 0.016–0.050], a 4.9% [B: 0.049; 95% CI: 0.020–0.078], and a 2.2% [B: 0.022; 95% CI: 0.001–0.043] increase in these causes respectively. No meaningful associations were observed between shape complexity and any mortality outcomes. Associations for aggregation and fragmentation were generally stronger in highly urbanized municipalities.
Conclusions:
At the municipal scale, mortality was lower where tree canopy was distributed across several moderately sized, spatially balanced patches rather than highly aggregated or highly fragmented structures. These findings suggest that urban greening strategies should optimize its spatial configuration to maximize health benefits.},
  author       = {Chi, Dengkai and Manoli, Gabriele and Yang, Jun and Richards, Daniel and Hahs, Amy and Lin, Brenda and McDonnell, Mark J. and Zhang, Ye and Zhu, Yue and Qiu, Yeshan and Wang, Jing and Zheng, Xing and Burlando, Paolo and Fatichi, Simone and Tan, Puay Yok},
  issn         = {1873-6750},
  journal      = {Environment International},
  keywords     = {Aggregation, Fragmentation, Green space exposure, Green space morphology, Green space structure, Landscape metrics, Shape complexity},
  publisher    = {Elsevier},
  title        = {{Tree canopy configuration and Swiss adult mortality at the municipal level: A nationwide ecological study}},
  doi          = {10.1016/j.envint.2026.110188},
  volume       = {209},
  year         = {2026},
}

@inproceedings{22405,
  abstract     = {Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainly depends on the object types: for unit disks and squares in 2D, the problem is solvable in truly subquadratic time [Chan et al., 2025], while for other objects, including unit segments and equilateral triangles in 2D or unit balls and axis-parallel unit cubes in 3D, there is no truly subquadratic time algorithm under the Orthogonal Vector (OV) hypothesis [Bringmann et al., 2022]. 
We undertake a comprehensive study of computing the diameter of geometric intersection graphs for various types of objects. We discover many new irregularities, showing that the landscape is extremely nuanced: the source of hardness is a combination of the object type, the true diameter value, and how the objects intersect with each other. Our highlighted results for the 2D case include:  
1) The diameter of non-degenerate, axis-aligned line segments can be computed in truly subquadratic time. Previous hardness result [Bringmann et al., 2022] for line segments applies only to degenerate instances. On the other hand, for the degenerate case, we show that a truly subquadratic time algorithm exists when the true diameter is constant. 
2) An almost-linear-time algorithm for unit-square graphs of constant diameter. Previous algorithms [Duraj et al., 2024; Chan et al., 2025] rely on succinct representation assuming bounded VC-dimension; for such a strategy Ω(n^{7/4}) time is an inherent barrier. 
3) An Õ(n^{4/3})-time algorithm to decide if the diameter of a unit-disk graph is at most 2. This improves upon the recent algorithm with running time Õ(n^{2-1/9}) [Chan et al., 2025]. 
4) Deciding if the diameter of intersection graphs of fat triangles or line segments is at most 2 is truly subquadratic-hard under fine-grained complexity assumptions. Previous lower bounds [Bringmann et al., 2022] only hold when deciding if diameter is at most 3.  Our findings are presented in a pair of papers. This paper focuses solely on the 2D case, while the companion paper is devoted to higher-dimensional cases.},
  author       = {Chan, Timothy M. and Chang, Hsien-Chih and Gao, Jie and Kisfaludi-Bak, Sándor and Le, Hung and Zheng, Da Wei},
  booktitle    = {53rd International Colloquium on Automata, Languages, and Programming},
  issn         = {1868-8969},
  keywords     = {String graphs, Fine-grained complexity, Theory of computation → Computational geometry},
  location     = {Egham, United Kingdom},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Charting the landscape of diameter computation on geometric intersection graphs in the plane}},
  doi          = {10.4230/LIPICS.ICALP.2026.54},
  volume       = {374},
  year         = {2026},
}

@article{10045,
  abstract     = {Given a fixed finite metric space (V,μ), the {\em minimum 0-extension problem}, denoted as 0-Ext[μ], is equivalent to the following optimization problem: minimize function of the form minx∈Vn∑ifi(xi)+∑ijcijμ(xi,xj) where cij,cvi are given nonnegative costs and fi:V→R are functions given by fi(xi)=∑v∈Vcviμ(xi,v). The computational complexity of 0-Ext[μ] has been recently established by Karzanov and by Hirai: if metric μ is {\em orientable modular} then 0-Ext[μ] can be solved in polynomial time, otherwise 0-Ext[μ] is NP-hard. To prove the tractability part, Hirai developed a theory of discrete convex functions on orientable modular graphs generalizing several known classes of functions in discrete convex analysis, such as L♮-convex functions. We consider a more general version of the problem in which unary functions fi(xi) can additionally have terms of the form cuv;iμ(xi,{u,v}) for {u,v}∈F, where set F⊆(V2) is fixed. We extend the complexity classification above by providing an explicit condition on (μ,F) for the problem to be tractable. In order to prove the tractability part, we generalize Hirai's theory and define a larger class of discrete convex functions. It covers, in particular, another well-known class of functions, namely submodular functions on an integer lattice. Finally, we improve the complexity of Hirai's algorithm for solving 0-Ext on orientable modular graphs.
},
  author       = {Dvorak, Martin and Kolmogorov, Vladimir},
  issn         = {1436-4646},
  journal      = {Mathematical Programming},
  keywords     = {minimum 0-extension problem, metric labeling problem, discrete metric spaces, metric extensions, computational complexity, valued constraint satisfaction problems, discrete convex analysis, L-convex functions},
  pages        = {279--322},
  publisher    = {Springer Nature},
  title        = {{Generalized minimum 0-extension problem and discrete convexity}},
  doi          = {10.1007/s10107-024-02064-5},
  volume       = {209},
  year         = {2025},
}

@inproceedings{22373,
  abstract     = {Data dissemination is a fundamental task in distributed computing. This paper studies broadcast problems in various innovative models where the communication network connecting n processes is dynamic (e.g., due to mobility or failures) and controlled by an adversary. 
In the first model, the processes transitively communicate their ids in synchronous rounds along a rooted tree given in each round by the adversary whose goal is to maximize the number of rounds until at least one id is known by all processes. Previous research has shown a ⌈(3n-1)/2⌉-2 lower bound and an O(nlog log n) upper bound. We show the first linear upper bound for this problem, namely ⌈(1+√2) n-1⌉ ≈ 2.4n.
We extend these results to the setting where the adversary gives in each round k-disjoint forests and their goal is to maximize the number of rounds until there is a set of k ids such that each process knows of at least one of them. We give a ⌈3(n-k)/2⌉-1 lower bound and a (π²+6)/6 n+1 ≈ 2.6n upper bound for this problem.
Finally, we study the setting where the adversary gives in each round a directed graph with k roots and their goal is to maximize the number of rounds until there exist k ids that are known by all processes. We give a ⌈3(n-3k)/2⌉+2 lower bound and a ⌈(1+√2)n⌉+k-1 ≈ 2.4n+k upper bound for this problem.
For the two latter problems no upper or lower bounds were previously known.},
  author       = {El-Hayek, Antoine and Henzinger, Monika H and Schmid, Stefan},
  booktitle    = {14th Innovations in Theoretical Computer Science Conference},
  editor       = {Tauman Kalai, Yael},
  isbn         = {9783959772631},
  issn         = {1868-8969},
  keywords     = {broadcast, cover, k-broadcast, dynamic radius, dynamic graphs, oblivious message adversary, time complexity, Theory of computation → Distributed algorithms, Networks → Network algorithms},
  location     = {Cambridge, Massachusetts, USA},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks}},
  doi          = {10.4230/LIPICS.ITCS.2023.47},
  volume       = {251},
  year         = {2023},
}

@inproceedings{10004,
  abstract     = {Markov chains are the de facto finite-state model for stochastic dynamical systems, and Markov decision processes (MDPs) extend Markov chains by incorporating non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization criterion is the maximal expected total reward where the MDP stops after T steps, which can be computed by a simple dynamic programming algorithm. We consider a natural generalization of the problem where the stopping times can be chosen according to a probability distribution, such that the expected stopping time is T, to optimize the expected total reward. Quite surprisingly we establish inter-reducibility of the expected stopping-time problem for Markov chains with the Positivity problem (which is related to the well-known Skolem problem), for which establishing either decidability or undecidability would be a major breakthrough. Given the hardness of the exact problem, we consider the approximate version of the problem: we show that it can be solved in exponential time for Markov chains and in exponential space for MDPs.},
  author       = {Chatterjee, Krishnendu and Doyen, Laurent},
  booktitle    = {Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science},
  isbn         = {978-1-6654-4896-3},
  issn         = {1043-6871},
  keywords     = {Computer science, Heuristic algorithms, Memory management, Automata, Markov processes, Probability distribution, Complexity theory},
  location     = {Rome, Italy},
  pages        = {1--13},
  publisher    = {IEEE},
  title        = {{Stochastic processes with expected stopping time}},
  doi          = {10.1109/LICS52264.2021.9470595},
  year         = {2021},
}

@inbook{4317,
  author       = {Barton, Nicholas H},
  booktitle    = {Analytical biogeography: An integrated approach to the study of animal and plant distributions},
  editor       = {Myers, Alan and Giller, Paul},
  isbn         = {978-0-412-40050-6},
  issn         = {978-94-009-0435-4},
  keywords     = {biogeography, biology, complexity, distribution, evolution, geology},
  pages        = {185 -- 218},
  publisher    = {Springer},
  title        = {{Speciation}},
  doi          = {10.1007/978-94-009-0435-4},
  year         = {1988},
}