skip to main content

Title: Trilateration Using Unlabeled Path or Loop Lengths

Let$$\textbf{p}$$pbe a configuration ofnpoints in$$\mathbb R^d$$Rdfor somenand some$$d \ge 2$$d2. Each pair of points defines an edge, which has a Euclidean length in the configuration. A path is an ordered sequence of the points, and a loop is a path that begins and ends at the same point. A path or loop, as a sequence of edges, also has a Euclidean length, which is simply the sum of its Euclidean edge lengths. We are interested in reconstructing$$\textbf{p}$$pgiven a set of edge, path and loop lengths. In particular, we consider the unlabeled setting where the lengths are given simply as a set of real numbers, and are not labeled with the combinatorial data describing which paths or loops gave rise to these lengths. In this paper, we study the question of when$$\textbf{p}$$pwill be uniquely determined (up to an unknowable Euclidean transform) from some given set of path or loop lengths through an exhaustive trilateration process. Such a process has already been used for the simpler problem of reconstruction using unlabeled edge lengths. This paper also provides a complete proof that this process must work in that edge-setting when given a sufficiently rich set of edge measurements and assuming that$$\textbf{p}$$pis generic.

more » « less
Author(s) / Creator(s):
; ; ;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Discrete & Computational Geometry
Medium: X Size: p. 399-441
["p. 399-441"]
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    The notion of generalized rank in the context of multiparameter persistence has become an important ingredient for defining interesting homological structures such as generalized persistence diagrams. However, its efficient computation has not yet been studied in the literature. We show that the generalized rank over a finite intervalIof a$$\textbf{Z}^2$$Z2-indexed persistence moduleMis equal to the generalized rank of the zigzag module that is induced on a certain path inItracing mostly its boundary. Hence, we can compute the generalized rank ofMoverIby computing the barcode of the zigzag module obtained by restricting to that path. IfMis the homology of a bifiltrationFof$$t$$tsimplices (while accounting for multi-criticality) andIconsists of$$t$$tpoints, this computation takes$$O(t^\omega )$$O(tω)time where$$\omega \in [2,2.373)$$ω[2,2.373)is the exponent of matrix multiplication. We apply this result to obtain an improved algorithm for the following problem. Given a bifiltration inducing a moduleM, determine whetherMis interval decomposable and, if so, compute all intervals supporting its indecomposable summands.

    more » « less
  2. Abstract

    Consider two half-spaces$$H_1^+$$H1+and$$H_2^+$$H2+in$${\mathbb {R}}^{d+1}$$Rd+1whose bounding hyperplanes$$H_1$$H1and$$H_2$$H2are orthogonal and pass through the origin. The intersection$${\mathbb {S}}_{2,+}^d:={\mathbb {S}}^d\cap H_1^+\cap H_2^+$$S2,+d:=SdH1+H2+is a spherical convex subset of thed-dimensional unit sphere$${\mathbb {S}}^d$$Sd, which contains a great subsphere of dimension$$d-2$$d-2and is called a spherical wedge. Choosenindependent random points uniformly at random on$${\mathbb {S}}_{2,+}^d$$S2,+dand consider the expected facet number of the spherical convex hull of these points. It is shown that, up to terms of lower order, this expectation grows like a constant multiple of$$\log n$$logn. A similar behaviour is obtained for the expected facet number of a homogeneous Poisson point process on$${\mathbb {S}}_{2,+}^d$$S2,+d. The result is compared to the corresponding behaviour of classical Euclidean random polytopes and of spherical random polytopes on a half-sphere.

    more » « less
  3. Abstract

    It has been recently established in David and Mayboroda (Approximation of green functions and domains with uniformly rectifiable boundaries of all dimensions.arXiv:2010.09793) that on uniformly rectifiable sets the Green function is almost affine in the weak sense, and moreover, in some scenarios such Green function estimates are equivalent to the uniform rectifiability of a set. The present paper tackles a strong analogue of these results, starting with the “flagship degenerate operators on sets with lower dimensional boundaries. We consider the elliptic operators$$L_{\beta ,\gamma } =- {\text {div}}D^{d+1+\gamma -n} \nabla $$Lβ,γ=-divDd+1+γ-nassociated to a domain$$\Omega \subset {\mathbb {R}}^n$$ΩRnwith a uniformly rectifiable boundary$$\Gamma $$Γof dimension$$d < n-1$$d<n-1, the now usual distance to the boundary$$D = D_\beta $$D=Dβgiven by$$D_\beta (X)^{-\beta } = \int _{\Gamma } |X-y|^{-d-\beta } d\sigma (y)$$Dβ(X)-β=Γ|X-y|-d-βdσ(y)for$$X \in \Omega $$XΩ, where$$\beta >0$$β>0and$$\gamma \in (-1,1)$$γ(-1,1). In this paper we show that the Green functionGfor$$L_{\beta ,\gamma }$$Lβ,γ, with pole at infinity, is well approximated by multiples of$$D^{1-\gamma }$$D1-γ, in the sense that the function$$\big | D\nabla \big (\ln \big ( \frac{G}{D^{1-\gamma }} \big )\big )\big |^2$$|D(ln(GD1-γ))|2satisfies a Carleson measure estimate on$$\Omega $$Ω. We underline that the strong and the weak results are different in nature and, of course, at the level of the proofs: the latter extensively used compactness arguments, while the present paper relies on some intricate integration by parts and the properties of the “magical distance function from David et al. (Duke Math J, to appear).

    more » « less
  4. Abstract

    Let Kbe a finite simplicial, cubical, delta or CW complex. The persistence map $$\textrm{PH}$$PHtakes a filter $$f:K\rightarrow \mathbb {R}$$f:KRas input and returns the barcodes of the sublevel set persistent homology of fin each dimension. We address the inverse problem: given target barcodes D, computing the fiber $$\textrm{PH}^{-1}(D)$$PH-1(D). For this, we use the fact that $$\textrm{PH}^{-1}(D)$$PH-1(D)decomposes as a polyhedral complex when Kis a simplicial complex, and we generalise this result to arbitrary based chain complexes. We then design and implement a depth-first search that recovers the polytopes forming the fiber $$\textrm{PH}^{-1}(D)$$PH-1(D). As an application, we solve a corpus of 120 sample problems, providing a first insight into the statistical structure of these fibers, for general CW complexes.

    more » « less
  5. Abstract

    A classical parking function of lengthnis a list of positive integers$$(a_1, a_2, \ldots , a_n)$$(a1,a2,,an)whose nondecreasing rearrangement$$b_1 \le b_2 \le \cdots \le b_n$$b1b2bnsatisfies$$b_i \le i$$bii. The convex hull of all parking functions of lengthnis ann-dimensional polytope in$${\mathbb {R}}^n$$Rn, which we refer to as the classical parking function polytope. Its geometric properties have been explored in Amanbayeva and Wang (Enumer Combin Appl 2(2):Paper No. S2R10, 10, 2022) in response to a question posed by Stanley (Amer Math Mon 127(6):563–571, 2020). We generalize this family of polytopes by studying the geometric properties of the convex hull of$${\textbf{x}}$$x-parking functions for$${\textbf{x}}=(a,b,\dots ,b)$$x=(a,b,,b), which we refer to as$${\textbf{x}}$$x-parking function polytopes. We explore connections between these$${\textbf{x}}$$x-parking function polytopes, the Pitman–Stanley polytope, and the partial permutahedra of Heuer and Striker (SIAM J Discrete Math 36(4):2863–2888, 2022). In particular, we establish a closed-form expression for the volume of$${\textbf{x}}$$x-parking function polytopes. This allows us to answer a conjecture of Behrend et al. (2022) and also obtain a new closed-form expression for the volume of the convex hull of classical parking functions as a corollary.

    more » « less