搜索结果：empty

In the paper, we consider the problem of searching for the Largest empty rectangle in a 2D map, and the one-dimensional version of the problem is the problem of searching for the largest empty segment. We present a quantum algorithm for the Largest Empty Square problem and the Largest Empty Rectangle of a fixed width $d$ for $n\times n$-rectangular map. Query complexity of the algorithm is $\tilde{O}(n^{1.5})$ for the square case, and $\tilde{O}(n\sqrt{d})$ for the rectangle with a fixed width $d$ case, respectively. At the same time, the lower bounds for the classical case are $Ω(n^2)$, and $Ω(nd)$, respectively. The Quantum algorithm for the one-dimensional version of the problem has $O(\sqrt{n}\log n\log\log n)$ query complexity. The quantum lower bound for the problem is $Ω(\sqrt{n})$ which is almost equal to the upper bound up to a log factor. The classical lower bound is $Ω(n)$. So, we obtain the quadratic speed-up for the problem.

Let $S$ be a set of $n$ points in general position in the plane. The Second Selection Lemma states that for any family of $Θ(n^3)$ triangles spanned by $S$, there exists a point of the plane that lies in a constant fraction of them. For families of $Θ(n^{3-α})$ triangles, with $0\le α\le 1$, there might not be a point in more than $Θ(n^{3-2α})$ of those triangles. An empty triangle of $S$ is a triangle spanned by $S$ not containing any point of $S$ in its interior. Bárány conjectured that there exist an edge spanned by $S$ that is incident to a super constant number of empty triangles of $S$. The number of empty triangles of $S$ might be $O(n^2)$; in such a case, on average, every edge spanned by $S$ is incident to a constant number of empty triangles. The conjecture of Bárány suggests that for the class of empty triangles the above upper bound might not hold. In this paper we show that, somewhat surprisingly, the above upper bound does in fact hold for empty triangles. Specifically, we show that for any integer $n$ and real number $0\leq α\leq 1$ there exists a point set of size $n$ with $Θ(n^{3-α})$ empty triangles such that any point of the plane is only in $O(n^{3-2α})$ empty t

We are interested in algebraic properties of empty lattice simplices $Δ$, that is, $d$-dimensional lattice polytopes containing exactly $d+1$ points of the integer lattice $\mathbb{Z}^d$. The cyclicity rank of $Δ$ is the minimal number of cyclic subgroups that the quotient group of $Δ$ splits into. It is known that up to dimension $d \leq 4$, every empty lattice $d$-simplex is cyclic, meaning that its cyclicity rank is at most $1$. We determine the maximal possible cyclicity rank of an empty lattice $d$-simplex for dimensions $d \leq 8$, and determine the asymptotics of this number up to a logarithmic term.

A recent breakthrough in computer-assisted mathematics showed that every set of $30$ points in the plane in general position (i.e., without three on a common line) contains an empty convex hexagon, thus closing a line of research dating back to the 1930s. Through a combination of geometric insights and automated reasoning techniques, Heule and Scheucher constructed a CNF formula $φ_n$, with $O(n^4)$ clauses, whose unsatisfiability implies that no set of $n$ points in general position can avoid an empty convex hexagon. An unsatisfiability proof for n = 30 was then found with a SAT solver using 17300 CPU hours of parallel computation, thus implying that the empty hexagon number h(6) is equal to 30. In this paper, we formalize and verify this result in the Lean theorem prover. Our formalization covers discrete computational geometry ideas and SAT encoding techniques that have been successfully applied to similar Erdős-Szekeres-type problems. In particular, our framework provides tools to connect standard mathematical objects to propositional assignments, which represents a key step towards the formal verification of other SAT-based mathematical results. Overall, we hope that this work

Compactness in deep learning can be critical to a model's viability in low-resource applications, and a common approach to extreme model compression is quantization. We consider Iterative Product Quantization (iPQ) with Quant-Noise to be state-of-the-art in this area, but this quantization framework suffers from preventable inference quality degradation due to prevalent empty clusters. In this paper, we propose several novel enhancements aiming to improve the accuracy of iPQ with Quant-Noise by focusing on resolving empty clusters. Our contribution, which we call Partitioning-Guided k-means (PG k-means), is a heavily augmented k-means implementation composed of three main components. First, we propose a partitioning-based pre-assignment strategy that ensures no initial empty clusters and encourages an even weight-to-cluster distribution. Second, we propose an empirically superior empty cluster resolution heuristic executed via cautious partitioning of large clusters. Finally, we construct an optional optimization step that consolidates intuitively dense clusters of weights to ensure shared representation. The proposed approach consistently reduces the number of empty clusters in iP

Given a set $P$ of $n$ points in the plane, in general position, denote by $N_Δ(P)$ the number of empty triangles with vertices in $P$. In this paper we investigate by how much $N_Δ(P)$ changes if a point $x$ is removed from $P$. By constructing a graph $G_P(x)$ based on the arrangement of the empty triangles incident on $x$, we transform this geometric problem to the problem of counting triangles in the graph $G_P(x)$. We study properties of the graph $G_P(x)$ and, in particular, show that it is kite-free. This relates the growth rate of the number of empty triangles to the famous Ruzsa-Szemerédi problem.

For the Iwahori-Hecke algebras of type $A$, James and Mathas proved a theorem which relates $v$-decomposition numbers for different values of $e$, by adding empty runners to the James' abacus display. This result is often referred to as the empty runner removal theorem. In this paper, we extend this theorem to the Ariki-Koike algebras, establishing a similar relationship for the $v$-decomposition numbers.

We introduce a new approach for the adaptation of the Maximal Internal Envelope method, extended to address the Largest Empty Sphere problem within unstructured 3D point clouds. We explore the identification of the Largest Empty Sphere by computing Convex Hull vertices and employing a Voidness Score based on Minimal Distance Scoring for optimal segment selection. The integration of Delaunay triangulation and Voronoi diagrams facilitates the initial identification of potential Largest Empty Sphere candidates. Our analysis reveals the method's efficacy and efficiency, often locating the Largest Empty Sphere in initial computational stages, suggesting a lower complexity than initially projected.

Consider a class of simplices defined by systems $A x \leq b$ of linear inequalities with $Δ$-modular matrices. A matrix is called $Δ$-modular, if all its rank-order sub-determinants are bounded by $Δ$ in an absolute value. In our work we call a simplex $Δ$-modular, if it can be defined by a system $A x \leq b$ with a $Δ$-modular matrix $A$. And we call a simplex empty, if it contains no points with integer coordinates. In literature, a simplex is called lattice-simplex, if all its vertices have integer coordinates. And a lattice-simplex called empty, if it contains no points with integer coordinates excluding its vertices. Recently, assuming that $Δ$ is fixed, it was shown that the number of $Δ$-modular empty simplices modulo the unimodular equivalence relation is bounded by a polynomial on dimension. We show that the analogous fact holds for the class of $Δ$-modular empty lattice-simplices. As the main result, assuming again that the value of the parameter $Δ$ is fixed, we show that all unimodular equivalence classes of simplices of the both types can be enumerated by a polynomial-time algorithm. As the secondary result, we show the existence of a polynomial-time algorithm for th

A lattice $d$-simplex is the convex hull of $d+1$ affinely independent integer points in ${\mathbb R}^d$. It is called empty if it contains no lattice point apart of its $d+1$ vertices. The classification of empty $3$-simplices is known since 1964 (White), based on the fact that they all have width one. But for dimension $4$ no complete classification is known. Haase and Ziegler (2000) enumerated all empty $4$-simplices up to determinant 1000 and based on their results conjectured that after determinant $179$ all empty $4$-simplices have width one or two. We prove this conjecture as follows: - We show that no empty $4$-simplex of width three or more can have determinant greater than 5058, by combining the recent classification of hollow 3-polytopes (Averkov, Krümpelmann and Weltge, 2017) with general methods from the geometry of numbers. - We continue the computations of Haase and Ziegler up to determinant 7600, and find that no new $4$-simplices of width larger than two arise. In particular, we give the whole list of empty $4$-simplices of width larger than two, which is as computed by Haase and Ziegler: There is a single empty $4$-simplex of width four (of determinant 101), and 1

Let $P$ be a $2n$-point set in the plane that is in general position. We prove that every red-blue bipartition of $P$ into $R$ and $B$ with $|R| = |B| = n$ generates $Ω(n^{3/2})$ red-red-blue empty triangles.

I discuss empty space, as it appears in the physical foundations of relativistic field theories and in the semiclassical study of isolated systems. Of particular interest is the relationship between empirical measurements of the cosmological constant and the question of appropriate representation of empty space by spacetimes, or models of general relativity. Also considered is a speculative move that shows up in one corner of quantum gravity research. In pursuit of holographic quantum cosmology given a positive cosmological constant, there is evidently some freedom available for theoretical physicists to pick between two physically inequivalent spacetime representations of empty space, moving forward: de Sitter spacetime or its 'elliptic' cousin.

A gas in a box is perhaps the most important model system studied in thermodynamics and statistical mechanics. Usually, studies focus on the gas, whereas the box merely serves as an idealized confinement. The present article focuses on the box as the central object and develops a thermodynamic theory by treating the geometric degrees of freedom of the box as the degrees of freedom of a thermodynamic system. Applying standard mathematical methods to the thermodynamics of an empty box allows equations with the same structure as those of cosmology and classical and quantum mechanics to be derived. The simple model system of an empty box is shown to have interesting connections to classical mechanics, special relativity, and quantum field theory.

Harborth [{\it Elemente der Mathematik}, Vol. 33 (5), 116--118, 1978] proved that every set of 10 points in the plane, no three on a line, contains an empty convex pentagon. From this it follows that the number of disjoint empty convex pentagons in any set of $n$ points in the plane is least $\lfloor\frac{n}{10}\rfloor$. In this paper we prove that every set of 19 points in the plane, no three on a line, contains two disjoint empty convex pentagons. We also show that any set of $2m+9$ points in the plane, where $m$ is a positive integer, can be subdivided into three disjoint convex regions, two of which contains $m$ points each, and another contains a set of 9 points containing an empty convex pentagon. Combining these two results, we obtain non-trivial lower bounds on the number of disjoint empty convex pentagons in planar points sets. We show that the number of disjoint empty convex pentagons in any set of $n$ points in the plane, no three on a line, is at least $\lfloor\frac{5n}{47}\rfloor$. This bound has been further improved to $\frac{3n-1}{28}$ for infinitely many $n$.

For open world applications, deep neural networks (DNNs) need to be aware of previously unseen data and adaptable to evolving environments. Furthermore, it is desirable to detect and learn novel classes which are not included in the DNNs underlying set of semantic classes in an unsupervised fashion. The method proposed in this article builds upon anomaly detection to retrieve out-of-distribution (OoD) data as candidates for new classes. We thereafter extend the DNN by $k$ empty classes and fine-tune it on the OoD data samples. To this end, we introduce two loss functions, which 1) entice the DNN to assign OoD samples to the empty classes and 2) to minimize the inner-class feature distances between them. Thus, instead of ground truth which contains labels for the different novel classes, the DNN obtains a single OoD label together with a distance matrix, which is computed in advance. We perform several experiments for image classification and semantic segmentation, which demonstrate that a DNN can extend its own semantic space by multiple classes without having access to ground truth.

When a quantum object -- a particle as we call it in a non-rigorous way -- is described by a multi-branched wave- function, with the corresponding wave-packets occupying separated regions of the time-space, a frequently asked question is whether the quantum object is actually contained in only one of these wave-packets. If the answer is positive, then the other wave-packets are called in literature empty waves. The wave-packet containing the object is called a full wave, and is the only one that would produce a recording in a detector. A question immediately arising is whether the empty waves may also have an observable effect. Different works were dedicated to the elucidation of this question. None of them proved that the hypothesis of full/empty waves is correct - it may be that the Nature is indeed non-deterministic and the quantum object is not confined to one region of the space-time. All the works that proved that the empty waves have an effect, in fact, proved that if there exist full and empty waves, then the latter may have an observable effect. This is also the purpose and the limitation of the present work. What is shown here is that if the hypothesis is true, the empty

We study stochastic properties of the empty space for stationary germ-grain models in $\R^d$, in particular we deal with the inner radius of the empty space with respect to a general structuring element which is allowed to be lower-dimensional. We consider Poisson cluster germ-grain models and Boolean models with grains that are clusters of convex bodies and show that more variable size of clusters results in stochastically greater empty space in terms of the empty space hazard function. We also study impact of clusters being more spread in the space on the value of the empty space hazard. Further we obtain asymptotic behavior of the empty space hazard functions at zero and at infinity.

This paper studies empty squares in arbitrary orientation among a set $P$ of $n$ points in the plane. We prove that the number of empty squares with four contact pairs is between $Ω(n)$ and $O(n^2)$, and that these bounds are tight, provided $P$ is in a certain general position. A contact pair of a square is a pair of a point $p\in P$ and a side $\ell$ of the square with $p\in \ell$. The upper bound $O(n^2)$ also applies to the number of empty squares with four contact points, while we construct a point set among which there is no square of four contact points. These combinatorial results are based on new observations on the $L_\infty$ Voronoi diagram with the axes rotated and its close connection to empty squares in arbitrary orientation. We then present an algorithm that maintains a combinatorial structure of the $L_\infty$ Voronoi diagram of $P$, while the axes of the plane continuously rotates by $90$ degrees, and simultaneously reports all empty squares with four contact pairs among $P$ in an output-sensitive way within $O(s\log n)$ time and $O(n)$ space, where $s$ denotes the number of reported squares. Several new algorithmic results are also obtained: a largest empty square

The de Broglie-Bohm interpretation is a no-collapse interpretation, which implies that we are in principle surrounded by empty waves generated by all particles of the universe, empty waves that will never collapse. It is common to establish an analogy between these pilot-waves and 3D radio-waves, which are nearly devoided of energy but carry nevertheless information to which we may have access after an amplification process. Here we show that this analogy is limited: if we consider empty waves in configuration space, an effective collapse occurs when a detector clicks and the 3ND empty wave associated to a particle may not influence another particle (even if these two particles are identical, e.g. bosons as in the example considered here).