Abstract We consider the problem of digitalizing Euclidean segments. Specifically, we look for a constructive method to connect any two points in $$\mathbb {Z}^d$$ Z d . The construction must be consistent (that is, satisfy the natural extension of the Euclidean axioms) while resembling them as much as possible. Previous work has shown asymptotically tight results in two dimensions with $$\varTheta (\log N)$$ Θ ( log N ) error, where resemblance between segments is measured with the Hausdorff distance, and N is the $$L_1$$ L 1 distance between the two points. This construction was considered tight because of a $$\varOmega (\log N)$$ Ω ( log N ) lower bound that applies to any consistent construction in $$\mathbb {Z}^2$$ Z 2 . In this paper we observe that the lower bound does not directly extend to higher dimensions. We give an alternative argument showing that any consistent construction in d dimensions must have $$\varOmega (\log ^{1/(d-1)}\!N)$$ Ω ( log 1 / ( d - 1 ) N ) error. We tie the error of a consistent construction in high dimensions to the error of similar weak constructions in two dimensions (constructions for which some points need not satisfy all the axioms). This not only opens the possibility for having constructions with $$o(\log N)$$ o ( log N ) error in high dimensions, but also opens up an interesting line of research in the tradeoff between the number of axiom violations and the error of the construction. A side result, that we find of independent interest, is the introduction of the bichromatic discrepancy: a natural extension of the concept of discrepancy of a set of points. In this paper, we define this concept and extend known results to the chromatic setting.

We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of n vertices and h holes. We introduce a graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in O ( min ⁡ ( n ω , n 2 + n h log ⁡ h + χ 2 ) ) time, where ω < 2.373 denotes the matrix multiplication exponent and χ ∈ Ω ( n ) ∩ O ( n 2 ) is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in O ( n 2 log ⁡ n ) time.

Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances $x_1,\cdots,x_n$ follow some unknown \emph{product distribution}. That is, $x_i$ comes from a fixed unknown distribution $\mathsf{D}_i$, and the $x_i$'s are drawn independently. After spending $O(n^{1+\varepsilon})$ time in a learning phase, the subsequent expected running time is $O((n+ H)/\varepsilon)$, where $H \in \{H_\mathrm{S},H_\mathrm{DT}\}$, and $H_\mathrm{S}$ and $H_\mathrm{DT}$ are the entropies of the distributions of the sorting and DT output, respectively. In this paper, we allow dependence among the $x_i$'s under the \emph{group product distribution}. There is a hidden partition of $[1,n]$ into groups; the $x_i$'s in the $k$-th group are fixed unknown functions of the same hidden variable $u_k$; and the $u_k$'s are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map $u_k$ to $x_i$'s are well-behaved. After an $O(\mathrm{poly}(n))$-time training phase, we achieve $O(n + H_\mathrm{S})$ and $O(nα(n) + H_\mathrm{DT})$ expected running times for sorting and DT, respectively, where $α(\cdot)$ is the inverse Ackermann function.

We consider the problem of digitalizing Euclidean segments. Specifically, we look for a constructive method to connect any two points in ℤ^d. The construction must be consistent (that is, satisfy the natural extension of the Euclidean axioms) while resembling them as much as possible. Previous work has shown asymptotically tight results in two dimensions with Θ(log N) error, where resemblance between segments is measured with the Hausdorff distance, and N is the L₁ distance between the two points. This construction was considered tight because of a Ω(log N) lower bound that applies to any consistent construction in ℤ². In this paper we observe that the lower bound does not directly extend to higher dimensions. We give an alternative argument showing that any consistent construction in d dimensions must have Ω(log^{1/(d-1)} N) error. We tie the error of a consistent construction in high dimensions to the error of similar weak constructions in two dimensions (constructions for which some points need not satisfy all the axioms). This not only opens the possibility for having constructions with o(log N) error in high dimensions, but also opens up an interesting line of research in the tradeoff between the number of axiom violations and the error of the construction. In order to show our lower bound, we also consider a colored variation of the concept of discrepancy of a set of points that we find of independent interest.

The classic Ham-Sandwich theorem states that for any $d$ measurable sets in $\mathbb{R}^d$, there is a hyperplane that bisects them simultaneously. An extension by Bárány, Hubard, and Jerónimo [DCG 2008] states that if the sets are convex and \emph{well-separated}, then for any given $α_1, \dots, α_d \in [0, 1]$, there is a unique oriented hyperplane that cuts off a respective fraction $α_1, \dots, α_d$ from each set. Steiger and Zhao [DCG 2010] proved a discrete analogue of this theorem, which we call the \emph{$α$-Ham-Sandwich theorem}. They gave an algorithm to find the hyperplane in time $O(n (\log n)^{d-3})$, where $n$ is the total number of input points. The computational complexity of this search problem in high dimensions is open, quite unlike the complexity of the Ham-Sandwich problem, which is now known to be PPA-complete (Filos-Ratsikas and Goldberg [STOC 2019]). Recently, Fearley, Gordon, Mehta, and Savani [ICALP 2019] introduced a new sub-class of CLS (Continuous Local Search) called \emph{Unique End-of-Potential Line} (UEOPL). This class captures problems in CLS that have unique solutions. We show that for the $α$-Ham-Sandwich theorem, the search problem of finding the dividing hyperplane lies in UEOPL. This gives the first non-trivial containment of the problem in a complexity class and places it in the company of classic search problems such as finding the fixed point of a contraction map, the unique sink orientation problem and the $P$-matrix linear complementarity problem.

We consider the problem of digitalizing Euclidean line segments from $\mathbb{R}^d$ to $\mathbb{Z}^d$. Christ, Pálvölgyi, and Stojaković, [ Discrete Comput. Geom., 47 (2012), pp. 691--710] showed how to construct a set of consistent digital segments (CDS) for $d=2$: a collection of segments connecting any two points in $\mathbb{Z}^2$ that satisfies the natural extension of the Euclidean axioms to $\mathbb{Z}^d$. In this paper we study the construction of CDSs in higher dimensions. We extend some of their results to higher dimensions. Specifically we show that any total order can be used to create a set of consistent digital rays CDR in $\mathbb{Z}^d$ (a set of rays emanating from a fixed point $p$ that satisfies the extension of the Euclidean axioms). Then we use the same approach to create a CDS in $\mathbb{Z}^d$ and observe that it only works in some cases. We fully characterize for which total orders the construction is consistent (and thus gives a CDS). In particular, this positively answers the question posed by Christ and co-authors.

We consider the problem of digitalizing Euclidean line segments from R^d to Z^d. Christ {et al.} (DCG, 2012) showed how to construct a set of {consistent digital segments} (CDS) for d=2: a collection of segments connecting any two points in Z^2 that satisfies the natural extension of the Euclidean axioms to Z^d. In this paper we study the construction of CDSs in higher dimensions. We show that any total order can be used to create a set of {consistent digital rays} CDR in Z^d (a set of rays emanating from a fixed point p that satisfies the extension of the Euclidean axioms). We fully characterize for which total orders the construction holds and study their Hausdorff distance, which in particular positively answers the question posed by Christ {et al.}.

We consider the problem of routing a data packet through the visibility graph of a polygonal domain P with n vertices and h holes. We may preprocess P to obtain a label and a routing table for each vertex. Then, we must be able to route a data packet between any two vertices p and q of P , where each step must use only the label of the target node q and the routing table of the current node. For any fixed eps > 0, we pre ent a routing scheme that always achieves a routing path that exceeds the shortest path by a factor of at most 1 + eps. The labels have O(log n) bits, and the routing tables are of size O((eps^{-1} + h) log n). The preprocessing time is O(n^2 log n + hn^2 + eps^{-1}hn). It can be improved to O(n 2 + eps^{-1}n) for simple polygons.

Let P be a dense set of points sampled from an m-dimensional compact smooth manifold Σ in ℝd. We show how to construct an implicit function φ : ℝd → ℝd–m from P so that the zero-set Sφ of φ contains a homeomorphic approximation of Σ. The Hausdorff distance between Σ and this homeomorphic approximation is at most ∊τ for any fixed τ < 2. Moreover, for every point × at distance ∊τ or less from Σ, the normal space of Sφ at × makes an O(∊(τ–1)/2) angle with the normal space of Σ at the point nearest to ×. The function φ has local support, which makes local homeomorphic reconstruction possible without a complete sampling.

We present a novel approach to estimate the dimension m of an unknown manifold M ⊂ ℝ with positive reach from a set of point samples P ⊆ M. It works by analyzing the shape of simplices formed by point samples. Suppose that P is drawn from M according to a Poisson process with an unknown parameter λ. Let k be some fixed positive integer. When λ is large enough, we prove that the dimension can be correctly output in O(kd|P|1+1/k) time with probability greater than 1 − 2−-k. We experimented with a practical variant and showed that its performance is competitive with several previous methods.