Interpolating solutions of the Poisson equation in the disk based on Radon projections

We consider an algebraic method for reconstruction of a function satisfying the Poisson equation with a polynomial right-hand side in the unit disk. The given data, besides the right-hand side, is assumed to be in the form of a finite number of values of Radon projections of the unknown function. We first homogenize the problem by finding a polynomial which satisfies the given Poisson equation. This leads to an interpolation problem for a harmonic function, which we solve in the space of harmonic polynomials using a previously established method. For the special case where the Radon projections are taken along chords that form a regular convex polygon, we extend the error estimates from the harmonic case to this Poisson problem. Finally we give some numerical examples.     

Interpolation of harmonic functions based on Radon projections

We consider an algebraic method for reconstruction of a harmonic function in the unit disk via a finite number of values of its Radon projections. The approach is to seek a harmonic polynomial which matches given values of Radon projections along some chords of the unit circle. We prove an analogue of the famous Marr’s formula for computing the Radon projection of the basis orthogonal polynomials in our setting of harmonic polynomials. Using this result, we show unique solvability for a family of schemes where all chords are chosen at equal distance to the origin. For the special case of chords forming a regular convex polygon, we prove error estimates on the unit circle and in the unit disk. We present an efficient reconstruction algorithm which is robust with respect to noise in the input data and provide numerical examples.     

Upper bounds for the perimeter of plane convex bodies

We show that the maximum total perimeter of k plane convex bodies with disjoint interiors lying inside a given convex body C is equal to $\operatorname{per}\, (C)+2(k-1)\operatorname{diam}\, (C)$ , in the case when C is a square or an arbitrary triangle. A weaker bound is obtained for general plane convex bodies. As a consequence, we establish a bound on the perimeter of a polygon with at most k reflex angles lying inside a given plane convex body.     

Non-crossing matchings of points with geometric objects

Given an ordered set of points and an ordered set of geometric objects in the plane, we are interested in finding a non-crossing matching between point–object pairs. In this paper, we address the algorithmic problem of determining whether a non-crossing matching exists between a given point–object pair. We show that when the objects we match the points to are finite point sets, the problem is NP-complete in general, and polynomial when the objects are on a line or when their size is at most 2. When the objects are line segments, we show that the problem is NP-complete in general, and polynomial when the segments form a convex polygon or are all on a line. Finally, for objects that are straight lines, we show that the problem of finding a min-max non-crossing matching is NP-complete.     

Optimal Synthesis in a Model Problem with Two-Dimensional Control Lying in an Arbitrary Convex Set

Mathematical Notes - We consider a model nilpotent convex problem with two-dimensional control from an arbitrary convex set Ω. For the case in which Ω is a polygon, the problem is solved...     

Prior Learning and Convex-Concave Regularization of Binary Tomography

In our previous work, we introduced a convex-concave regularization approach to the reconstruction of binary objects from few projections within a limited range of angles. A convex reconstruction functional, comprising the projections equations and a smoothness prior, was complemented with a concave penalty term enforcing binary solutions. In the present work we investigate alternatives to the smoothness prior in terms of probabilistically learnt priors encoding local object structure. We show that the difference-of-convex-functions DC-programming framework is flexible enough to cope with this more general model class. Numerical results show that reconstruction becomes feasible under conditions where our previous approach fails.     

Family constraining of iterative algorithms

In constraining iterative processes, the algorithmic operator of the iterative process is pre-multiplied by a constraining operator at each iterative step. This enables the constrained algorithm, besides solving the original problem, also to find a solution that incorporates some prior knowledge about the solution. This approach has been useful in image restoration and other image processing situations when a single constraining operator was used. In the field of image reconstruction from projections a priori information about the original image, such as smoothness or that it belongs to a certain closed convex set, may be used to improve the reconstruction quality. We study here constraining of iterative processes by a family of operators rather than by a single operator.     

Isodiametric Problems for Polygons

The maximal area of a polygon with n = 2m edges and unit diameter is not known when m ≥ 5, nor is the maximal perimeter of a convex polygon with n = 2^m edges and unit diameter known when m ≥ 4. We construct improved polygons in both problems, and show that the values we obtain cannot be improved for large n by more than c₁/n³ in the area problem and c₂/n⁵ in the perimeter problem, for certain constants c₁ and c₂.     

Tomographic reconstruction using heuristic Monte Carlo methods

A tomographic reconstruction method based on Monte Carlo random searching guided by the information contained in the projections of radiographed objects is presented. In order to solve the optimization problem, a multiscale algorithm is proposed to reduce computation. The reconstruction is performed in a coarse-to-fine multigrid scale that initializes each resolution level with the reconstruction of the previous coarser level, which substantially improves the performance. The method was applied to a real case reconstructing the internal structure of a small metallic object with internal components, showing excellent results.     

广义重心坐标与凸多胞形的性质

提出n维欧氏空间中广义重心坐标的概念,建立了广义重心坐标下两点间的距离公式,并利用于研究凸多胞形的若干性质,将欧氏平面上凸多边形的一些定值与极值性质推广到n维空间.     

Quantum convex support

Convex support, the mean values of a set of random variables, is central in information theory and statistics. Equally central in quantum information theory are mean values of a set of observables in a finite-dimensional C^∗-algebra A, which we call (quantum) convex support. The convex support can be viewed as a projection of the state space of A and it is a projection of a spectrahedron.Spectrahedra are increasingly investigated at least since the 1990s boom in semi-definite programming. We recall the geometry of the positive semi-definite cone and of the state space. We write a convex duality for general self-dual convex cones. This restricts to projections of state spaces and connects them to results on spectrahedra.Our main result is an analysis of the face lattice of convex support by mapping this lattice to a lattice of orthogonal projections, using natural isomorphisms. The result encodes the face lattice of the convex support into a set of projections in A and enables the integration of convex geometry with matrix calculus or algebraic techniques.     

On reconstruction of objects from measurements of the diffracted field (*)

The aim of this paper is the shape restoration of a plane object from measurements of its diffracted field at a discrete and finite set of points. The plane sampling lattice is supposed: i) rectangular; ii)periodic.

The problem is approached as an interpolation one. A numerical algorithm for practical reconstructions is presented. A-priori limitations on the perimeter of the object and conditions on the samples lead to a-priori bounds able to estimate the precision of the reconstruction.     

Convex equipartitions via Equivariant Obstruction Theory

We describe a regular cell complex model for the configuration space F(? ^d , n). Based on this, we use Equivariant Obstruction Theory to prove the prime power case of the conjecture by Nandakumar and Ramana Rao that every polygon can be partitioned into n convex parts of equal area and perimeter.     

Hyperbolic polygons of minimal perimeter with given angles

We prove that, among all convex hyperbolic polygons with given angles, the perimeter is minimized by the unique polygon with an inscribed circle. The proof relies on work of Schlenker (Trans Am Math Soc 359(5): 2155–2189, 2007).     

The perimeter of rounded convex planar sets

A convex set is inscribed into a rectangle with sides a and 1/a so that the convex set has points on all four sides of the rectangle. By “rounding” we mean the composition of two orthogonal linear transformations parallel to the edges of the rectangle, which makes a unit square out of the rectangle. The transformation is also applied to the convex set, which now has the same area, and is inscribed into a square. One would expect this transformation to decrease the perimeter of the convex set as well. Interestingly, this is not always the case. For each a we determine the largest and smallest possible increase of the perimeter.      

Reconstructing orthogonal polyhedra from putative vertex sets

In this paper we study the problem of reconstructing orthogonal polyhedra from a putative vertex set, i.e., we are given a set of points and want to find an orthogonal polyhedron for which this is the set of vertices. This is well-studied in 2D; we mostly focus on 3D, and on the case where the given set of points may be rotated beforehand. We obtain fast algorithms for reconstruction in the case where the answer must be orthogonally convex.     

Offset-polygon annulus placement problems

An offset-polygon annulus region is defined in terms of a polygon P and a distance δ > 0 (offset of P). In this paper we solve several containment problems for polygon annulus regions with respect to an input point set. Optimization criteria include both maximizing the number of points contained in a fixed size annulus and minimizing the size of the annulus needed to contain all points. We address the following variants of the problem: placement of an annulus of a convex polygon as well as of a simple polygon; placement by translation only, or by translation and rotation; off-line and on-line versions of the corresponding decision problems; and decision as well as optimization versions of the problems. We present efficient algorithms in each case.     

Finding the projection of a point onto the intersection of convex sets via projections onto half-spaces

We present a modification of Dykstra's algorithm which allows us to avoid projections onto general convex sets. Instead, we calculate projections onto either a half-space or onto the intersection of two half-spaces. Convergence of the algorithm is established and special choices of the half-spaces are proposed.The option to project onto half-spaces instead of general convex sets makes the algorithm more practical. The fact that the half-spaces are quite general enables us to apply the algorithm in a variety of cases and to generalize a number of known projection algorithms.The problem of projecting a point onto the intersection of closed convex sets receives considerable attention in many areas of mathematics and physics as well as in other fields of science and engineering such as image reconstruction from projections.In this work we propose a new class of algorithms which allow projection onto certain super half-spaces, i.e., half-spaces which contain the convex sets. Each one of the algorithms that we present gives the user freedom to choose the specific super half-space from a family of such half-spaces. Since projecting a point onto a half-space is an easy task to perform, the new algorithms may be more useful in practical situations in which the construction of the super half-spaces themselves is not too difficult.     

On the feasible set for the squared Euclidean Weber problem and applications

In this paper we find the set of feasible solution points to the Weber location problem with squared Euclidean distances when the weights can be at any point in a given set of intervals. We prove that this set is a convex polygon. The result is then used to solve the minimax regret objective when individual scenarios can be any set of weights in a given set of intervals.