Abstract We construct small coresets for weight-constrained anisotropic assignment and clustering with a specific view toward applications in materials science. Building on previous results for unconstrained least-squares clustering of Har-Peled & Kushal, we obtain coresets even for weight-constrained anisotropic clustering and, particularly, reduce the dependence of their sizes on the number of clusters from cubic to quadratic, an improvement which is decisive for applications in small dimensions such as grain mapping.

Abstract. The present paper studies mathematical models for representing, imaging, and analyzing polycrystalline materials. We introduce various techniques for converting grain maps into diagram or tessellation representations that rely on constrained clustering. In particular, we show how to significantly accelerate the computation of generalized balanced power diagrams and how to extend it to allow for optimization over all relevant parameters. A comparison of the accuracy of the proposed approaches is given based on a three-dimensional real-world data set of [Formula: see text] voxels.

Abstract The paper deals with an inverse problem of reconstructing matrices from their marginal sums. More precisely, we are interested in the existence of $$r\times s$$ r × s matrices for which only the following information is available: The entries belong to known subsets of c distinguishable abelian groups, and the row and column sums of all entries from each group are given. This generalizes Ryser’s classical problem of characterizing the set of all 0–1-matrices with given row and column sums and is a basic problem in (polyatomic) discrete tomography. We show that the problem is closely related to packings of trees in bipartite graphs, prove consistency results, give algorithms and determine its complexity. In particular, we find a somewhat unusual complexity behavior: the problem is hard for “small” but easy for “large” matrices.

Superresolution imaging aims at improving the resolution of an image by enhancing it with other images or data that might have been acquired using different imaging techniques or modalities. In this paper we consider the task of doubling, in each dimension, the resolution of grayscale images of binary objects by fusion with double-resolution tomographic data that have been acquired from two viewing angles. We show that this task is polynomial-time solvable if the gray levels have been reliably determined. The problem becomes ${N}{P}$-hard if the gray levels of some pixels come with an error of $\pm1$ or larger. The ${N}{P}$-hardness persists for any larger resolution enhancement factor. This means that noise does not only affect the quality of a reconstructed image but, less expectedly, also the algorithmic tractability of the inverse problem itself.

The present paper deals with the discrete inverse problem of reconstructing binary matrices from their row and column sums under additional constraints on the number and pattern of entries in specified minors. While the classical consistency and reconstruction problems for two directions in discret e tomography can be solved in polynomial time, it turns out that these window constraints cause various unexpected complexity jumps back and forth from polynomialtime solvability to ℕℙ-hardness.

Ring structures in molecules belong to the most important substructures for many applications in Computational Chemistry. One typical task is to find an implicit description of the ring structure of a molecule. We present efficient algorithms for cyclic graph invariants that may serve as molecular descriptors to accelerate database searches. Another task is to construct a well‐defined set of rings of a molecular graph explicitly. We give a new algorithm for computing the set of relevant cycles of a graph. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(2), 116–131 2017

We study weighted clustering problems in Minkowski spaces under balancing constraints with a view towards separation properties. First, we introduce the gravity polytopes and more general gravity bodies that encode all feasible clusterings and indicate how they can be utilized to develop efficient approximation algorithms for quite general, hard to compute objective functions. Then we show that their extreme points correspond to strongly feasible power diagrams, certain specific cell complexes, whose defining polyhedra contain the clusters, respectively. Further, we characterize strongly feasible centroidal power diagrams in terms of the local optima of some ellipsoidal function over the gravity polytope. The global optima can also be characterized in terms of the separation properties of the corresponding clusterings.

Discrete tomography is concerned with the retrieval of finite point sets in some $\mathbbm{R}^d$ from their X-rays in a given number m of directions $u_1,\ldots, u_m$. In the present paper we focus on uniqueness issues. The first remark gives a uniform treatment and extension of known uniqueness results. In particular, we introduce the concept of J-additivity and give conditions when a subset J of possible positions is already determined by the given data. As a by-product, we settle a conjecture of Brunetti and Daurat on planar lattice convex sets. Remark 2 resolves a problem of Kuba posed in 1997 on the uniqueness in the case $d=m=3$ with $u_1,u_2,u_3$ being the standard unit vectors. Remark 3 determines the computational complexity of finding a smallest set J of positions whose disclosure yields uniqueness. As a corollary, we obtain a hardness result for 0-1-polytopes.

The task of reconstructing binary images from the knowledge of their line sums (discrete X-rays) in a given finite number m of directions is ill-posed. Even some small noise in the physical measurements can lead to dramatically different yet still unique solutions. The present paper addresses in particular the following problems. Does discrete tomography have the power of error correction? Can noise be compensated by taking more X-ray images, and, if so, what is the quantitative effect of taking one more X-ray? Our main theorem gives the first nontrivial unconditioned (and best possible) stability result. In particular, we show that the Hamming distance between any two different sets of m X-ray images of the same cardinality is at least 2(m-1), and this is best possible. As a consequence, this result implies a Rényi-type theorem for denoising and shows that the noise compensating effect of X-rays is linear in their number. Our theoretical results are complemented by determining the computational complexity of some underlying algorithmic tasks. In particular, we show that while there always is a certain inherent stability, the possibility of making (worst-case) efficient use of it is rather limited.

We describe a deterministic polynomial-time algorithm which, for a convex body K in Euclidean n-space, finds upper and lower bounds on K's diameter which differ by a factor of O(/spl radic/n/logn). We show that this is, within a constant factor, the best approximation to the diameter that a polynomial-time algorithm can produce even if randomization is allowed. We also show that the above results hold for other quantities similar to the diameter-namely; inradius, circumradius, width, and maximization of the norm over K. In addition to these results for Euclidean spaces, we give tight results for the error of deterministic polynomial-time approximations of radii and norm-maxima for convex bodies in finite-dimensional l/sub p/ spaces.

This paper gives various (positive and negative) results on the complexity of the problem of computing and approximating mixed volumes of polytopes and more general convex bodies in arbitrary dimension. On the negative side, we present several $#\P$-hardness results that focus on the difference of computing mixed volumes versus computing the volume of polytopes. We show that computing the volume of zonotopes is $#\P$-hard (while each corresponding mixed volume can be computed easily) but also give examples showing that computing mixed volumes is hard even when computing the volume is easy. On the positive side, we derive a randomized algorithm for computing the mixed volumes $$ V(\overbrace{K_1\ld K_1}^{m_1}, \overbrace{K_2,\dots,K_2}^{m_2},\dots,\overbrace{K_s,\dots,K_s}^{m_s}) $$ of well-presented convex bodies $K_1,\dots,K_s$, where $m_1,\dots,m_s \in \N_0$ and $m_1 \geq n-\psi(n)$ with $\psi(n)=o(\frac{\log n}{\log \log n})$. The algorithm is an interpolation method based on polynomial-time randomized algorithms for computing the volume of convex bodies. This paper concludes with applications of our results to various problems in discrete mathematics, combinatorics, computational convexity, algebraic geometry, geometry of numbers, and operations research.

Article Free Access Share on A polynomial time algorithm for Minkowski reconstruction Authors: Peter Gritzmann Universität Trier, Fb IV, Mathematik, D-54286 Trier, Germany Universität Trier, Fb IV, Mathematik, D-54286 Trier, GermanyView Profile , Alexander Hufnagel Universität Trier, Fb IV, Mathematik, D-54286 Trier, Germany Universität Trier, Fb IV, Mathematik, D-54286 Trier, GermanyView Profile Authors Info & Claims SCG '95: Proceedings of the eleventh annual symposium on Computational geometrySeptember 1995 Pages 1–9https://doi.org/10.1145/220279.220280Online:01 September 1995Publication History 2citation276DownloadsMetricsTotal Citations2Total Downloads276Last 12 Months9Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper deals with a problem from computational convexity and its application to computer algebra. This paper determines the complexity of computing the Minkowski sum of k convex polytopes in $\mathbb{R}^d $, which are presented either in terms of vertices or in terms of facets. In particular, if the dimension d is fixed, the authors obtain a polynomial time algorithm for adding k polytopes with up to n vertices. The second part of this paper introduces dynamic versions of Buchberger’s Gröbner bases algorithm for polynomial ideals. Using the Minkowski addition of Newton polytopes, the authors show that the following problem can be solved in polynomial time for any finite set of polynomials $\mathcal{T} \subset K [ x_1 , \ldots ,x_d ]$, where d is fixed: Does there exist a term order $\tau $ such that $\mathcal{T}$ is a Gröbner basis for its ideal with respect to $\tau $? If not, find an optimal term order for $\mathcal{T}$ with respect to a natural Hilbert function criterion.

The “radii” considered here are the inradius $\rho $, the circumradius R, the diameter $\delta $, and the width $\Delta $. The convex polygons in question have their vertices at points of the integer lattice in $\mathbb{R}^2 $, and their radii are measured with respect to an $\ell ^p $ norm. Computation of these radii for convex polygons (and of their higher-dimensional analogues for convex polytopes) is of interest in connection with a number of applications, and may be regarded as a basic problem in computational geometry. The terms good radius and bad radius refer to the existence or nonexistence of a rationalizing polynomial—a nonconstant rational polynomial q such that $q(\varphi (C))$ is rational whenever C is a convex lattice polygon and $\varphi $ is the radius function in question. When a radius is good, the polynomial is a tool for implicit computation of the radius in the binary model of computation; otherwise it seems to be necessary to resort to approximation. It is proved here that all four radii are good when $p \in \{ 1,\infty \} $, while $\delta $ is good when p is an integer and $\Delta $ is good when $p / (p - 1)$ is an integer. Thus $\delta $ and $\Delta $ are both good when $p = 2$, and it turns out that R is also good in this case. However, the main results are that r is bad when $p = 2$ and R is bad for each integer $p \geq 3$.

Article Free AccessOn the limited power of linear probes and other optimization oracles Authors: Peter Gritzmann Universität Augsburg, Institut für Mathematik, Universitätsstr. 8, D-8900 Augsburg, Federal Republic of Germany Universität Augsburg, Institut für Mathematik, Universitätsstr. 8, D-8900 Augsburg, Federal Republic of GermanyView Profile , Victor Klee Department of Mathematics, University of Washington, Seattle, Washington Department of Mathematics, University of Washington, Seattle, WashingtonView Profile , John Westwater Department of Mathematics, University of Washington, Seattle, Washington Department of Mathematics, University of Washington, Seattle, WashingtonView Profile Authors Info & Claims SCG '90: Proceedings of the sixth annual symposium on Computational geometryMay 1990 Pages 92–101https://doi.org/10.1145/98524.98544Published:01 May 1990Publication History 1citation10DownloadsMetricsTotal Citations1Total Downloads10Last 12 Months3Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF