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. 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
3. 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
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. Rationale and Precautioning Clauses: Insights from A’ingae

   https://doi.org/10.1093/jos/ffac012  

   Dąbkowski, Maksymilian; AnderBois, Scott (January 2024, Journal of Semantics)

   Abstract We describe and analyze the semantics of rationale and precautioning clauses (i.e. in order to- and lest-clauses) through a detailed case study of two operators in A’ingae (or Cofán, iso 639-3: con, an Amazonian isolate): the infinitive -ye ‘inf’ and the apprehensional -sa’ne ‘appr.’ We provide a new account of rationale semantics and the first formal account of precautioning semantics. We propose that in structures such as [$$p$$ [(in order) to$$q$$]] or [$$p$$ [$$q$$-ye]], the rationale operator (underlined) encodes modal semantics where the goal worlds of the actor responsible for $$p$$ achieve $$q$$. In structures such as [$$p$$ [lest$$q$$]] or [$$p$$ [$$q$$-sa’ne]], the precautioning operator encodes modal semantics where the actor’s goal worlds avoid a recoverable situation $$r$$ which entails $$q$$ ($$r\Rightarrow q$$). We observe and account for three apparent asymmetries within the domain of rationale and precautioning semantics, which we dub precautioning semantics asymmetry, rationale polarity asymmetry, and precautioning encoding asymmetry. We thus elucidate the relation between rationale and precautioning clauses and make substantial predictions with respect to the cross-linguistic inventories of rationale and precautioning operators. 

   more » « less