We present efficient dynamic data structures for maintaining the union of unit discs and the lower envelope of pseudolines in the plane. More precisely, we present three main results in this paper: (i) We present a linearsize data structure to maintain the union of a set of unit discs under insertions. It can insert a disc and update the union in O (( k +1)log 2 n ) time, where n is the current number of unit discs and k is the combinatorial complexity of the structural change in the union due to the insertion of the new disc. It can also compute, within the same time bound, the area of the union after the insertion of each disc. (ii) We propose a linearsize data structure for maintaining the lower envelope of a set of x monotone pseudolines. It can handle insertion/deletion of a pseudoline in O (log 2 n ) time; for a query point x 0 ∈ ℝ, it can report, in O (log n ) time, the point on the lower envelope with x coordinate x 0 ; and for a query point q ∈ ℝ 2 , it can return all k pseudolines lying below q in time O (log n + k log 2 n ). (iii) We present a linearsize data structure for storing a set of circular arcs of unit radius (not necessarily on the boundary of the union of the corresponding discs), so that for a query unit disc D , all input arcs intersecting D can be reported in O ( n 1/2+ɛ + k ) time, where k is the output size and ɛ > 0 is an arbitrarily small constant. A unitcircle arc can be inserted or deleted in O (log 2 n ) time.
more »
« less
Affine actions with Hitchin linear part
Properly discontinuous actions of a surface group by affine automorphisms of ℝ^d were shown to exist by DancigerGueritaudKassel. We show, however, that if the linear part of an affine surface group action is in the Hitchin component, then the action fails to be properly discontinuous. The key case is that of linear part in 𝖲𝖮(n,n−1), so that the affine action is by isometries of a flat pseudoRiemannian metric on ℝ^d of signature (n,n−1). Here, the translational part determines a deformation of the linear part into 𝖯𝖲𝖮(n,n)Hitchin representations and the crucial step is to show that such representations are not Anosov in 𝖯𝖲𝖫(2n,ℝ) with respect to the stabilizer of an nplane. We also prove a negative curvature analogue of the main result, that the action of a surface group on the pseudoRiemannian hyperbolic space of signature (n,n−1) by a 𝖯𝖲𝖮(n,n)Hitchin representation fails to be properly discontinuous.
more »
« less
 Award ID(s):
 1812216
 NSFPAR ID:
 10111998
 Date Published:
 Journal Name:
 Geometric and Functional Analysis
 ISSN:
 1016443X
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Grandoni, Fabrizio ; Herman, Grzegorz ; Sanders, Peter (Ed.)Reliable spanners can withstand huge failures, even when a linear number of vertices are deleted from the network. In case of failures, some of the remaining vertices of a reliable spanner may no longer admit the spanner property, but this collateral damage is bounded by a fraction of the size of the attack. It is known that Ω(nlog n) edges are needed to achieve this strong property, where n is the number of vertices in the network, even in one dimension. Constructions of reliable geometric (1+ε)spanners, for n points in ℝ^d, are known, where the resulting graph has 𝒪(n log n log log⁶n) edges. Here, we show randomized constructions of smaller size spanners that have the desired reliability property in expectation or with good probability. The new construction is simple, and potentially practical  replacing a hierarchical usage of expanders (which renders the previous constructions impractical) by a simple skip list like construction. This results in a 1spanner, on the line, that has linear number of edges. Using this, we present a construction of a reliable spanner in ℝ^d with 𝒪(n log log²n log log log n) edges.more » « less

null (Ed.)Abstract We investigate the Hölder geometry of curves generated by iterated function systems (IFS) in a complete metric space. A theorem of Hata from 1985 asserts that every connected attractor of an IFS is locally connected and pathconnected. We give a quantitative strengthening of Hata’s theorem. First we prove that every connected attractor of an IFS is (1/ s )Hölder pathconnected, where s is the similarity dimension of the IFS. Then we show that every connected attractor of an IFS is parameterized by a (1/ α)Hölder curve for all α > s . At the endpoint, α = s , a theorem of Remes from 1998 already established that connected selfsimilar sets in Euclidean space that satisfy the open set condition are parameterized by (1/ s )Hölder curves. In a secondary result, we show how to promote Remes’ theorem to selfsimilar sets in complete metric spaces, but in this setting require the attractor to have positive s dimensional Hausdorff measure in lieu of the open set condition. To close the paper, we determine sharp Hölder exponents of parameterizations in the class of connected selfaffine BedfordMcMullen carpets and build parameterizations of selfaffine sponges. An interesting phenomenon emerges in the selfaffine setting. While the optimal parameter s for a selfsimilar curve in ℝ n is always at most the ambient dimension n , the optimal parameter s for a selfaffine curve in ℝ n may be strictly greater than n .more » « less

We study a clustering problem where the goal is to maximize the coverage of the input points by k chosen centers. Specifically, given a set of n points P ⊆ ℝ^d, the goal is to pick k centers C ⊆ ℝ^d that maximize the service ∑_{p∈P}φ(𝖽(p,C)) to the points P, where 𝖽(p,C) is the distance of p to its nearest center in C, and φ is a nonincreasing service function φ: ℝ+ → ℝ+. This includes problems of placing k base stations as to maximize the total bandwidth to the clients  indeed, the closer the client is to its nearest base station, the more data it can send/receive, and the target is to place k base stations so that the total bandwidth is maximized. We provide an n^{ε^O(d)} time algorithm for this problem that achieves a (1ε)approximation. Notably, the runtime does not depend on the parameter k and it works for an arbitrary nonincreasing service function φ: ℝ+ → ℝ+.more » « less

null (Ed.)Abstract The duality principle for group representations developed in Dutkay et al. (J Funct Anal 257:1133–1143, 2009), Han and Larson (Bull Lond Math Soc 40:685–695, 2008) exhibits a fact that the wellknown duality principle in Gabor analysis is not an isolated incident but a more general phenomenon residing in the context of group representation theory. There are two other wellknown fundamental properties in Gabor analysis: the biorthogonality and the fundamental identity of Gabor analysis. The main purpose of this this paper is to show that these two fundamental properties remain to be true for general projective unitary group representations. Moreover, we also present a general duality theorem which shows that that mutiframe generators meet superframe generators through a dual commutant pair of group representations. Applying it to the Gabor representations, we obtain that $$\{\pi _{\Lambda }(m, n)g_{1} \oplus \cdots \oplus \pi _{\Lambda }(m, n)g_{k}\}_{m, n \in {\mathbb {Z}}^{d}}$$ { π Λ ( m , n ) g 1 ⊕ ⋯ ⊕ π Λ ( m , n ) g k } m , n ∈ Z d is a frame for $$L^{2}({\mathbb {R}}\,^{d})\oplus \cdots \oplus L^{2}({\mathbb {R}}\,^{d})$$ L 2 ( R d ) ⊕ ⋯ ⊕ L 2 ( R d ) if and only if $$\cup _{i=1}^{k}\{\pi _{\Lambda ^{o}}(m, n)g_{i}\}_{m, n\in {\mathbb {Z}}^{d}}$$ ∪ i = 1 k { π Λ o ( m , n ) g i } m , n ∈ Z d is a Riesz sequence, and $$\cup _{i=1}^{k} \{\pi _{\Lambda }(m, n)g_{i}\}_{m, n\in {\mathbb {Z}}^{d}}$$ ∪ i = 1 k { π Λ ( m , n ) g i } m , n ∈ Z d is a frame for $$L^{2}({\mathbb {R}}\,^{d})$$ L 2 ( R d ) if and only if $$\{\pi _{\Lambda ^{o}}(m, n)g_{1} \oplus \cdots \oplus \pi _{\Lambda ^{o}}(m, n)g_{k}\}_{m, n \in {\mathbb {Z}}^{d}}$$ { π Λ o ( m , n ) g 1 ⊕ ⋯ ⊕ π Λ o ( m , n ) g k } m , n ∈ Z d is a Riesz sequence, where $$\pi _{\Lambda }$$ π Λ and $$\pi _{\Lambda ^{o}}$$ π Λ o is a pair of Gabor representations restricted to a time–frequency lattice $$\Lambda $$ Λ and its adjoint lattice $$\Lambda ^{o}$$ Λ o in $${\mathbb {R}}\,^{d}\times {\mathbb {R}}\,^{d}$$ R d × R d .more » « less