Locating least-distant lines in the plane

In this paper we deal with locating a line in a plane. Given a set of existing facilities, represented by points in the plane, our objective is to find a straight line l minimizing the sum of weighted distances to the existing facilities, or minimizing the maximum weighted distance to the existing facilities, respectively. We show that for all distance measures derived from norms, one of the lines minimizing the sum objective contains at least two of the existing facilities. For the center objective we always get an optimal line which is at maximum distance from at least three of the existing facilities. If all weights are equal, there is an optimal line which is parallel to one facet of the convex hull of the existing facilities.     

Properties of Three-Dimensional Median Line Location Models

We consider the problem of locating a line with respect to some existing facilities in 3-dimensional space, such that the sum of weighted distances between the line and the facilities is minimized. Measuring distance using the l _p norm is discussed, along with the special cases of Euclidean and rectangular norms. Heuristic solution procedures for finding a local minimum are outlined.     

Minmax-distance approximation and separation problems: geometrical properties

A center hyperplane in the d-dimensional space minimizes the maximum of its distances from a finite set of points A with respect to possibly different gauges. In this note it is shown that a center hyperplane exists which is at (equal) maximum distance from at least d?+?1 points of A. Moreover the projections of the points among these which lie above the center hyperplane cannot be separated by another hyperplane from the projections of those that are below it. When all gauges involved are smooth, all center hyperplanes satisfy these properties. This geometric property allows us to improve and generalize previously existing results, which were only known for the case in which all distances are measured using a common norm. The results also extend to the constrained case where for some points it is prespecified on which side of the hyperplane (above, below or on) they must lie. In this case the number of points lying on the hyperplane plus those at maximum distance is at least d?+?1. It follows that solving such global optimization problems reduces to inspecting a finite set of candidate solutions. Extensions of these results to a separation problem are outlined.     

On the sum of distances along a circle

The arc distance between two points on a circle is their geodesic distance along the circle. We study the sum of the arc distances determined by n points on a circle, which is a useful measure of the evenness of scales and rhythms in music theory. We characterize the configurations with the maximum sum of arc distances by a balanced condition: for each line that goes through the circle center and touches no point, the numbers of points on each side of the line differ by at most one. When the points are restricted to lattice positions on a circle, we show that Toussaint's snap heuristic finds an optimal configuration. We derive closed-form formulas for the maximum sum of arc distances when the points are either allowed to move continuously on the circle or restricted to lattice positions. We also present a linear-time algorithm for computing the sum of arc distances when the points are presorted by the polar coordinates.     

On 5-isosceles sets in the plane, with linear restriction

A finite planar set is k-isosceles for k≥3 if every k-point subset of the set contains a point equidistant from two others. We show that an 8-set on a line is 5-isosceles if and only if its adjacent interpoint distances are equal to each other, and no 5-isosceles 9-set has 9 points on a line. We also show that the maximum 5-isosceles set with 8 points on a line contains at most 10 points.     

Evaluation of nondominated solution sets for k-objective optimization problems: An exact method and approximations

Integrated Preference Functional (IPF) is a set functional that, given a discrete set of points for a multiple objective optimization problem, assigns a numerical value to that point set. This value provides a quantitative measure for comparing different sets of points generated by solution procedures for difficult multiple objective optimization problems. We introduced the IPF for bi-criteria optimization problems in [Carlyle, W.M., Fowler, J.W., Gel, E., Kim, B., 2003. Quantitative comparison of approximate solution sets for bi-criteria optimization problems. Decision Sciences 34 (1), 63–82]. As indicated in that paper, the computational effort to obtain IPF is negligible for bi-criteria problems. For three or more objective function cases, however, the exact calculation of IPF is computationally demanding, since this requires k (⩾3) dimensional integration.In this paper, we suggest a theoretical framework for obtaining IPF for k (⩾3) objectives. The exact method includes solving two main sub-problems: (1) finding the optimality region of weights for all potentially optimal points, and (2) computing volumes of k dimensional convex polytopes. Several different algorithms for both sub-problems can be found in the literature. We use existing methods from computational geometry (i.e., triangulation and convex hull algorithms) to develop a reasonable exact method for obtaining IPF. We have also experimented with a Monte Carlo approximation method and compared the results to those with the exact IPF method.     

Finding efficient solutions for rectilinear distance location problems efficiently

Given n planar existing facility locations, a planar new facility location X is called efficient if there is no other location Y for which the rectilinear distance between Y and each existing facility is at least as small as between X and each existing facility, and strictly less for at least one existing facility. Rectilinear distances are typically used to measure travel distances between points via rectilinear aisles or street networks. We first present a simple arrow algorithm, based entirely on geometrical analysis, that constructs all efficient locations. We then present a row algorithm which is of order n(log n) that constructs all efficient locations, and establish that no alternative algorithm can be of a lower order.     

Approximating largest convex hulls for imprecise points

Assume that a set of imprecise points in the plane is given, where each point is specified by a region in which the point will lie. Such a region can be modelled as a circle, square, line segment, etc. We study the problem of maximising the area of the convex hull of such a set. We prove NP-hardness when the imprecise points are modelled as line segments, and give linear time approximation schemes for a variety of models, based on the core-set paradigm.     

Solving the uncapacitated multi-facility Weber problem by vector quantization and self-organizing maps

The uncapacitated multi-facility Weber problem is concerned with locating m facilities in the Euclidean plane and allocating the demands of n customers to these facilities with the minimum total transportation cost. This is a non-convex optimization problem and difficult to solve exactly. As a consequence, efficient and accurate heuristic solution procedures are needed. The problem has different types based on the distance function used to model the distance between the facilities and customers. We concentrate on the rectilinear and Euclidean problems and propose new vector quantization and self-organizing map algorithms. They incorporate the properties of the distance function to their update rules, which makes them different from the existing two neural network methods that use rather ad hoc squared Euclidean metric in their updates even though the problem is originally stated in terms of the rectilinear and Euclidean distances. Computational results on benchmark instances indicate that the new methods are better than the existing ones, both in terms of the solution quality and computation time.     

Reprint of: Extreme point and halving edge search in abstract order types

Many properties of finite point sets only depend on the relative position of the points, e.g., on the order type of the set. However, many fundamental algorithms in computational geometry rely on coordinate representations. This includes the straightforward algorithms for finding a halving line for a given planar point set, as well as finding a point on the convex hull, both in linear time. In his monograph Axioms and Hulls, Knuth asks whether these problems can be solved in linear time in a more abstract setting, given only the orientation of each point triple, i.e., the setʼs chirotope, as a source of information. We answer this question in the affirmative. More precisely, we can find a halving line through any given point, as well as the vertices of the convex hull edges that are intersected by the supporting line of any two given points of the set in linear time. We first give a proof for sets realizable in the Euclidean plane and then extend the result to non-realizable abstract order types.     

Extreme point and halving edge search in abstract order types

Many properties of finite point sets only depend on the relative position of the points, e.g., on the order type of the set. However, many fundamental algorithms in computational geometry rely on coordinate representations. This includes the straightforward algorithms for finding a halving line for a given planar point set, as well as finding a point on the convex hull, both in linear time. In his monograph Axioms and Hulls, Knuth asks whether these problems can be solved in linear time in a more abstract setting, given only the orientation of each point triple, i.e., the set?s chirotope, as a source of information. We answer this question in the affirmative. More precisely, we can find a halving line through any given point, as well as the vertices of the convex hull edges that are intersected by the supporting line of any two given points of the set in linear time. We first give a proof for sets realizable in the Euclidean plane and then extend the result to non-realizable abstract order types.     

Convex solution of a permutation problem

In this paper, we show that a problem of finding a permuted version of k vectors from R^N such that they belong to a prescribed rank r subset, can be solved by convex optimization. We prove that under certain generic conditions, the wanted permutation matrix is unique in the convex set of doubly-stochastic matrices. In particular, this implies a solution of the classical correspondence problem of finding a permutation that transforms one collection of points in R^k into the another one. Solutions to these problems have a wide set of applications in Engineering and Computer Science.     

Link distance and shortest path problems in the plane

This paper describes algorithms to compute Voronoi diagrams, shortest path maps, the Hausdorff distance, and the Fréchet distance in the plane with polygonal obstacles. The underlying distance measures for these algorithms are either shortest path distances or link distances. The link distance between a pair of points is the minimum number of edges needed to connect the two points with a polygonal path that avoids a set of obstacles. The motivation for minimizing the number of edges on a path comes from robotic motions and wireless communications because turns are more difficult in these settings than straight movements.Link-based Voronoi diagrams are different from traditional Voronoi diagrams because a query point in the interior of a Voronoi face can have multiple nearest sites. Our site-based Voronoi diagram ensures that all points in a face have the same set of nearest sites. Our distance-based Voronoi diagram ensures that all points in a face have the same distance to a nearest site.The shortest path maps in this paper support queries from any source point on a fixed line segment. This is a middle-ground approach because traditional shortest path maps typically support queries from either a fixed point or from all possible points in the plane.The Hausdorff distance and Fréchet distance are fundamental similarity metrics for shape matching. This paper shows how to compute new variations of these metrics using shortest paths or link-based paths that avoid polygonal obstacles in the plane.     

平面上端点受约束的一种随机点配线

对于平面上有限个随机点,推导了配一条端点受直线段约束的直线的最优选址的公式算法.其中目标函数是加权距离平方和的数学期望.     

A projected Weiszfeld algorithm for the box-constrained Weber location problem

The Weber problem consists of finding a point in Rⁿ that minimizes the weighted sum of distances from m points in Rⁿ that are not collinear. An application that motivated this problem is the optimal location of facilities in the 2-dimensional case. A classical method to solve the Weber problem, proposed by Weiszfeld in 1937, is based on a fixed-point iteration.In this work we generalize the Weber location problem considering box constraints. We propose a fixed-point iteration with projections on the constraints and demonstrate descending properties. It is also proved that the limit of the sequence generated by the method is a feasible point and satisfies the KKT optimality conditions. Numerical experiments are presented to validate the theoretical results.     

The minimum distance superset problem: formulations and algorithms

The partial digest problem consists in retrieving the positions of a set of points on the real line from their unlabeled pairwise distances. This problem is critical for DNA sequencing, as well as for phase retrieval in X-ray crystallography. When some of the distances are missing, this problem generalizes into a “minimum distance superset problem”, which aims to find a set of points of minimum cardinality such that the multiset of their pairwise distances is a superset of the input. We introduce a quadratic integer programming formulation for the minimum distance superset problem with a pseudo-polynomial number of variables, as well as a polynomial-size integer programming formulation. We investigate three types of solution approaches based on an available integer programming solver: (1) solving a linearization of the pseudo-polynomial-sized formulation, (2) solving the complete polynomial-sized formulation, or (3) performing a binary search over the number of points and solving a simpler feasibility or optimization problem at each step. As illustrated by our computational experiments, the polynomial formulation with binary search leads to the most promising results, allowing to optimally solve most instances with up to 25 distance values and 8 solution points.     

Harmonic Properties of the Logarithmic Potential and the Computability of Elliptic Fekete Points

We investigate the properties of the function sending each N-tuple of points to minus the logarithm of the product of their mutual distances. We prove that, as a function defined on the product of N spheres, this function is subharmonic, and indeed its (Riemannian) Laplacian is constant. We also prove a mean value equality and an upper bound on the derivative of the function. We use these results to get sharp upper bounds for the precision needed to describe an approximation to elliptic Fekete points (in the sense demanded by Smale’s 7th problem). We also conclude that Smale’s 7th problem has solutions given by rational spherical points of bounded (small) bit length, proving that there exists an exponential running time algorithm which solves it on the Turing machine model.     

The residual method for regularizing ill-posed problems

Although the residual method, or constrained regularization, is frequently used in applications, a detailed study of its properties is still missing. This sharply contrasts the progress of the theory of Tikhonov regularization, where a series of new results for regularization in Banach spaces has been published in the recent years. The present paper intends to bridge the gap between the existing theories as far as possible. We develop a stability and convergence theory for the residual method in general topological spaces. In addition, we prove convergence rates in terms of (generalized) Bregman distances, which can also be applied to non-convex regularization functionals.We provide three examples that show the applicability of our theory. The first example is the regularized solution of linear operator equations on L^p-spaces, where we show that the results of Tikhonov regularization generalize unchanged to the residual method. As a second example, we consider the problem of density estimation from a finite number of sampling points, using the Wasserstein distance as a fidelity term and an entropy measure as regularization term. It is shown that the densities obtained in this way depend continuously on the location of the sampled points and that the underlying density can be recovered as the number of sampling points tends to infinity. Finally, we apply our theory to compressed sensing. Here, we show the well-posedness of the method and derive convergence rates both for convex and non-convex regularization under rather weak conditions.     

Few distinct distances implies no heavy lines or circles

We study the structure of planar point sets that determine a small number of distinct distances. Specifically, we show that if a set \(\mathcal{P}\) of n points determines o(n) distinct distances, then no line contains Ω(n ^7/8) points of \(\mathcal{P}\) and no circle contains Ω(n ^5/6) points of \(\mathcal{P}\).We rely on the partial variant of the Elekes-Sharir framework that was introduced by Sharir, Sheffer, and Solymosi in [19] for bipartite distinct distance problems. To prove our bound for the case of lines we combine this framework with a theorem from additive combinatorics, and for our bound for the case of circles we combine it with some basic algebraic geometry and a recent incidence bound for plane algebraic curves by Wang, Yang, and Zhang [20].A significant difference between our approach and that of [19] (and of other related results) is that instead of dealing with distances between two point sets that are restricted to one-dimensional curves, we consider distances between one set that is restricted to a curve and one set with no restrictions on it.     

Location of an undesirable facility in a polygonal region with forbidden zones

In this paper, we develop the problem of locating an undesirable facility in a bounded polygonal region (with forbidden polygonal zones), using Euclidean distances, under an objective function that generalizes the maximin and maxisum criteria, and includes other criteria such as the linear combinations of these criterions. We identify a finite dominating set (finite set of points to which an optimal solution must belong) for this problem and show that an optimum solution can be found in polynomial time in the number of vertices of the polygons in the model and the number of existing facilities.