Search

Folding a discrete geometry from a flat sheet of material is one way to construct a 3D object. A typical creation pipeline first designs the 3D object, unfolds it, prints and cuts the unfold pattern from a 2D material, and then refolds the object. Within this work we focus on the unfold part of this pipeline. Most current unfolding approaches segment the input, which has structural downsides for the refolded result. Therefore, we are aiming to unfold the input into a single-patched pattern. Our algorithm applies tabu search to the topic of unfolding. We show empirically that our algorithm is faster and more reliable than other methods unfolding into single-patched unfold patterns. Moreover, our algorithm can handle any sort of flat polygon as faces, while comparable methods are bound to triangles. [ABSTRACT FROM AUTHOR]

In this paper, we give examples that improve the lower bound on the maximum number of halving lines for sets in the plane with 35, 59, 95, and 97 points and, as a consequence, we improve the current best upper bound of the rectilinear crossing number for sets in the plane with 35, 59, 95, and 97 points, provided that a conjecture included in the literature is true. As another consequence, we also improve the lower bound on the maximum number of halving pseudolines for sets in the plane with 35 points. These examples, and the recursive bounds for the maximum number of halving lines for sets with an odd number of points achieved, give a new insight in the study of the rectilinear crossing number problem, one of the most challenging tasks in Discrete Geometry. With respect to this problem, it is conjectured that, for all n multiples of 3, there are 3-symmetric sets of n points for which the rectilinear crossing number is attained. [ABSTRACT FROM AUTHOR]

Euclidean geometry is a form of structural geometry grounded in a set of axioms from which all theorems are derived. This branch of mathematics encompasses two fundamental measurement types: angles and distances. It is widely recognized that the Euclidean axioms for measuring distances taught to students during primary, middle, and high school mathematics curricula establish the foundational concepts and structures of geometry they learn. The purpose of this article is to propose an educational resource that is designed for exceptional or gifted students in secondary school. This resource introduces alternative methods for measuring distances that differ from the Euclidean method. The objective of this educational material is to encourage students to think beyond the conventional Euclidean framework and explore alternative worlds of geometric structures. By broadening their horizons, students can recognize that geometric structures are not absolute but relative to the axioms and logical definitions that are agreed upon beforehand. [ABSTRACT FROM AUTHOR]

This paper provides computational tools for the modeling and design of quad mesh mechanisms, which are meshes allowing continuous flexions under the assumption of rigid faces and hinges in the edges. We combine methods and results from different areas, namely differential geometry of surfaces, rigidity and flexibility of bar and joint frameworks, algebraic geometry, and optimization. The basic idea to achieve a time-continuous flexion is time-discretization justified by an algebraic degree argument. We are able to prove computationally feasible bounds on the number of required time instances we need to incorporate in our optimization. For optimization to succeed, an informed initialization is crucial. We present two computational pipelines to achieve that: one based on remeshing isometric surface pairs, another one based on iterative refinement. A third manner of initialization proved very effective: We interactively design meshes which are close to a narrow known class of flexible meshes, but not contained in it. Having enjoyed sufficiently many degrees of freedom during design, we afterwards optimize towards flexibility. [ABSTRACT FROM AUTHOR]

Motivated by the emergence of rough surfaces in various areas of design, we address the computational design of triangle meshes with controlled roughness. Our focus lies on small levels of roughness. There, roughness or smoothness mainly arises through the local positioning of the mesh edges and faces with respect to the curvature behavior of the reference surface. The analysis of this interaction between curvature and roughness is simplified by a 2D dual diagram and its generation within so-called isotropic geometry, which may be seen as a structure-preserving simplification of Euclidean geometry. Isotropic dihedral angles of the mesh are close to the Euclidean angles and appear as Euclidean edge lengths in the dual diagram, which also serves as a tool for visualization and interactive local design. We present a computational framework that includes appearance-aware remeshing, optimization-based automatic roughening, and control of dihedral angles. [ABSTRACT FROM AUTHOR]

Meshes with spherical faces and circular edges are an attractive alternative to polyhedral meshes for applications in architecture and design. Approximation of a given surface by such a mesh needs to consider the visual appearance, approximation quality, the position and orientation of circular intersections of neighboring faces and the existence of a torsion free support structure that is formed by the planes of circular edges. The latter requirement implies that the mesh simultaneously defines a second mesh whose faces lie on the same spheres as the faces of the first mesh. It is a discretization of the two envelopes of a sphere congruence, i.e., a two-parameter family of spheres. We relate such sphere congruences to torsal parameterizations of associated line congruences. Turning practical requirements into properties of such a line congruence, we optimize line and sphere congruence as a basis for computing a mesh with spherical triangular or quadrilateral faces that approximates a given reference surface. [ABSTRACT FROM AUTHOR]

Let $\mathbb {F}_q^d$ denote the d -dimensional vector space over the finite field $\mathbb {F}_q$ with q elements. Define for $\alpha = (\alpha _1, \dots , \alpha _d) \in \mathbb {F}_q^d$. Let $k\in \mathbb {N}$ , A be a nonempty subset of $\{(i, j): 1 \leq i and $r\in (\mathbb {F}_q)^2\setminus {0}$ , where $(\mathbb {F}_q)^2=\{a^2:a\in \mathbb {F}_q\}$. If $E\subset \mathbb {F}_q^d$ , our main result demonstrates that when the size of the set E satisfies $|E| \geq C_k q^{d/2}$ , where $C_k$ is a constant depending solely on k , it is possible to find two $(k+1)$ -tuples in E such that one of them is dilated by r with respect to the other, but only along $|A|$ edges. To be more precise, we establish the existence of $(x_1, \dots , x_{k+1}) \in E^{k+1}$ and $(y_1, \dots , y_{k+1}) \in E^{k+1}$ such that, for $(i, j) \in A$ , we have $\lVert y_i - y_j \rVert = r \lVert x_i - x_j \rVert $ , with the conditions that $x_i \neq x_j$ and $y_i \neq y_j$ for $1 \leq i , provided that $|E| \geq C_k q^{d/2}$ and $r\in (\mathbb {F}_q)^2\setminus \{0\}$. We provide two distinct proofs of this result. The first uses the technique of group actions, a powerful method for addressing such problems, while the second is based on elementary combinatorial reasoning. Additionally, we establish that in dimension 2, the threshold $d/2$ is sharp when $q \equiv 3 \pmod 4$. As a corollary of the main result, by varying the underlying set A , we determine thresholds for the existence of dilated k -cycles, k -paths and k -stars (where $k \geq 3$) with a dilation ratio of $r\in (\mathbb {F}_q)^2\setminus \{0\}$. These results improve and generalise the findings of Xie and Ge ['Some results on similar configurations in subsets of $\mathbb {F}_q^d$ ', Finite Fields Appl. 91 (2023), Article no. 102252, 20 pages]. [ABSTRACT FROM AUTHOR]

Denote by C ℓ - the 3-uniform hypergraph obtained by removing one hyperedge from the tight cycle on ℓ vertices. It is conjectured that the Turán density of C 5 - is 1/4. In this paper, we make progress toward this conjecture by proving that the Turán density of C ℓ - is 1/4, for every sufficiently large ℓ not divisible by 3. One of the main ingredients of our proof is a forbidden-subhypergraph characterization of the hypergraphs, for which there exists a tournament on the same vertex set such that every hyperedge is a cyclic triangle in this tournament. A byproduct of our method is a human-checkable proof for the upper bound on the maximum number of almost similar triangles in a planar point set, which was recently proved using the method of flag algebras by Balogh, Clemen, and Lidický. [ABSTRACT FROM AUTHOR]

In order to achieve an effective balance between SAR image simulation fidelity and efficiency, we proposed a ray-tracing-assisted SAR image simulation method under range doppler (RD) imaging geometry. This method utilizes the spatial traversal mode of RD imaging geometry to transmit discrete electromagnetic (EM) waves into the SAR radiation area and follows the Nyquist sampling law to set the density of transmitted EM waves to effectively identify the beam radiation area. The ray-tracing algorithm is used to obtain the backscatter amplitude and real-time slant range of the transmitted EM wave, which can effectively record the multiple backscattering among the components of the distributed target so that the backscattering subfields of each component can be correlated. According to the RD condition equation, the backscattering amplitude is assigned to the corresponding range gate, and the three-dimensional (3D) target is mapped into the two-dimensional (2D) SAR slant-range coordinate system, and the SAR target simulated image is directly obtained. Finally, the simulation images of the proposed method are compared qualitatively and quantitatively with those obtained by commercial simulation software, and the effectiveness of the proposed method is verified. [ABSTRACT FROM AUTHOR]

The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d + 1) (r - 1) + 1 points in R d , one can find a partition X = X 1 ∪ ⋯ ∪ X r of X, such that the convex hulls of the X i , i = 1 , ... , r , all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span ⌊ n / 3 ⌋ vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Álvarez-Rebollar et al. guarantees ⌊ n / 6 ⌋ pairwise crossing triangles. Our result generalizes to a result about simplices in R d , d ≥ 2 . [ABSTRACT FROM AUTHOR]

In one of their seminal articles on allowable sequences, Goodman and Pollack gave combinatorial generalizations for three problems in discrete geometry, one of which being the Dirac conjecture. According to this conjecture, any set of n noncollinear points in the plane has a point incident to at least cn connecting lines determined by the set. The notion of allowable sequences of permutations provides a natural combinatorial setting for analyzing these problems. Within this formalism, the conjectured generalization reads as follows: Any nontrivial allowablen-sequence Σ has a local sequence Λ i whose half-period is at leastcn. The conjecture is confirmed here with a concrete bound c = 1 / 845 . Several related problems are discussed. [ABSTRACT FROM AUTHOR]

The general position problem for graphs was inspired by the no-three-in-line problem from discrete geometry. A set S of vertices of a graph G is a general position set if no shortest path in G contains three or more vertices of S. The general position number of G is the number of vertices in a largest general position set. In this paper we investigate the general position numbers of the Mycielskian of graphs. We give tight upper and lower bounds on the general position number of the Mycielskian of a graph G and investigate the structure of the graphs meeting these bounds. We determine this number exactly for common classes of graphs, including cubic graphs and a wide range of trees. [ABSTRACT FROM AUTHOR]

This paper studies the discrete differential geometry of the checkerboard pattern inscribed in a quadrilateral net by connecting edge midpoints. It turns out to be a versatile tool which allows us to consistently define principal nets, Koenigs nets and eventually isothermic nets as a combination of both. Principal nets are based on the notions of orthogonality and conjugacy and can be identified with sphere congruences that are entities of Möbius geometry. Discrete Koenigs nets are defined via the existence of the so-called conic of Koenigs. We find several interesting properties of Koenigs nets, including their being dualizable and having equal Laplace invariants. Isothermic nets can be defined as Koenigs nets that are also principal nets. We prove that the class of isothermic nets is invariant under both dualization and Möbius transformations. Among other things, this allows a natural construction of discrete minimal surfaces and their Goursat transformations. [ABSTRACT FROM AUTHOR]

In this paper, we provide improvements in the additive constant of the current best asymptotic upper bound for the maximum number of halving lines for planar sets of n points, where n is an even number. We also improve this current best upper bound for small values of n, namely, 106 ≤ n ≤ 336 . To obtain this enhancements, we provide lower bounds for the sum of the squares of the degrees of the vertices of a graph related to the halving lines. [ABSTRACT FROM AUTHOR]

In 2013, while studying a relevant class of polyominoes that tile the plane by translation, i.e., double square polyominoes, Blondin Massé et al. found that their boundary words, encoded by the Freeman chain coding on a four letters alphabet, have specific interesting properties that involve notions of combinatorics on words such as palindromicity, periodicity and symmetry. Furthermore, they defined a notion of reducibility on double squares using homologous morphisms, so leading to a set of irreducible tile elements called prime double squares. The authors, by inspecting the boundary words of the smallest prime double squares, conjectured the strong property that no runs of two (or more) consecutive equal letters are present there. In this paper, we prove such a conjecture using combinatorics on words' tools, and setting the path to the definition of a fast generation algorithm and to the possibility of enumerating the elements of this class w.r.t. standard parameters, as perimeter and area. [ABSTRACT FROM AUTHOR]

We prove an explicit expression for the solutions of the discrete Schwarzian octahedron recurrence, also known as the discrete Schwarzian KP equation (dSKP), as the ratio of two partition functions. Each one counts weighted oriented dimer configurations of an associated bipartite graph, and is equal to the determinant of a Kasteleyn matrix. This is in the spirit of Speyer's result on the dKP equation, or octahedron recurrence (Journal of Alg. Comb. 2007). One consequence is that dSKP has zero algebraic entropy, meaning that the growth of the degrees of the polynomials involved is only polynomial. There are cancellations in the partition function, and we prove an alternative, cancellation free explicit expression involving complementary trees and forests. Using all of the above, we show several instances of the Devron property for dSKP, i.e., that certain singularities in initial data repeat after a finite number of steps. This has many applications for discrete geometric systems and is the subject of a companion paper (preprint 2022, Affolter, de Tillière, and Melotti). We also find limit shape results analogous to the arctic circle of the Aztec diamond. Finally, we discuss the combinatorics of all the other octahedral equations in the classification of Adler, Bobenko and Suris (IMRN 2012).Mathematics Subject Classifications: 05A15, 37K10, 37K60, 82B20, 82B23Keywords: Dimer model, octahedron recurrence, discrete KP equation, integrable system, spanning forests, algebraic entropy, discrete geometry, projective geometry, Aztec diamond, limit shapes

Given two circle patterns of the same combinatorics in the plane, the Möbius transformations mapping circumdisks of one to the other induce a PSL(2,\mathbb {C})-valued function on the dual graph. Such a function plays the role of an osculating Möbius transformation and induces a realization of the dual graph in hyperbolic space. We characterize the realizations and obtain a one-to-one correspondence in the cases that the two circle patterns share the same discrete conformal structure. These correspondences are analogous to the Weierstrass representation for surfaces with constant mean curvature H\equiv 1 in hyperbolic space. We further establish convergence on triangular lattices. [ABSTRACT FROM AUTHOR]

Simplicial Kuramoto models have emerged as a diverse and intriguing class of models describing oscillators on simplices rather than nodes. In this paper, we present a unified framework to describe different variants of these models, categorized into three main groups: "simple" models, "Hodge-coupled" models, and "order-coupled" (Dirac) models. Our framework is based on topology and discrete differential geometry, as well as gradient systems and frustrations, and permits a systematic analysis of their properties. We establish an equivalence between the simple simplicial Kuramoto model and the standard Kuramoto model on pairwise networks under the condition of manifoldness of the simplicial complex. Then, starting from simple models, we describe the notion of simplicial synchronization and derive bounds on the coupling strength necessary or sufficient for achieving it. For some variants, we generalize these results and provide new ones, such as the controllability of equilibrium solutions. Finally, we explore a potential application in the reconstruction of brain functional connectivity from structural connectomes and find that simple edge-based Kuramoto models perform competitively or even outperform complex extensions of node-based models. [ABSTRACT FROM AUTHOR]

We solve the dual multijoint problem and prove the existence of so-called factorisations for arbitrary fields and multijoints of k j -planes. More generally, we deduce a discrete analogue of a theorem due in essence to Bourgain and Guth. Our result is a universal statement which describes a property of the discrete wedge product without any explicit reference to multijoints and is stated as follows: Suppose that k 1 + ... + k d = n . There is a constant C = C (n) so that for any field F and for any finitely supported function S : F n → R ≥ 0 , there are factorising functions s k j : F n × Gr (k j , F n) → R ≥ 0 such that V 1 ∧ ⋯ ∧ V d S p d ≤ ∏ j = 1 d s k j p , V j , for every p ∈ F n and every tuple of planes V j ∈ Gr (k j , F n) , and ∑ p ∈ π j s (p , e (π j)) = C S d , for every k j -plane π j ⊂ F n , where e (π j) ∈ Gr (k j , F n) , is the translate of π j that contains the origin and ∧ denotes the discrete wedge product. [ABSTRACT FROM AUTHOR]

We define a metric that makes the algebraic closure of a finite field F ¯ p into a UDBG (uniformly discrete with bounded geometry) metric space. This metric stems from algebraic properties of F ¯ p. From this perspective, for F ¯ p we explore common research themes in metric spaces, reveal how peculiar properties naturally arise, and present it as a new type of example for certain well-studied questions. [ABSTRACT FROM AUTHOR]

The Steinitz constant in dimension d is the smallest value c(d) such that for any norm on R d and for any finite zero-sum sequence in the unit ball, the sequence can be permuted such that the norm of each partial sum is bounded by c(d). Grinberg and Sevastyanov prove that c (d) ≤ d and that the bound of d is best possible for arbitrary norms; we refer to their result as the Steinitz Lemma. We present a variation of the Steinitz Lemma that permutes multiple sequences at one time. Our result, which we term a colorful Steinitz Lemma, demonstrates upper bounds that are independent of the number of sequences. Many results in the theory of integer programming are proved by permuting vectors of bounded norm; this includes proximity results, Graver basis algorithms, and dynamic programs. Due to a recent paper of Eisenbrand and Weismantel, there has been a surge of research on how the Steinitz Lemma can be used to improve integer programming results. As an application we prove a proximity result for block-structured integer programs. [ABSTRACT FROM AUTHOR]

This article explores the Erdős-Szekeres conjecture, a mathematical problem concerning geometric patterns in sets of points. The conjecture was proposed in 1935 and has been the focus of extensive research. Various mathematicians, including Tóth, Valtr, and Suk, have made significant contributions to proving the conjecture. Suk's proof is described as a moment of brilliance in applying the right tools. The article concludes with a quote from Erdős emphasizing the importance of an open mind in mathematics. [Extracted from the article]

Ball's complex plank theorem states that if v 1 , ⋯ , v n are unit vectors in C d , and t 1 , ⋯ , t n are non-negative numbers satisfying ∑ k = 1 n t k 2 = 1 , then there exists a unit vector v in C d for which | ⟨ v k , v ⟩ | ≥ t k for every k. Here we present a streamlined version of Ball's original proof. [ABSTRACT FROM AUTHOR]

Recently, Ludewig and Thiang introduced a notion of a uniformly localized Wannier basis with localization centers in an arbitrary uniformly discrete subset D in a complete Riemannian manifold X. They show that, under certain geometric conditions on X, the class of the orthogonal projection onto the span of such a Wannier basis in the K-theory of the Roe algebra C*(X) is trivial. In this paper, we clarify the geometric conditions on X, which guarantee triviality of the K-theory class of any Wannier projection. We show that this property is equivalent to triviality of the unit of the uniform Roe algebra of D in the K-theory of its Roe algebra, and provide a geometric criterion for that. As a consequence, we prove triviality of the K-theory class of any Wannier projection on a connected proper measure space X of bounded geometry with a uniformly discrete set of localization centers. [ABSTRACT FROM AUTHOR]

We show that the Holmes-Thompson area of every Finsler disk of radius r whose interior geodesics are length-minimizing is at least .... Furthermore, we construct examples showing that the inequality is sharp and observe that equality is attained by a non-rotationally-symmetric metric. This contrasts with Berger's conjecture in the Riemannian case, which asserts that the round hemisphere is extremal. To prove our theorem we discretize the Finsler metric using random geodesics. As an auxiliary result, we include a proof of the integral geometry formulas of Blaschke and Santaló for Finsler manifolds with almost no trapped geodesics. [ABSTRACT FROM AUTHOR]

In this paper, we provide a brief introduction to the main notions of geometric group theory and of asymptotic topology of finitely generated groups. We will start by presenting the basis of discrete groups and of the topology at infinity, then we will state some of the main theorems in these fields. Our aim is to give a sample of how the presence of a group action may affect the geometry of the underlying space and how in many cases topological methods may help the determine solutions of algebraic problems which may appear unrelated. [ABSTRACT FROM AUTHOR]

In this article, we will examine some points related to sequences in school textbooks. By examining the school and university textbooks, it can be seen that the sequences are presented in the textbooks very briefly, which has caused students to face problems in the university. Because there are many topics such as limit, continuity, derivative and integral, existence of limit or continuity or not of some functions, and even other topics in discrete mathematics or geometry books to know the concept and characteristics of sequences. In addition, there are many sequences, each of which, depending on whether they are convergent or divergent, have interesting features that can be useful for teaching. In this article, considering the roots of an equation in the second dimension, we will introduce and examine the Lucas and Fibonacci sequences. In the following, we will discuss the characteristics of this biped and check their relationship with each other. [ABSTRACT FROM AUTHOR]

To decide the number, size, and location of its plants, a firm balances the benefit of delivering goods from multiple plants with the cost of setting up and managing these plants and the potential for cannibalization among them. Modeling the decisions of heterogeneous firms in an economy with a vast number of distinct locations involves a large combinatorial problem. Using insights from discrete geometry, we study a tractable limit case of this problem in which these forces operate at a local level. Our analysis delivers predictions on sorting across space. Compared with less productive firms, productive firms place more plants in dense, high-rent locations and fewer plants in markets with low density and low rents. We present evidence consistent with these and several other predictions, using US establishment-level data. [ABSTRACT FROM AUTHOR]

In Chuanming Zong's program to attack Hadwiger's covering conjecture, which is a longstanding open problem from Convex and Discrete Geometry, it is essential to estimate covering functionals of convex bodies effectively. Recently, He et al. and Yu et al. provided two deterministic global optimization algorithms having high computational complexity for this purpose. Since satisfactory estimations of covering functionals will be sufficient in Zong's program, we propose a stochastic global optimization algorithm based on CUDA and provide an error estimation for the algorithm. The accuracy of our algorithm is tested by comparing numerical and exact values of covering functionals of convex bodies including the Euclidean unit disc, the three-dimensional Euclidean unit ball, the regular tetrahedron, and the regular octahedron. We also present estimations of covering functionals for the regular dodecahedron and the regular icosahedron. [ABSTRACT FROM AUTHOR]

A covering path for a planar point set is a path drawn in the plane with straight- line edges such that every point lies at a vertex or on an edge of the path. A covering tree is defined analogously. Let π(n) be the minimum number such that every set of n points in the plane can be covered by a noncrossing path with at most π(n) edges. Let T(n) be the analogous number for non-crossing covering trees. Dumitrescu, Gerbner, Keszegh, and Tóth (Discrete & Computational Geometry, 2014) established the following inequalities: (5n)/9 - O(1) < π(n) < (1 - 1/601080391), n and (9n)/17 - O(1) < tau(n) ≤ [5n/6]. We report the following improved upper bounds: π(n) <= (1 - 1/22), n and t(n) ≤ =[(4n)/5]. In the same context we study rainbow polygons. For a set of colored points in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color in its interior or on its boundary. Let rho(k) be the minimum number such that every k-colored point set in the plane admits a perfect rainbow polygon of size p(k). Flores-Peñaloza, Kano, Martínez-Sandoval, Orden, Tejel, Tóth, Urrutia, and Vogtenhuber (Discrete Mathematics, 2021) proved that 20k / 19 - O(1) < p(k) < 10k/7+O(1) We report the improved upper bound p(k) < 7k/5 + O(1) To obtain the improved bounds we present simple algorithms that achieve paths, trees, and polygons with our desired number of edges. [ABSTRACT FROM AUTHOR]

A number of important recent developments in various branches of discrete geometry were presented at the workshop. The presentations illustrated both the diversity of the area and its strong connections to other fields of mathematics such as convex geometry, combinatorics, or topology. Two open problem sessions highlighted the abundance of open questions and many of the results presented were obtained by young researchers, confirming the vitality of the field. [ABSTRACT FROM AUTHOR]

Managing on-time delivery systems is challenging because of the underlying uncertainties and combinatorial nature of the routing decision. In practice, the efficiency of such systems also hinges on the driver's familiarity with the local neighborhood. In "Provably Good Region Partitioning for On-Time Last-Mile Delivery," Carlsson et al. study a region partitioning policy to minimize the expected delivery time of customer orders in a stochastic and dynamic setting. This policy assigns every driver to a subregion, ensuring that drivers are only dispatched to their territories. The authors characterize the structure of the optimal partitioning policy and show its expected on-time performance converges to that of the flexible dispatching policy in heavy traffic. The optimal characterization features two insightful conditions that are critical to the on-time performance of last-mile delivery systems. Furthermore, the paper develops partitioning algorithms with performance guarantees, leveraging ham sandwich cuts and three-partitions from discrete geometry. On-time last-mile delivery is expanding rapidly as people expect faster delivery of goods ranging from grocery to medicines. Managing on-time delivery systems is challenging because of the underlying uncertainties and combinatorial nature of the routing decision. In practice, the efficiency of such systems also hinges on the driver's familiarity with the local neighborhood. This paper studies the optimal region partitioning policy to minimize the expected delivery time of customer orders in a stochastic and dynamic setting. We allow both the order locations and on-site service times to be random and generally distributed. This policy assigns every driver to a subregion, hence making sure drivers will only be dispatched to their own territories. We characterize the structure of the optimal partitioning policy and show its expected on-time performance converges to that of the flexible dispatching policy in heavy traffic. The optimal characterization features two insightful conditions that are critical to the on-time performance of last-mile delivery systems. We then develop partitioning algorithms with performance guarantees, leveraging ham sandwich cuts and three-partitions from discrete geometry. This algorithmic development can be of independent interest for other logistics problems. We demonstrate the efficiency of the proposed region partitioning policy via numerical experiments using synthetic and real-world data sets. Funding: The first author gratefully acknowledges the support of the Office of Naval Research [Grant N00014-21-1-2208] and METRANS [Grant PSR-21-22]. The second author gratefully acknowledges the support of the Natural Sciences and Engineering Research Council of Canada [Grant RGPIN-2022-04950] and the National Natural Science Foundation of China [Grant 72242106]. The third author gratefully acknowledges the support of the Natural Sciences and Engineering Research Council of Canada [Grant RGPIN-2023-04453]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2021.0588. [ABSTRACT FROM AUTHOR]

The tongue surface houses a range of papillae that are integral to the mechanics and chemistry of taste and textural sensation. Although gustatory function of papillae is well investigated, the uniqueness of papillae within and across individuals remains elusive. Here, we present the first machine learning framework on 3D microscopic scans of human papillae ( n = 2092 ), uncovering the uniqueness of geometric and topological features of papillae. The finer differences in shapes of papillae are investigated computationally based on a number of features derived from discrete differential geometry and computational topology. Interpretable machine learning techniques show that persistent homology features of the papillae shape are the most effective in predicting the biological variables. Models trained on these features with small volumes of data samples predict the type of papillae with an accuracy of 85%. The papillae type classification models can map the spatial arrangement of filiform and fungiform papillae on a surface. Remarkably, the papillae are found to be distinctive across individuals and an individual can be identified with an accuracy of 48% among the 15 participants from a single papillae. Collectively, this is the first evidence demonstrating that tongue papillae can serve as a unique identifier, and inspires a new research direction for food preferences and oral diagnostics. [ABSTRACT FROM AUTHOR]

The Erdős distinct distance problem is a ubiquitous problem in discrete geometry. Less well known is Erdős's distinct angle problem, the problem of finding the minimum number of distinct angles between n non-collinear points in the plane. The standard problem is already well understood. However, it admits many of the same variants as the distinct distance problem, many of which are unstudied. We provide upper and lower bounds on a broad class of distinct angle problems. We show that the number of distinct angles formed by n points in general position is O (n log 2 7) providing the first non-trivial bound for this quantity. We introduce a new class of asymptotically optimal point configurations with no four cocircular points. Then, we analyze the sensitivity of asymptotically optimal point sets to perturbation, yielding a much broader class of asymptotically optimal configurations. In higher dimensions we show that a variant of Lenz's construction admits fewer distinct angles than the optimal configurations in two dimensions. We also show that the minimum size of a maximal subset of n points in general position admitting only unique angles is Ω (n 1 / 5) and O (n (log 2 7) / 3 ) . We also provide bounds on the partite variants of the standard distinct angle problem. [ABSTRACT FROM AUTHOR]

A k-transversal to a family of sets in R d is a k-dimensional affine subspace that intersects each set of the family. In 1957 Hadwiger provided a necessary and sufficient condition for a family of pairwise disjoint, planar convex sets to have a 1-transversal. After a series of three papers among the authors Goodman, Pollack, and Wenger from 1988 to 1990, Hadwiger's Theorem was extended to necessary and sufficient conditions for (d - 1) -transversals to finite families of convex sets in R d with no disjointness condition on the family of sets. However, no such conditions for a finite family of convex sets in R d to have a k-transversal for 0 < k < d - 1 have previously been proven or conjectured. We make progress in this direction by providing necessary and sufficient conditions for a finite family of convex sets in R 2 d to have a (2 d - 2) -transversal. [ABSTRACT FROM AUTHOR]

The pyramidalization angle and spherical curvature are well-known quantities used to characterize the local geometry of a molecule and to provide a measure of regio-chemical activity of molecules. In this paper, we give a self-contained presentation of these two concepts and discuss their limitations. These limitations can bypass, thanks to the introduction of the notions of angular defect and discrete Gauss curvature coming from discrete differential geometry. In particular, these quantities can be easily computed for arbitrary molecules, trivalent or not, with bond of equal lengths or not. All these quantities have been implemented. We then compute all these quantities over the Tománek database covering an almost exhaustive list of fullerene molecules. In particular, we discuss the interdependence of the pyramidalization angle with the spherical curvature, angular defect, and hybridization numbers. We also explore the dependence of the pyramidalization angle with respect to some characteristics of the molecule, such as the number of atoms, the group of symmetry, and the geometrical optimization process. [ABSTRACT FROM AUTHOR]

Digital geometry is a field in the intersection of discrete mathematics and geometry having various applications including geographical information systems (GIS). In digital spaces, in grids, distances can be defined based on steps in paths in somewhat similarly as in graph theory. However, the grids have more definite structures, thus one may obtain more concrete results, for example, close formulae, than on arbitrary graphs. In this article, the weighted (also called chamfer) distances, and based on them, the distance transform are investigated on the regular triangular grid. Three types of neighborhood relations are used on the grid, and therefore, three weights are used to define a distance function. Natural conditions are used on the weights such as they are positive and a larger step (in the usual and also in the Euclidean sense) cannot have a smaller weight than a smaller one. Some properties of the weighted distances are discussed; for example, they are proven to be metrics. We also give algorithms and formulae that compute the weighted distance of any point pair on a triangular grid. Algorithm for weighted distance transform is provided based on wave‐front propagation. Therefore, these new distance functions are ready for further applications in GIS, in image processing tasks, in computer vision, in graphics, in networking, and also in other applied fields. [ABSTRACT FROM AUTHOR]

The visible-volume function assigns to a configuration of cameras and a flexible environment in a convex room the volume that can be supervised by the cameras. It is of interest to configure the cameras and the environment in such a way that the visible volume is maximized. Some methods of global optimization can take profit from desirable analytic properties of the visible-volume function. Earlier work has only considered this function in dimensions two and three or for static environments implicitly defined by level-set functions. In this paper it is shown, that the visible-volume function for a flexible environment modeled explicitly by a parametrized simplicial complex is continuous, piecewise rational, locally Lipschitz, and semi-algebraic in all dimensions. [ABSTRACT FROM AUTHOR]

In a colouring of R d a pair (S , s 0) with S ⊆ R d and with s 0 ∈ S is almost-monochromatic if S \ { s 0 } is monochromatic but S is not. We consider questions about finding almost-monochromatic similar copies of pairs (S , s 0) in colourings of R d , Z d , and of Q under some restrictions on the colouring. Among other results, we characterise those (S , s 0) with S ⊆ Z for which every finite colouring of R without an infinite monochromatic arithmetic progression contains an almost-monochromatic similar copy of (S , s 0) . We also show that if S ⊆ Z d and s 0 is outside of the convex hull of S \ { s 0 } , then every finite colouring of R d without a monochromatic similar copy of Z d contains an almost-monochromatic similar copy of (S , s 0) . Further, we propose an approach based on finding almost-monochromatic sets that might lead to a human-verifiable proof of χ (R 2) ≥ 5 . [ABSTRACT FROM AUTHOR]

We develop the methods used by Rudnev and Wheeler (2022) to prove an incidence theorem between arbitrary sets of Möbius transformations and point sets in F p 2 . We also note some asymmetric incidence results, and give applications of these results to various problems in additive combinatorics and discrete geometry. For instance, we give an improvement to a result of Shkredov concerning the number of representations of a non-zero product defined by a set with small sum-set, and a version of Beck's theorem for Möbius transformations. [ABSTRACT FROM AUTHOR]

Discrete Weierstrass-type representations yield a construction method in discrete differential geometry for certain classes of discrete surfaces. We show that the known discrete Weierstrass-type representations of certain surface classes can be viewed as applications of the Ω -dual transform to lightlike Gauss maps in Laguerre geometry. From this construction, further Weierstrass-type representations arise. As an application of the techniques we develop, we show that all discrete linear Weingarten surfaces of Bryant or Bianchi type locally arise via Weierstrass-type representations from discrete holomorphic maps. [ABSTRACT FROM AUTHOR]

The relationship of discrete L-algebras to projective geometry is deepened and made explicit in several ways. Firstly, a geometric lattice is associated to any discrete L-algebra. Monoids of I-type are obtained as a special case where the perspectivity relation is trivial. Secondly, the structure group of a non-degenerate discrete L-algebra X is determined and shown to be a complete invariant. It is proved that X ∖ {1} is a projective space with an orthogonality relation. A new definition of non-symmetric quantum sets, extending the recursive definition of symmetric quantum sets, is provided and shown to be equivalent to the former one. Quantum sets are characterized as complete projective spaces with an anisotropic duality, and they are also characterized in terms of their complete lattice of closed subspaces, which is one-sided orthomodular and semimodular. For quantum sets of finite cardinality n > 3, a representation as a projective space with duality over a skew-field is given. Quantum sets of cardinality 2 are classified, and the structure group of their associated L-algebra is determined. [ABSTRACT FROM AUTHOR]

The 2023 Oberwolfach meeting “Geometric, Algebraic, and Topological Combinatorics” was organized by Gil Kalai (Jerusalem), Isabella Novik (Seattle), Francisco Santos (Santander), and Volkmar Welker (Marburg). It covered a wide variety of aspects of Discrete Geometry, Algebraic Combinatorics with geometric flavor, and Topological Combinatorics. Some of the highlights of the conference were (1) Federico Ardila and Tom Braden discussed recent exciting developments in the intersection theory of matroids; (2) Stavros Papadakis and Vasiliki Petrotou presented their proof of the Lefschetz property for spheres, and, more generally, for pseudomanifolds and cycles (this second part is joint with Karim Adiprasito); (3) Gaku Liu reported on his joint work with Spencer Backman that establishes the existence of a regular unimodular triangulation of an arbitrary matroid base polytope. [ABSTRACT FROM AUTHOR]