亚洲男人的天堂2018av,欧美草比,久久久久久免费视频精选,国色天香在线看免费,久久久久亚洲av成人片仓井空

We study the $k$-th nearest neighbor distance function from a finite point-set in $\mathbb{R}^d$. We provide a Morse theoretic framework to analyze the sub-level set topology. In particular, we present a simple combinatorial-geometric characterization for critical points and their indices, along with detailed information about the possible changes in homology at the critical levels. We conclude by computing the expected number of critical points for a homogeneous Poisson process. Our results deliver significant insights and tools for the analysis of persistent homology in order-$k$ Delaunay mosaics, and random $k$-fold coverage.

For an n-vertex directed graph $G = (V,E)$, a $\beta$-\emph{shortcut set} $H$ is a set of additional edges $H \subseteq V \times V$ such that $G \cup H$ has the same transitive closure as $G$, and for every pair $u,v \in V$, there is a $uv$-path in $G \cup H$ with at most $\beta$ edges. A natural generalization of shortcut sets to distances is a $(\beta,\epsilon)$-\emph{hopset} $H \subseteq V \times V$, where the requirement is that $H$ and $G \cup H$ have the same shortest-path distances, and for every $u,v \in V$, there is a $(1+\epsilon)$-approximate shortest path in $G \cup H$ with at most $\beta$ edges. There is a large literature on the tradeoff between the size of a shortcut set / hopset and the value of $\beta$. We highlight the most natural point on this tradeoff: what is the minimum value of $\beta$, such that for any graph $G$, there exists a $\beta$-shortcut set (or a $(\beta,\epsilon)$-hopset) with $O(n)$ edges? Not only is this a natural structural question in its own right, but shortcuts sets / hopsets form the core of many distributed, parallel, and dynamic algorithms for reachability / shortest paths. Until very recently the best known upper bound was a folklore construction showing $\beta = O(n^{1/2})$, but in a breakthrough result Kogan and Parter [SODA 2022] improve this to $\beta = \tilde{O}(n^{1/3})$ for shortcut sets and $\tilde{O}(n^{2/5})$ for hopsets. Our result is to close the gap between shortcut sets and hopsets. That is, we show that for any graph $G$ and any fixed $\epsilon$ there is a $(\tilde{O}(n^{1/3}),\epsilon)$ hopset with $O(n)$ edges. More generally, we achieve a smooth tradeoff between hopset size and $\beta$ which exactly matches the tradeoff of Kogan and Parter for shortcut sets (up to polylog factors). Using a very recent black-box reduction of Kogan and Parter, our new hopset implies improved bounds for approximate distance preservers.

Let $P$ be a set of $m$ points in ${\mathbb R}^2$, let $\Sigma$ be a set of $n$ semi-algebraic sets of constant complexity in ${\mathbb R}^2$, let $(S,+)$ be a semigroup, and let $w: P \rightarrow S$ be a weight function on the points of $P$. We describe a randomized algorithm for computing $w(P\cap\sigma)$ for every $\sigma\in\Sigma$ in overall expected time $O^*\bigl( m^{\frac{2s}{5s-4}}n^{\frac{5s-6}{5s-4}} + m^{2/3}n^{2/3} + m + n \bigr)$, where $s>0$ is a constant that bounds the maximum complexity of the regions of $\Sigma$, and where the $O^*(\cdot)$ notation hides subpolynomial factors. For $s\ge 3$, surprisingly, this bound is smaller than the best-known bound for answering $m$ such queries in an on-line manner. The latter takes $O^*(m^{\frac{s}{2s-1}}n^{\frac{2s-2}{2s-1}}+m+n)$ time. Let $\Phi: \Sigma \times P \rightarrow \{0,1\}$ be the Boolean predicate (of constant complexity) such that $\Phi(\sigma,p) = 1$ if $p\in\sigma$ and $0$ otherwise, and let $\Sigma\mathop{\Phi} P = \{ (\sigma,p) \in \Sigma\times P \mid \Phi(\sigma,p)=1\}$. Our algorithm actually computes a partition ${\mathcal B}_\Phi$ of $\Sigma\mathop{\Phi} P$ into bipartite cliques (bicliques) of size (i.e., sum of the sizes of the vertex sets of its bicliques) $O^*\bigl( m^{\frac{2s}{5s-4}}n^{\frac{5s-6}{5s-4}} + m^{2/3}n^{2/3} + m + n \bigr)$. It is straightforward to compute $w(P\cap\sigma)$ for all $\sigma\in \Sigma$ from ${\mathcal B}_\Phi$. Similarly, if $\eta: \Sigma \rightarrow S$ is a weight function on the regions of $\Sigma$, $\sum_{\sigma\in \Sigma: p \in \sigma} \eta(\sigma)$, for every point $p\in P$, can be computed from ${\mathcal B}_\Phi$ in a straightforward manner. A recent work of Chan et al. solves the online version of this dual point enclosure problem within the same performance bound as our off-line solution. We also mention a few other applications of computing ${\mathcal B}_\Phi$.

If $G$ is a group, we say a subset $S$ of $G$ is product-free if the equation $xy=z$ has no solutions with $x,y,z \in S$. For $D \in \mathbb{N}$, a group $G$ is said to be $D$-quasirandom if the minimal dimension of a nontrivial complex irreducible representation of $G$ is at least $D$. Gowers showed that in a $D$-quasirandom finite group $G$, the maximal size of a product-free set is at most $|G|/D^{1/3}$. This disproved a longstanding conjecture of Babai and S\'os from 1985. For the special unitary group, $G=SU(n)$, Gowers observed that his argument yields an upper bound of $n^{-1/3}$ on the measure of a measurable product-free subset. In this paper, we improve Gowers' upper bound to $\exp(-cn^{1/3})$, where $c>0$ is an absolute constant. In fact, we establish something stronger, namely, product-mixing for measurable subsets of $SU(n)$ with measure at least $\exp(-cn^{1/3})$; for this product-mixing result, the $n^{1/3}$ in the exponent is sharp. Our approach involves introducing novel hypercontractive inequalities, which imply that the non-Abelian Fourier spectrum of the indicator function of a small set concentrates on high-dimensional irreducible representations. Our hypercontractive inequalities are obtained via methods from representation theory, harmonic analysis, random matrix theory and differential geometry. We generalize our hypercontractive inequalities from $SU(n)$ to an arbitrary $D$-quasirandom compact connected Lie group for $D$ at least an absolute constant, thereby extending our results on product-free sets to such groups. We also demonstrate various other applications of our inequalities to geometry (viz., non-Abelian Brunn-Minkowski type inequalities), mixing times, and the theory of growth in compact Lie groups.

Given a set of $n$ sites from $\mathbb{R}^d$, each having some positive weight factor, the Multiplicatively Weighted Voronoi Diagram is a subdivision of space that associates each cell to the site whose weighted Euclidean distance is minimal for all points in the cell. We give novel approximation algorithms that output a cube-based subdivision such that the weighted distance of a point with respect to the associated site is at most $(1+\varepsilon)$ times the minimum weighted distance, for any fixed parameter $\varepsilon \in (0,1)$. The diagram size is $O_d(n \log(1/\varepsilon)/\varepsilon^{d-1})$ and the construction time is within an $O_D(\log(n)/\varepsilon^{(d+5)/2})$-factor of the size bound. We also prove a matching lower bound for the size, showing that the proposed method is the first to achieve \emph{optimal size}, up to $\Theta(1)^d$-factors. In particular, the obscure $\log(1/\varepsilon)$ factor is unavoidable. As a by-product, we obtain a factor $d^{O(d)}$ improvement in size for the unweighted case and $O(d \log(n) + d^2 \log(1/\varepsilon))$ point-location time in the subdivision, improving the known query bound by one $d$-factor. The key ingredients of our approximation algorithms are the study of convex regions that we call cores, an adaptive refinement algorithm to obtain optimal size, and a novel notion of \emph{bisector coresets}, which may be of independent interest. In particular, we show that coresets with $O_d(1/\varepsilon^{(d+3)/2})$ worst-case size can be computed in near-linear time.

We consider metrical task systems on general metric spaces with $n$ points, and show that any fully randomized algorithm can be turned into a randomized algorithm that uses only $2\log n$ random bits, and achieves the same competitive ratio up to a factor $2$. This provides the first order-optimal barely random algorithms for metrical task systems, i.e. which use a number of random bits that does not depend on the number of requests addressed to the system. We put forward an equivalent view that we call collective metrical task systems where $k$ agents in a metrical task system team up, and suffer the average cost paid by each agent. Our results imply that such team can be $O(\log n^2)$-competitive, as soon as $k\geq n^2$ (in comparison, a single agent is $\Omega(n)$-competitive at best). We discuss implications on various aspects of online decision making such as: distributed systems, transaction costs, and advice complexity, suggesting broad applicability.

We consider the elastic scattering problem by multiple disjoint arcs or \emph{cracks} in two spatial dimensions. A key aspect of our approach lies in the parametric description of each arc's shape, which is controlled by a potentially high-dimensional, possibly countably infinite, set of parameters. We are interested in the efficient approximation of the parameter-to-solution map employing model order reduction techniques, specifically the reduced basis method. Initially, we utilize boundary potentials to transform the boundary value problem, originally posed in an unbounded domain, into a system of boundary integral equations set on the parametrically defined open arcs. Our aim is to construct a rapid surrogate for solving this problem. To achieve this, we adopt the two-phase paradigm of the reduced basis method. In the offline phase, we compute solutions for this problem under the assumption of complete decoupling among arcs for various shapes. Leveraging these high-fidelity solutions and Proper Orthogonal Decomposition (POD), we construct a reduced-order basis tailored to the single arc problem. Subsequently, in the online phase, when computing solutions for the multiple arc problem with a new parametric input, we utilize the aforementioned basis for each individual arc. To expedite the offline phase, we employ a modified version of the Empirical Interpolation Method (EIM) to compute a precise and cost-effective affine representation of the interaction terms between arcs. Finally, we present a series of numerical experiments demonstrating the advantages of our proposed method in terms of both accuracy and computational efficiency.

Given a simple undirected graph $G$, a quasi-clique is a subgraph of $G$ whose density is at least $\gamma$ $(0 < \gamma \leq 1)$. Finding a maximum quasi-clique has been addressed from two different perspectives: $i)$ maximizing vertex cardinality for a given edge density; and $ii)$ maximizing edge density for a given vertex cardinality. However, when no a priori preference information about cardinality and density is available, a more natural approach is to consider the problem from a multiobjective perspective. We introduce the Multiobjective Quasi-clique Problem (MOQC), which aims to find a quasi-clique by simultaneously maximizing both vertex cardinality and edge density. To efficiently address this problem, we explore the relationship among MOQC, its single-objective counterpart problems, and a biobjective optimization problem, along with several properties of the MOQC problem and quasi-cliques. We propose a baseline approach using $\varepsilon$-constraint scalarization and introduce a Two-phase strategy, which applies a dichotomic search based on weighted sum scalarization in the first phase and an $\varepsilon$-constraint methodology in the second phase. Additionally, we present a Three-phase strategy that combines the dichotomic search used in Two-phase with a vertex-degree-based local search employing novel sufficient conditions to assess quasi-clique efficiency, followed by an $\varepsilon$-constraint in a final stage. Experimental results on real-world sparse graphs indicate that the integrated use of dichotomic search and local search, together with mechanisms to assess quasi-clique efficiency, makes the Three-phase strategy an effective approach for solving the MOQC problem in terms of running time and ability to produce new efficient quasi-cliques.

A new $H(\textrm{divdiv})$-conforming finite element is presented, which avoids the need for super-smoothness by redistributing the degrees of freedom to edges and faces. This leads to a hybridizable mixed method with superconvergence for the biharmonic equation. Moreover, new finite element divdiv complexes are established. Finally, new weak Galerkin and $C^0$ discontinuous Galerkin methods for the biharmonic equation are derived.

A partition $\mathcal{P}$ of a weighted graph $G$ is $(\sigma,\tau,\Delta)$-sparse if every cluster has diameter at most $\Delta$, and every ball of radius $\Delta/\sigma$ intersects at most $\tau$ clusters. Similarly, $\mathcal{P}$ is $(\sigma,\tau,\Delta)$-scattering if instead for balls we require that every shortest path of length at most $\Delta/\sigma$ intersects at most $\tau$ clusters. Given a graph $G$ that admits a $(\sigma,\tau,\Delta)$-sparse partition for all $\Delta>0$, Jia et al. [STOC05] constructed a solution for the Universal Steiner Tree problem (and also Universal TSP) with stretch $O(\tau\sigma^2\log_\tau n)$. Given a graph $G$ that admits a $(\sigma,\tau,\Delta)$-scattering partition for all $\Delta>0$, we construct a solution for the Steiner Point Removal problem with stretch $O(\tau^3\sigma^3)$. We then construct sparse and scattering partitions for various different graph families, receiving many new results for the Universal Steiner Tree and Steiner Point Removal problems.