More Like this

1. Computing the Caratheodory Number of a Point

   Bereg, Sergey; Haghpanah, Mohammadreza (August 2020, Canadian Conference on Computational Geometry)

   Caratheodory’s theorem says that any point in the convex hull of a set $$P$$ in $R^d$ is in the convex hull of a subset $P'$ of $$P$$ such that $$|P'| \le d + 1$$. For some sets P, the upper bound d + 1 can be improved. The best upper bound for P is known as the Caratheodory number [2, 15, 17]. In this paper, we study a computational problem of finding the smallest set $P'$ for a given set $$P$$ and a point $$p$$. We call the size of this set $P'$, the Caratheodory number of a point p or CNP. We show that the problem of deciding the Caratheodory number of a point is NP-hard. Furthermore, we show that the problem is k-LDT-hard. We present two algorithms for computing a smallest set $P'$, if CNP= 2,3. Bárány [1] generalized Caratheodory’s theorem by using d+1 sets (colored sets) such that their convex hulls intersect. We introduce a Colorful Caratheodory number of a point or CCNP which can be smaller than d+1. Then we extend our results for CNP to CCNP. 

   more » « less
2. A simple proof of reflexivity and separability of N^{1,p} Sobolev spaces

   https://doi.org/10.54330/afm.127419  

   Alvarado, Ryan; Hajłasz, Piotr; Malý, Lukáš (October 2022, Annales Fennici Mathematici)

   We present an elementary proof of a well-known theorem of Cheeger which states that if a metric-measure space \(X\) supports a \(p\)-Poincaré inequality, then the \(N^{1,p}(X)\) Sobolev space is reflexive and separable whenever \(p\in (1,\infty)\). We also prove separability of the space when \(p=1\). Our proof is based on a straightforward construction of an equivalent norm on \(N^{1,p}(X)\), \(p\in [1,\infty)\), that is uniformly convex when \(p\in (1,\infty)\). Finally, we explicitly construct a functional that is pointwise comparable to the minimal \(p\)-weak upper gradient, when \(p\in (1,\infty)\). 

   more » « less
3. Classification of metric measure spaces and their ends using p-harmonic functions

   https://doi.org/10.54330/afm.120618  

   Björn, Anders; Björn, Jana; Shanmugalingam, Nageswari (March 2022, Annales Fennici Mathematici)

   By seeing whether a Liouville type theorem holds for positive, bounded, and/or finite \(p\)-energy \(p\)-harmonic and \(p\)-quasiharmonic functions, we classify proper metric spaces equipped with a locally doubling measure supporting a local \(p\)-Poincaré inequality. Similar classifications have earlier been obtained for Riemann surfaces and Riemannian manifolds. We study the inclusions between these classes of metric measure spaces, and their relationship to the \(p\)-hyperbolicity of the metric space and its ends. In particular, we characterize spaces that carry nonconstant \(p\)-harmonic functions with finite \(p\)-energy as spaces having at least two well-separated \(p\)-hyperbolic sequences of sets towards infinity. We also show that every such space \(X\) has a function \(f \notin L^p(X) + \mathbf{R}\) with finite \(p\)-energy. 

   more » « less
4. Fast and Exact Convex Hull Simplification

   https://doi.org/10.4230/LIPIcs.FSTTCS.2021.26  

   Klimenko, Georgiy; Raichel, Benjamin (October 2021, Foundations of Software Technology and Theoretical Computer Science (FSTTCS))

   Bojanczyk, Mikolaj; Chekuri, Chandra (Ed.)

   Given a point set P in the plane, we seek a subset Q ⊆ P, whose convex hull gives a smaller and thus simpler representation of the convex hull of P. Specifically, let cost(Q,P) denote the Hausdorff distance between the convex hulls CH(Q) and CH(P). Then given a value ε > 0 we seek the smallest subset Q ⊆ P such that cost(Q,P) ≤ ε. We also consider the dual version, where given an integer k, we seek the subset Q ⊆ P which minimizes cost(Q,P), such that |Q| ≤ k. For these problems, when P is in convex position, we respectively give an O(n log²n) time algorithm and an O(n log³n) time algorithm, where the latter running time holds with high probability. When there is no restriction on P, we show the problem can be reduced to APSP in an unweighted directed graph, yielding an O(n^2.5302) time algorithm when minimizing k and an O(min{n^2.5302, kn^2.376}) time algorithm when minimizing ε, using prior results for APSP. Finally, we show our near linear algorithms for convex position give 2-approximations for the general case. 

   more » « less
5. Underestimated Neotropical diversity: Integrative taxonomy reveals two unrelated look-alike species in a suboscine bird ( Pachyramphus albogriseus )

   https://doi.org/10.1093/ornithology/ukac047  

   Musher, Lukas J.; Krabbe, Niels K.; Areta, Juan I. (August 2022, Ornithology)

   Abstract We applied an integrative taxonomic framework to evaluate the systematics of the Neotropical Black-and-white Becard (Pachyramphus albogriseusSclater 1857). Combining phylogenomic (ultraconserved elements), morphological, and vocalization data, we confirmed that this species is polyphyletic; some individuals form a clade sister to P. polychopterus and should be afforded species rank as P. salviniRichmond 1899 (Slender-billed Becard), whereas the remaining subspecies of P. albogriseus (Broad-banded Becard) are sister to P. major. We found that P. salvini differs from P. albogriseus in song, color of the lores, wing-bar width, body size, and bill width. Whereas P. albogriseus occurs in montane forest in Costa Rica and Panama (ssp. ornatus) and along the eastern slope of the Andes from northern Venezuela to southern Peru (ssp. albogriseus), P. salvini is found in the lowlands from Pacific Colombia south to northwest Peru and in the Río Marañón drainage. The latter also occurs, possibly only seasonally, along the eastern slope of the Andes, where the two species’ ranges approach closely. We treat P. a. guayaquilensisZimmer 1936 as a junior synonym of P. salviniRichmond 1899, and P. a. coronatusPhelps and Phelps 1953 as a junior synonym of P. a. albogriseusSclater 1857. This study provides a striking example of a major problem for comparative biology: underestimated and mischaracterized diversity. We argue that there are likely many more cases like this awaiting discovery. 

   more » « less