Gauge Distances and Median Hyperplanes

A median hyperplane in d-dimensional space minimizes the weighted sum of the distances from a finite set of points to it. When the distances from these points are measured by possibly different gauges, we prove the existence of a median hyperplane passing through at least one of the points. When all the gauges are equal, some median hyperplane will pass through at least d-1 points, this number being increased to d when the gauge is symmetric, i.e. the gauge is a norm.Whereas some of these results have been obtained previously by different methods, we show that they all derive from a simple formula for the distance of a point to a hyperplane as measured by an arbitrary gauge.     

Anchored Hyperplane Location Problems

   Abstract. The anchored hyperplane location problem is to locate a hyperplane passing through some given points P

Centers and shore points of a dendroid

A bottleneck in a dendroid is a continuum that intersects every arc connecting two nonempty open sets. Every dendroid contains a point called a center which is contained in arbitrarily small bottlenecks. A subset A of a dendroid is a shore set if for every ε>0 there is a continuum in D?A with Hausdorff distance from D less than ε. If a shore set has only one point it is called a shore point. This paper explores the relationship between center points and shore points in a dendroid. We show that if a dendroid contains a strong center, then any finite union of the arc components of the set of shore points is a shore set.     

Probabilistic analysis of geometric location problems

We analyze the behaviour of thek center and median problems forn points randomly distributed in an arbitrary regionA ofR ^d . Under a mild assumption on the regionA, we show that fork≦k(n)=o(n/logn), the objective function values of the discrete and continuous versions of these problems are equal to each otheralmost surely. For the two-dimensional case, both these problems can be solved by placing the centers or medians in an especially simple regular hexagonal pattern (the ‘honeycomb heuristic’ of Papadimitriou). This yields the exact asymptotic values for thek center and median problem, namely, α(|A|/k)^1/2 and β(|A|/k)^1/2, where |A| denotes the volume ofA, α and β are known constants, and the objective of the median problem is given in terms of the average, rather than the usual total, distance. For the 3- and 4-dimensional case, similar results can be obtained for the center problem to within an accuracy of roughly one percent. As a by-product, we also get asymptotically optimal algorithms for the 2-dimensionalp-normk median problem and for the twin problems of minimizing the maximum number of vertices served by any center and similarly for maximizing the minimum.     

Two Characterizations of Smooth Norms

In an arbitrary Minkowski space M, n2, let there be given an arbitrary finite set P of weighted points whose affine hull is n-dimensional. We show that the unit ball B of M has smooth boundary if and only if each median hyperplane (minimizing the sum of weighted distances with respect to P) is spanned by n affinely independent points from P. Moreover, B has the same property if and only if every center hyperplane (minimizing the maximal weighted distance with respect to P) has the same maximal distance to at least n+1 affinely independent points from P.     

An upper bound for the minimum diameter of integral point sets

For alln> d there existn points in the Euclidean spaceE ^d such that not all points are in a hyperplane and all mutual distances are integral. It is proved that the minimum diameter of such integral point sets has an upper bound of 2 ^{c logn log logn} .     

Exact formulas for the proximal/regular/limiting normal cone of the second-order cone complementarity set

In this paper we address the problem of locating a new facility on a d-dimensional space when the distance measure (\(\ell _p\)- or polyhedral-norms) is different at each one of the sides of a given hyperplane \(\mathcal {H}\). We relate this problem with the physical phenomenon of refraction, and extend it to any finite dimensional space and different distances at each one of the sides of any hyperplane. An application to this problem is the location of a facility within or outside an urban area where different distance measures must be used. We provide a new second order cone programming formulation, based on the \(\ell _p\)-norm representation given in Blanco et al. (Comput Optim Appl 58(3):563–595, 2014) that allows to solve the problem in any finite dimensional space with second order cone or semidefinite programming tools. We also extend the problem to the case where the hyperplane is considered as a rapid transit media (a different third norm is also considered over \(\mathcal {H}\)) that allows the demand to travel, whenever it is convenient, through \(\mathcal {H}\) to reach the new facility. Extensive computational experiments run in Gurobi are reported in order to show the effectiveness of the approach. Some extensions of these models are also presented.     

Selecting distances in arrangements of hyperplanes spanned by points

In this paper we consider a problem of distance selection in the arrangement of hyperplanes induced by n given points. Given a set of n points in d-dimensional space and a number k, , determine the hyperplane that is spanned by d points and at distance ranked by k from the origin. For the planar case we present an O(nlog²n) runtime algorithm using parametric search partly different from the usual approach [N. Megiddo, J. ACM 30 (1983) 852]. We establish a connection between this problem in 3-d and the well-known 3SUM problem using an auxiliary problem of counting the number of vertices in the arrangement of n planes that lie between two sheets of a hyperboloid. We show that the 3-d problem is almost 3SUM-hard and solve it by an O(n²log²n) runtime algorithm. We generalize these results to the d-dimensional (d4) space and consider also a problem of enumerating distances.     

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.     

Un analogue elliptique du théorème de Roth

We present here quantitative versions, in dimension one, of Faltings' theorem according to which the set of K-rational points (where K is a given number field) of an Abelian variety A defined over K, which are close (with respect to a v-adic distance on K) to some K-subvariety X of A, but do not belong to X, is finite. More precisely, we treat the case where A is an elliptic curve and X is reduced to a point of A and we give (in this case) explicit bounds for the cardinal of the exceptional finite set. We consider also, more generally, not only one place v of K, but also a finite set S of places of K and the distance from the point of A to X, which takes into account all the places of S. To cite this article: B. Farhi, C. R. Acad. Sci. Paris, Ser. I 341 (2005).     

Alternating local search based VNS for linear classification

We consider the linear classification method consisting of separating two sets of points in d-space by a hyperplane. We wish to determine the hyperplane which minimises the sum of distances from all misclassified points to the hyperplane. To this end two local descent methods are developed, one grid-based and one optimisation-theory based, and are embedded into a VNS metaheuristic scheme. Computational results show these approaches to be complementary, leading to a single hybrid VNS strategy which combines both approaches to exploit the strong points of each. Extensive computational tests show that the resulting method can always be expected to approach the global optimum close enough that any deviations from the global optimum are irrelevant with respect to the classification power.     

Linear separation and approximation by minimizing the sum of concave functions of distances

One recently proposed criterion to separate two data sets in Classification is to use a hyperplane that minimizes the sum of distances to it from all the misclassified data points, where misclassification means lying on the wrong side of the hyperplane, or rather in the wrong halfspace. In this paper we study an extension of this problem: we seek the hyperplane minimizing the sum of concave nondecreasing functions of the distances of misclassified points to it. It is shown that an optimal hyperplane exists containing at least $d$ affinely independent points. This extends the result known for the minimization of the sum of distances, and enables to use combinatorial local-search heuristics for this problem. As a corollary, the same result is obtained for the approximation problem in which a hyperplane minimizing the sum of concave nondecreasing functions of the distances from a set of data points is sought.     

A combinatorial perspective on the non-Radon partitions

Let E be a finite set of points in $\text{R}$^d. Then {A, E ? A} is a non-Radon partition of E iff there is a hyperplane H separating A strictly from E?A. Or equivalently iff ${}_{\mathrm{<mtext>A</mtext>}}\text{O}$ is an acyclic reorientation of (M_Aff(E), O), the oriented matroid canonically determined by E. If (M(E), O) is an oriented matroid without loops then the set $\text{NR(E, O) = {(A, E ? A):}{}_{\mathrm{<mtext>A</mtext>}}\text{O}\text{is acyclic}\text{}}$ determines (M(E), O). In particular the matroidal properties of a finite set of points in $\text{R}$^d are precisely the properties which can be formulated in non-Radon partitions terms. The Möbius function of the poset $\text{A = {A: A ? E,}{}_{\mathrm{<mtext>A</mtext>}}\text{O}\text{is acyclic}\text{}}$ and in a special case its homotopy type are computed. This paper generalizes recent results of P. Edelman (A partial order on the regions of $\text{R}$ⁿ dissected by hyperplanes     

A correction to the definition of local center

It is known that in order to solve the minimax facility location problem on a graph with a finite set of demand points, only a finite set of possible location points, called ‘local centers’ must be considered.It has been shown that the continuous m-center problem on a graph can be solved by using a series of set covering problems in which each local center covers the demand points at a distance not greater than a corresponding number called ‘the range’ of the local center.However, all points which are at the same distance from more than two demand points, and from which there is no direction where all these distances are decreasing, must also be considered as local centers. This paper proves that, in some special cases, it is not sufficient to consider only the points where this occurs with respect to pairs of demand points. The definition of local center is corrected and the corresponding results and algorithms are revised.     

Two special cases of the assignment problem

The assignment problem may be stated as follows: Given finite sets of points S and T, with|S| ? |T|, and given a “metric” which assigns a distance d(x, y) to each pair (x, y) such that x ∈ T and y ∈ S find a 1?1 function Q: T→ S which minimizes Σ_x∈Td(x, Q(x)) We consider the two special cases in which the points lie (1) on a line segment and (2) on a circle, and the metric is the distance along the line segment or circle, respectively. In each case, we show that the optimal assignment Q can be computed in a number of steps (additions and comparisons) proportional to the number of points. The problem arose in connection with the efficient rearrangement of desks located in offices along a corridor which encircles one floor of a building.     

On finite matroids with two more hyperplanes than points

One of the most interesting results about finite matroids of finite rank and generalized projective spaces is the result of Basterfield, Kelly and Green (1968/1970) (J.G. Basterfield, L.M. Kelly, A characterization of sets of n points which determine n hyperplanes, in: Proceedings of the Cambridge Philosophical Society, vol. 64, 1968, pp. 585-588; C. Greene, A rank inequality for finite geometric lattices, J. Combin Theory 9 (1970) 357-364) affirming that any matroid contains at least as many hyperplanes as points, with equality in the case of generalized projective spaces. Consequently, the goal is to characterize and classify all matroids containing more hyperplanes than points. In 1996, I obtained the classification of all finite matroids containing one more hyperplane than points. In this paper a complete classification of finite matroids with two more hyperplanes than points is obtained. Moreover, a partial contribution to the classification of those matroids containing a certain number of hyperplanes more than points is presented.     

Cutting dense point sets in half

A halving hyperplane of a set S of n points in R ^d contains d affinely independent points of S so that equally many of the points off the hyperplane lie in each of the two half-spaces. We prove bounds on the number of halving hyperplanes under the condition that the ratio of largest over smallest distance between any two points is at most , δ some constant. Such a set S is called dense. In d = 2 dimensions the number of halving lines for a dense set can be as much as , and it cannot exceed . The upper bound improves over the current best bound of which holds more generally without any density assumption. In d = 3 dimensions we show that is an upper bound on the number of halving planes for a dense set. The proof is based on a metric argument that can be extended to d≥ 4 dimensions, where it leads to as an upper bound for the number of halving hyperplanes. Received March 22, 1995, and in revised form January 15, 1996.     

Colorings of the space ℝn with several forbidden distances

The paper is concerned with the classical problem concerning the chromatic number of a metric space, i.e., the minimal number of colors required to color all points in the space so that the distance (the value of the metric) between points of the same color does not belong to a given set of positive real numbers (the set of forbidden distances). New bounds for the chromatic number are obtained for the case in which the space is ?ⁿ with a metric generated by some norm (in particular, l _p) and the set of forbidden distances either is finite or forms a lacunary sequence.