We prove that among all 1-periodic configurations $\Gamma $ of points on the real line $\mathbb{R}$ the quantities $\min _{x \in \mathbb{R}} \sum _{\gamma \in \Gamma } e^{- \pi \alpha (x - \gamma )^{2}}$ and $\max _{x \in \mathbb{R}} \sum _{\gamma \in \Gamma } e^{- \pi \alpha (x - \gamma )^{2}}$ are maximized and minimized, respectively, if and only if the points are equispaced and whenever the number of points $n$ per period is sufficiently large (depending on $\alpha $). This solves the polarization problem for periodic configurations with a Gaussian weight on $\mathbb{R}$ for large $n$. The first result is shown using Fourier series. The second result follows from the work of Cohn and Kumar on universal optimality and holds for all $n$ (independent of $\alpha $).
New Algorithms and Bounds for Halving Pseudolines
LetPbe a set of points in general position in the plane. Ahalving lineofPis a line passing through two points ofPand cuttingthe remainingn−2 points in a half (almost half ifnis odd). Gener-alized configurations of points and their representations using allowablesequences are useful for bounding the number of halving lines.We study a problem of finding generalized configurations of pointsmaximizing the number of halving pseudolines. We develop algorithmsfor optimizing generalized configurations of points using the new notionofpartial allowable sequenceand the problem of computing a partialallowable sequence maximizing the number ofk-transpositions. It canbe viewed as a sorting problem using transpositions of adjacent elementsand maximizing the number of transpositions at positionk.We show that this problem can be solved inO(nkn) time for anyk>2, and inO(nk)timefork=1,2. We develop an approach for opti-mizing allowable sequences. Using this approach, we find new bounds forhalving pseudolines for evenn,n≤100.
more »
« less
- Award ID(s):
- 1718994
- NSF-PAR ID:
- 10196126
- Date Published:
- Journal Name:
- LNCS
- Volume:
- 12016
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract -
We develop recursions for computing the mean and variance of the number of pooled tests needed by the halving scheme to determine the disease positive members of a population. It is assumed that each population member is independently positive with probability p, that the individual blood samples can be pooled to test whether or not at least one member of that pooled group is positive, and that a positive tested group is then split in half and the process continued.more » « less
-
Lossy compression has been employed to reduce the unprecedented amount of data produced by today's large-scale scientific simulations and high-resolution instruments. To avoid loss of critical information, state-of-the-art scientific lossy compressors provide error controls on relatively simple metrics such as absolute error bound. However, preserving these metrics does not translate to the preservation of topological features, such as critical points in vector fields. To address this problem, we investigate how to effectively preserve the sign of determinant in error-controlled lossy compression, as it is an important quantity of interest used for the robust detection of many topological features. Our contribution is three-fold. (1) We develop a generic theory to derive the allowable perturbation for one row of a matrix while preserving its sign of the determinant. As a practical use-case, we apply this theory to preserve critical points in vector fields because critical point detection can be reduced to the result of the point-in-simplex test that purely relies on the sign of determinants. (2) We optimize this algorithm with a speculative compression scheme to allow for high compression ratios and efficiently parallelize it in distributed environments. (3) We perform solid experiments with real-world datasets, demonstrating that our method achieves up to 440% improvements in compression ratios over state-of-the-art lossy compressors when all critical points need to be preserved. Using the parallelization strategies, our method delivers up to 1.25X and 4.38X performance speedup in data writing and reading compared with the vanilla approach without compression.more » « less
-
Vallan, Alberto (Ed.)Concentric ring electrodes are noninvasive and wearable sensors for electrophysiological measurement capable of estimating the surface Laplacian (second spatial derivative of surface potential) at each electrode. Previously, progress was made toward optimization of inter-ring distances (distances between the recording surfaces of a concentric ring electrode), maximizing the accuracy of the surface Laplacian estimate based on the negligible dimensions model of the electrode. However, this progress was limited to tripolar (number of concentric rings n equal to 2) and quadripolar (n = 3) electrode configurations only. In this study, the inter-ring distances optimization problem is solved for pentapolar (n = 4) and sextopolar (n = 5) concentric ring electrode configurations using a wide range of truncation error percentiles ranging from 1st to 25th. Obtained results also suggest consistency between all the considered concentric ring electrode configurations corresponding to n ranging from 2 to 5 that may allow estimation of optimal ranges of inter-ring distances for electrode configurations with n ≥ 6. Therefore, this study may inform future concentric ring electrode design for n ≥ 4 which is important since the accuracy of surface Laplacian estimation has been shown to increase with an increase in n.more » « less
-
In 1946, Erd\H{o}s posed the distinct distance problem, which seeks to findthe minimum number of distinct distances between pairs of points selected fromany configuration of $n$ points in the plane. The problem has since beenexplored along with many variants, including ones that extend it into higherdimensions. Less studied but no less intriguing is Erd\H{o}s' distinct angleproblem, which seeks to find point configurations in the plane that minimizethe number of distinct angles. In their recent paper "Distinct Angles inGeneral Position," Fleischmann, Konyagin, Miller, Palsson, Pesikoff, and Wolfuse a logarithmic spiral to establish an upper bound of $O(n^2)$ on the minimumnumber of distinct angles in the plane in general position, which prohibitsthree points on any line or four on any circle. We consider the question of distinct angles in three dimensions and providebounds on the minimum number of distinct angles in general position in thissetting. We focus on pinned variants of the question, and we examine explicitconstructions of point configurations in $\mathbb{R}^3$ which useself-similarity to minimize the number of distinct angles. Furthermore, westudy a variant of the distinct angles question regarding distinct angle chainsand provide bounds on the minimum number of distinct chains in $\mathbb{R}^2$and $\mathbb{R}^3$.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1007/978-3-030-39219-2_37
