Search

The cut-and-project method may be applied to graphs and complexes, although there are technical difficulties, most notably “collisions,” i.e. when the images (under the projection) of two disjoint edges or cells intersect. Given a particular periodic structure, a particular projection space, an appropriate “window” in the orthogonal complement of that space, the induced substructure within the cartesian product of the window and the projection space is projected to the projection space to produce a “model structure.” We may use an index space of vectors from the orthogonal complement to move the window around and obtain a “model system” of model structures. We adapt the notion of “general position” to higher dimensions: the projection space is in “doubly general position” with respect to a graph or complex when the projection of that structure maps vertices of that structure injectively into the projection space and the edges or polytopes of that structure injectively so that their dimension is not reduced and disjoint edges and polytopes remain disjoint. We find that if the initial structure was a periodic graph, if the projection space and its complement are in general position with respect to the vertices and edges, and the window is also in general position, then the model system has uncountably many isomorphism classes - with distinct coordination sequences.

We are given a set S of points in the Euclidean plane. We assume that S is in general position. A simple polygon P is a surrounding polygon of S if each vertex of P is a point in S and every point in S is either inside P or a vertex of P . In this paper, we present an enumeration algorithm of the surrounding polygons for a given point set. Our algorithm is based on reverse search by Avis and Fukuda and enumerates all the surrounding polygons in polynomial delay and quadratic space. It also provides the first space efficient method to generate all simple polygonizations on a given point set in exponential time. By relating these two problems we provide an upper bound on the number of surrounding polygons.

Two-agent scheduling problems with the general position-dependent processing time are studied in this paper. Under the constraint that the makespan of one agent is upper bounded, we show that the problem to minimize the other agent's makespan on a single machine is NP-hard. A polynomial time algorithm is proposed for the problem with learning or deteriorating effects. To minimize the total completion time of one agent's jobs on a single machine, we design a dynamic programming algorithm and an FPTAS. Moreover, we also provide dynamic programming algorithms and FPTASs for the problem to minimize one agent's makespan and the problem to minimize the total completion time of the other agent's jobs on parallel machines.

We consider edge insertion and deletion operations that increase the connectivity of a given planar straight-line graph (PSLG), while minimizing the total edge length of the output. We show that every connected PSLG G = ( V , E ) in general position can be augmented to a 2-connected PSLG ( V , E ∪ E + ) by adding new edges of total Euclidean length ‖ E + ‖ 2 ‖ E ‖ , and this bound is the best possible. An optimal edge set E + can be computed in O ( | V | 4 ) time; however the problem becomes NP-hard when G is disconnected. Further, we show that there is a sequence of edge insertions and deletions that transforms a connected PSLG G = ( V , E ) into a planar straight-line cycle G ′ = ( V , E ′ ) such that ‖ E ′ ‖ ≤ 2 ‖ MST ( V ) ‖ , and the graph remains connected with edge length below ‖ E ‖ + ‖ MST ( V ) ‖ at all stages. These bounds are the best possible.

Let P be a set of n points in the plane in general position, and consider the problem of finding an axis-parallel rectangle with a given perimeter, or area, or diagonal, that encloses the maximum number of points of P. We present an exact algorithm that finds such a rectangle in O ( n 5 / 2 log ⁡ n ) time, and, for the case of a fixed perimeter or diagonal, we also obtain (i) an improved exact algorithm that runs in O ( n k 3 / 2 log ⁡ k ) time, and (ii) an approximation algorithm that finds, in O ( n + n k e 5 log 5 / 2 ⁡ n k log ⁡ ( 1 e log ⁡ n k ) ) time, a rectangle of the given perimeter that contains at least ( 1 − e ) k points of P, where k is the optimum value. We then show how to turn this algorithm into one that finds, for a given k, an axis-parallel rectangle of smallest perimeter (or area, or diagonal) that contains k points of P. We obtain the first subcubic algorithms for these problems, significantly improving the current state of the art.

Although 3D Voronoi diagrams and medial axis transforms have numerous applications in biology, robotics, and manufacturing, most researchers use Voronoi diagrams of points instead of the true 3D input geometry, due to issues of robustness and scalability. In this paper, we present a robust sample-based GPU algorithm for calculating the full topology of Voronoi diagrams of non-general position spheres. Prior work demonstrated that the presence, geometry, and combinatorial basis of spheres that contribute to Voronoi vertices can be efficiently computed by shooting rays from each input sphere, mapping ray intersections with the nearest bisector surface to parametric bounding cubes, and analyzing the results. In this paper, we propose an algorithm on this parametric bounding cube to compute Voronoi edges in addition to the vertices. We successfully extract the full topology of the Voronoi diagram, including special cases such as isolated Voronoi edges that do not contain Voronoi vertices, more than three Voronoi edges emanating from a Voronoi vertex, and Voronoi edges that are shared by more than three Voronoi cells. Our GPU implementation efficiently and robustly handles all input, whether in general or non-general position, and finds all Voronoi vertices and edges, modulo the sampling density, including isolated disconnected edges.

We consider sets L = { l 1 , … , l n } of n labeled lines in general position in R 3 , and study the order types of point sets { p 1 , … , p n } that stem from the intersections of the lines in L with (directed) planes Π, not parallel to any line of L , that is, the proper cross-sections of L . As two main results, we show that the number of different order types that can be obtained as cross-sections of L is O ( n 9 ) when considering all possible planes Π, and O ( n 3 ) when restricting considerations to sets of pairwise parallel planes, where both bounds are tight. The result for parallel planes implies that any set of n points in R 2 moving with constant (but possibly different) speeds along straight lines forms at most O ( n 3 ) different order types over time. We further generalize the setting from R 3 to R d with d > 3 , showing that the number of order types that can be obtained as cross-sections of a set of n labeled ( d − 2 ) -flats in R d with planes is O ( ( ( n 3 ) + n d ( d − 2 ) ) ) .

Data in Brief, 34, ISSN:2352-3409

In this paper, we study the problem of counting the number of convex empty polygons in a given set of n points in general position in the plane. We present two algorithms: one counts the number of all convex empty polygons in O ( T ) time and the other counts the number of convex empty m-gons for all 3 ≤ m ≤ k in O ( k T ) time, where T denotes the number of empty triangles in S. Note that T varies from Ω ( n 2 ) to O ( n 3 ) , while its expected value is known to be Θ ( n 2 ) when n input points are chosen uniformly and independently at random from a convex and bounded body.

Karasev conjectured that for any set of 3k lines in general position in the plane, which is partitioned into 3 color classes of equal size k, the set can be partitioned into k colorful 3-subsets such that all the triangles formed by the subsets have a point in common. Although the general conjecture is false, we show that Karasev's conjecture is true for lines in convex position. We also discuss possible generalizations of this result.

An n × n matrix D is a Euclidean distance matrix (EDM) if there exist points p 1 , … , p n in some Euclidean space such that d i j = ‖ p i − p j ‖ 2 for all i , j = 1 , … , n . Let D be an EDM and let E i j be the n × n symmetric matrix with 1's in the ijth and jith entries and 0's elsewhere. We say that [ l i j , u i j ] is the yielding interval of entry d i j if it holds that D + t E i j is an EDM if and only if l i j ≤ t ≤ u i j . If the yielding interval of entry d i j has length 0, i.e., if l i j = u i j = 0 , then d i j is said to be unyielding. Otherwise, if l i j ≠ u i j , then d i j is said to be yielding. Let d i j and d i k be two unyielding entries of D. We say that d i j and d i k are jointly yielding if D + t 1 E i j + t 2 E i k is an EDM for some nonzero scalars t 1 and t 2 . In this paper, we characterize the yielding and the jointly yielding entries of an EDM D in terms of Gale transforms of p 1 , … , p n . Moreover, for each yielding entry, we present explicit formulae of its yielding interval. Finally, we specialize our results to the case where points p 1 , … , p n are in general position.

Let S be a set of n points in the plane in general position (no three points from S are collinear). For a positive integer k, a k-hole in S is a convex polygon with k vertices from S and no points of S in its interior. For a positive integer l, a simple polygon P is l-convex if no straight line intersects the interior of P in more than l connected components. A point set S is l-convex if there exists an l-convex polygonization of S.

Let S be a set of n points in general position in the plane, r of which are red and b of which are blue. In this paper we present algorithms to find convex sets containing a balanced number of red and blue points. We provide an O ( n 4 ) time algorithm that for a given α ∈ [ 0 , 1 2 ] finds a convex set containing exactly ⌈ α r ⌉ red points and exactly ⌈ α b ⌉ blue points of S. If ⌈ α r ⌉ + ⌈ α b ⌉ is not much larger than 1 3 n , we improve the running time to O ( n log ⁡ n ) . We also provide an O ( n 2 log ⁡ n ) time algorithm to find a convex set containing exactly ⌈ r + 1 2 ⌉ red points and exactly ⌈ b + 1 2 ⌉ blue points of S, and show that balanced islands with more points do not always exist.

Let S be a set of n points in the plane in general position such that the integers 1 , 2 , … , n are assigned to the points bijectively. Set h be an integer with 1 ≤ h n ( n + 1 ) ∕ 2 . In this paper we consider the problem of finding two vertex-disjoint simple geometric paths consisting of all points of S such that the sum of labels of the points in one path is equal to h and the paths have as few crossings as possible. We prove that there exists such a pair of paths with at most two crossings between them.

A vertex subset R of a graph G is called a general position set if any triple V 0 ⊆ R is non-geodesic, this is, the three elements of V 0 do not lie on the same geodesic in G . The general position number (gp-number for short) g p ( G ) of G is the number of vertices in a largest general position set in G . In this paper we first determine some formulae for the gp-numbers of Cartesian products involving a complete graph and of the Cartesian product of a complete multipartite graph with a path, respectively. Moreover, it is proved that g p ( G □ H ) ≤ n ( G ) + n ( H ) − 2 for any Cartesian product G □ H with equality holding if and only if G and H are both generalized complete graphs, that is, a special class of graphs with diameters at most 2. Finally several open problems are proposed on the gp-numbers of Cartesian products.

The local crossing number of a drawing of a graph is the largest number of crossings on any edge of the drawing. In a rectilinear drawing of a graph, the vertices are points in the plane in general position and the edges are straight-line segments. The rectilinear local crossing number of the complete graph K n , denoted by lcr ‾ ( K n ) , is the minimum local crossing number over all rectilinear drawings of K n . We determine lcr ‾ ( K n ) . More precisely, for every n ∉ { 8 , 14 } , lcr ‾ ( K n ) = ⌈ 1 2 ( n − 3 − ⌈ n − 3 3 ⌉ ) ⌈ n − 3 3 ⌉ ⌉ , lcr ‾ ( K 8 ) = 4 , and lcr ‾ ( K 14 ) = 15 .

Suppose that $nk$ points in general position in the plane are colored red and blue, with at least $n$ points of each color. We show that then there exist $n$ pairwise disjoint convex sets, each of them containing $k$ of the points, and each of them containing points of both colors. We also show that if $P$ is a set of $n(d+1)$ points in general position in $\mathbb{R}^d$ colored by $d$ colors with at least $n$ points of each color, then there exist $n$ pairwise disjoint $d$-dimensional simplices with vertices in $P$, each of them containing a point of every color. These results can be viewed as a step towards a common generalization of several previously known geometric partitioning results regarding colored point sets., 13 pages, 5 figures; new simple proof of Lemma 4

Let X = m P 1 + ⋯ + m P n + k be a fat point subscheme of P n , where S u p p ( X ) consists of n + k distinct points which generate P n . We study the regularity index τ ( X ) of X, which is the least degree in which the Hilbert function of X equals its Hilbert polynomial. We prove that the generalized Segre's bound for τ ( X ) holds if n ≥ 4 and there are k + 3 points of S u p p ( X ) on a linear subspace Λ ≃ P 3 . We assume S u p p ( X ) is not in general position and call d the least integer for which there exists a linear subspace Λ of dimension d containing at least d + 2 points of S u p p ( X ) . We prove that the generalized Segre's bound holds for simple points when either 3 ≤ k ≤ n + 1 and d > k − 3 or k = 4 with no restriction on d. For m ≥ 2 we prove the generalized Segre's bound when S u p p ( X ) consists of n + 4 points and either there are at least 3 points on a line or at least 5 points on a plane or at least 6 points on a linear subspace Λ ≃ P 3 . Finally we prove that, in general, 2 m − 1 ≤ τ ( X ) ≤ 2 m when 3 ≤ k ≤ n − 1 and d > k − 1 , and we extend this result to the non-equimultiple case. We also provide cases in which the previous bound gives the generalized Segre's bound.

Let P be a set of n points in general position in the plane which is partitioned into color classes. The set P is said to be color-balanced if the number of points of each color is at most ⌊ n / 2 ⌋ . Given a color-balanced point set P, a balanced cut is a line which partitions P into two color-balanced point sets, each of size at most 2 n / 3 + 1 . A colored matching of P is a perfect matching in which every edge connects two points of distinct colors by a straight line segment. A plane colored matching is a colored matching which is non-crossing. In this paper, we present an algorithm which computes a balanced cut for P in linear time. Consequently, we present an algorithm which computes a plane colored matching of P optimally in Θ ( n log ⁡ n ) time.

Let G be a graph on n nodes. In this note, we prove that if G is ( r + 1 ) -vertex connected, 1 ź r ź n - 2 , then there exists a configuration p in general position in R r such that the bar framework ( G , p ) is universally rigid. The proof is constructive, and is based on a theorem by Lovasz et al concerning orthogonal representations and connectivity of graphs Lovasz etźal. (0000, 2000).

The general position number gp(G) of a connected graph G is the cardinality of a largest set S of vertices such that no three pairwise distinct vertices from S lie on a common geodesic. The n-dimensional grid graph P ∞ n is the Cartesian product of n copies of the two-way infinite path P∞. It is proved that if n ∈ N , then gp ( P ∞ n ) = 2 2 n − 1 . The result was earlier known only for n ∈ {1, 2} and partially for n = 3 .

We compute the number of triangulations of a convex k-gon each of whose sides is subdivided by r − 1 points. We find explicit formulas and generating functions, and we determine the asymptotic behaviour of these numbers as k and/or r tend to infinity. We connect these results with the question of finding the planar set of n points in general position that has the minimum possible number of triangulations.

In this paper, we consider the embedding of a complete $d$-uniform geometric hypergraph with $n$ vertices in general position in $\mathbb{R}^d$, where each hyperedge is represented as a $(d-1)$-simplex, and a pair of hyperedges is defined to cross if they are vertex-disjoint and contains a common point in the relative interior of the simplices corresponding to them. As a corollary of the Van Kampen-Flores Theorem, it can be seen that such a hypergraph contains $\Omega(\frac{2^d}{\sqrt{d}})$ $n\choose 2d$ crossing pairs of hyperedges. Using Gale Transform and Ham Sandwich Theorem, we improve this lower bound to $\Omega(\frac{2^d \log d}{\sqrt{d}})$ $n\choose 2d$.

Consider the standard symplectic ( R 2 n , ω 0 ) , a point p ∈ R 2 n and an immersed closed orientable hypersurface Σ ⊂ R 2 n ∖ { p } , all in general position. We study the following passage/tangency question: how many lines in R 2 n pass through p and tangent to Σ parallel to the 1-dimensional characteristic distribution ker ⁡ ( ω 0 | T Σ ) ⊂ T Σ of ω 0 . We count each such line with a certain sign, and present an explicit formula for their algebraic number. This number is invariant under regular homotopies in the class of a general position of the pair ( p , Σ ) , but jumps (in a well-controlled way) when during a homotopy we pass a certain singular discriminant. It provides a low bound to the actual number of these isotropic lines.

For a scheme of fat points Z defined by the saturated ideal IZ, the regularity index computes the Castelnuovo-Mumford regularity of the Cohen-Macaulay ring R/IZ. For points in "general position" we improve the bound for the regularity index computed by Segre for P2 and generalised by Catalisano, Trung and Valla for Pn. Moreover, we prove that the generalised Segre's bound conjectured by Fatabbi and Lorenzini holds for n + 3 arbitrary points in Pn. We propose a modification of Segre's conjecture for arbitrary points and we discuss some evidences.

Given a finite group G of orientation-preserving isometries of euclidean 3-space E 3 and a closed surface S, an immersion f : S → E 3 is in G-general position if f ( S ) is invariant under G, points of S have disk neighborhoods whose images are in general position, and no singular points of f ( S ) lie on an axis of rotation of G. For such an immersion, there is an induced action of G on S whose Riemann–Hurwitz equation satisfies certain natural restrictions. We classify which restricted Riemann–Hurwitz equations are realized by a G-general position immersion of S. This generalizes work by various authors on euclidean symmetry of closed surfaces embedded in E 3 . The analysis involves a detailed study of immersions of the quotient surface S / G in the orbifold E 3 / G .

In this note we study linear systems on the blow-up of ( P 1 ) n at r points in very general position. We prove that the fibers of the projections ( P 1 ) n → ( P 1 ) s , 1 ≤ s ≤ n − 1 can give contribution to the speciality of the linear system. This allows us to give a new definition of expected dimension of a linear system in ( P 1 ) n which we call fiber dimension. Finally, we state a conjecture about linear systems on ( P 1 ) 3 .

It is known that the problem of computing (Steiner) spanners on a set of n points has an ? ( n log ? n ) lower bound. However, the proof is based on an example of points on the real line. Therefore, if we assume that the points belong to the plane or higher dimensions, and moreover, they are in general position, then the lower bound example does not work.In this paper, we show that the complexity of computing geometric spanners, possibly containing Steiner points, for a set of n points in d-dimensional Euclidean space ( R d ) that are in general position is ? ( n log ? n ) , in the algebraic computation tree model. To this end, we reduce the spanner construction to a variant of the closest pair problem which has an ? ( n log ? n ) lower bound.

Erdős-Beck's theorem states that n points in the plane with at most n − x points collinear define at least cxn lines for some positive constant c. It implies n points in the plane define Θ ( n 2 ) lines unless most of the points (i.e. n − o ( n ) points) are collinear. In this paper, we will present two ways to extend this result to higher dimensions. Given a set S of n points in R d , we want to estimate a lower bound of the number of hyperplanes they define (a hyperplane is defined or spanned by S if it contains d + 1 points of S in general position). Our first result says the number of spanned hyperplanes is at least c x n d − 1 if there exists some hyperplane that contains n − x points of S and is saturated (as defined in Definition 1.3 ). Our second result says n points in R d define Θ ( n d ) hyperplanes unless most of the points belong to the union of a collection of flats whose dimension sum to less than d. Our result has an application to point-hyperplane incidences and a potential application to the point covering problem.

Let $P$ be a finite set of points in the plane in general position, that is, no three points of $P$ are on a common line. We say that a set $H$ of five points from $P$ is a $5$-hole in $P$ if $H$ is the vertex set of a convex $5$-gon containing no other points of $P$. For a positive integer $n$, let $h_5(n)$ be the minimum number of 5-holes among all sets of $n$ points in the plane in general position. Despite many efforts in the last 30 years, the best known asymptotic lower and upper bounds for $h_5(n)$ have been of order $\Omega(n)$ and $O(n^2)$, respectively. We show that $h_5(n) = \Omega(n\log^{4/5}{n})$, obtaining the first superlinear lower bound on $h_5(n)$. The following structural result, which might be of independent interest, is a crucial step in the proof of this lower bound. If a finite set $P$ of points in the plane in general position is partitioned by a line $\ell$ into two subsets, each of size at least 5 and not in convex position, then $\ell$ intersects the convex hull of some 5-hole in $P$. The proof of this result is computer-assisted., Comment: 30 pages, 14 figures, minor changes and Theorem 3 and its proof were added

We develop the formal analogue of the Morse theory for a pair of commuting gradient-like vector fields. The resulting algebraic formalism turns out to be very similar to the algebra of the infrared of Gaiotto, Moore and Witten (see Gaiotto et al. (0000), and Kapranov et al. (0000)): from a manifold M with the pair of gradient-like commuting vector fields, subject to some general position conditions we construct an L ∞ -algebra and Maurer–Cartan element in it. We also provide Morse-theoretic examples for the algebra of the infrared data.

Mosheiov [4] and Fiszman and Mosheiov [2] studied flowshop scheduling problems with position dependent job processing times and proposed algorithms which employ solving an assignment problem as a subroutine. This subroutine needs a correction. We describe such a correction. The running times of the corrected algorithms match the best known running times for the studied problems.

A classical conjecture of Erdős and Szekeres states that, for every integer k ≥ 2 , every set of 2 k − 2 + 1 points in the plane in general position contains k points in convex position. In 2006, Peters and Szekeres introduced the following stronger conjecture: every red-blue coloring of the edges of the ordered complete 3-uniform hypergraph on 2 k − 2 + 1 vertices contains an ordered subhypergraph with k vertices and k − 2 edges, which is a union of a red monotone path and a blue monotone path that are vertex disjoint except for their two common end-vertices. Applying a state of art SAT solver, we refute the conjecture of Peters and Szekeres. We also apply techniques of Erdős, Tuza, and Valtr to refine the Erdős–Szekeres conjecture in order to tackle it with SAT solvers.

Let P be a set of n points in general position in the plane. In 1996, Urabe considered a partition of P into subsets S 1 ? ? ? S l such that each S i forms a hole (or an empty convex polygon) of P and these holes are mutually disjoint. Let f ( P ) be the minimum number of holes over all such partitions of P and F ( n ) = max { f ( P ) } over all sets P of n points. Then the current best bounds are given by ? n + 1 4 ? ? F ( n ) ? ? 5 n 18 ? . In this paper, we prove that F ( n ) ? ? n 4 ? + 1 .

Let n>=@?>=2 and q>=2. We consider the minimum N such that whenever we have N points in the plane in general position and the @?-subsets of these points are colored with q colors, there is a subset S of n points all of whose @?-subsets have the same color and furthermore S is in convex position. This combines two classical areas of intense study over the last 75 years: the Ramsey problem for hypergraphs and the Erdos-Szekeres theorem on convex configurations in the plane. For the special case @?=2, we establish a single exponential bound on the minimum N, such that every complete N-vertex geometric graph whose edges are colored with q colors, yields a monochromatic convex geometric graph on n vertices. For fixed @?>=2 and q>=4, our results determine the correct exponential tower growth rate for N as a function of n, similar to the usual hypergraph Ramsey problem, even though we require our monochromatic set to be in convex position. Our results also apply to the case of @?=3 and q=2 by using a geometric variation of the stepping up lemma of Erdos and Hajnal. This is in contrast to the fact that the upper and lower bounds for the usual 3-uniform hypergraph Ramsey problem for two colors differ by one exponential in the tower.

Set systems of finite VC dimension are frequently used in applications relating to machine learning theory and statistics. Two simple types of VC classes which have been widely studied are the maximum classes (those which are extremal with respect to Sauer's lemma) and so-called Dudley classes, which arise as sets of positivity for linearly parameterized functions. These two types of VC class were related by Floyd, who gave sufficient conditions for when a Dudley class is maximum. It is widely known that Floyd's condition applies to positive Euclidean half-spaces and certain other classes, such as sets of positivity for univariate polynomials. In this paper we show that Floyd's lemma applies to a wider class of linearly parameterized functions than has been formally recognized to date. In particular we show that, modulo some minor technicalities, the sets of positivity for any linear combination of real analytic functions is maximum on points in general position. This includes sets of positivity for multivariate polynomials as a special case., 7pgs

We consider orthogonal drawings in the general position model, i.e., no two points share a coordinate. The drawings are also required to be bend minimal, i.e., each edge of a drawing in k dimensions has exactly one segment parallel to each coordinate direction that are glued together at k-1 bends. We provide a precise description of the class of graphs that admit an orthogonal drawing in the general position model in the plane. The main tools for the proof are Eulerian orientations of graphs and discrete harmonic functions. The tools developed for the planar case can also be applied in higher dimensions. We discuss two-bend drawings in three dimensions and show that K"2"k"+"2 admits a k-bend drawing in k+1 dimensions. If we allow that a vertex is placed at infinity, we can draw K"2"k"+"3 with k bends in k+1 dimensions.

We present a general analysis of the bifurcation sequences of periodic orbits in general position of a family of reversible 1:1 resonant Hamiltonian normal forms invariant under Z 2 × Z 2 symmetry. The rich structure of these classical systems is investigated both with a singularity theory approach and geometric methods. The geometric approach readily allows to find an energy–momentum map describing the phase space structure of each member of the family and a catastrophe map that captures its global features. Quadrature formulas for the actions, periods and rotation number are also provided.

Given d + 1 hyperplanes h(1),..., h(d+1) in general position in R-d, let Delta(h(1),..., h(d+1)) denote the unique bounded simplex enclosed by them. There exists a constant c(d) > 0 such that for any finite families H-1,..., Hd+1 of hyperplanes in R-d, there are subfamilies H-i* subset of H-i with vertical bar H-i*vertical bar >= c(d)vertical bar H-i vertical bar and a point p is an element of R-d with the property that p is an element of Delta(h(1),..., h(d+1)) for all h(i) is an element of H-i*. (C) 2013 Elsevier Inc. All rights reserved.

Recently, Alfakih and Ye (2013) [4] proved that if an r -dimensional bar framework ( G , p ) on n ⩾ r + 2 nodes in general position in R r admits a positive semidefinite stress matrix with rank n − r − 1 , then ( G , p ) is universally rigid. In this paper, we generalize this result in two directions. First, we extend this result to tensegrity frameworks. Second, we replace the general position assumption by the weaker assumption that in configuration p , each point and its neighbors in G affinely span R r .

Hallʼs marriage theorem can be regarded as a condition for the existence of a rainbow set of distinct points. Motivated by this interpretation, we introduce the notion of geometric Hall-type problems. We prove that a linear Hall-type condition guarantees the existence of a rainbow set of pairwise disjoint unit balls in R n . We also prove that a quadratic Hall-type condition guarantees the existence of a rainbow set of points in general position on the plane. To prove these results, we present and extend a topological technique by Aharoni and Haxell that uses Spernerʼs lemma in tight triangulations of the k-dimensional simplex.

In this paper a method for establishing the structural equivalence of sets of planar geometric features composed by points and lines is presented. It is based on oriented matroid theory, a setting in which the combinatorial structural properties of these geometric features, such as incidence, order, partitioning, separation, and convexity, can be represented and analyzed in a coordinate-free manner. Projective transformations in computer vision keep in general the convexity property which implies an invariant oriented matroid representation of the planar geometric features under this class of transformations. As long as points and lines are in general position, the oriented matroid representation is also insensitive to small changes in the geometric image features. However the oriented matroid representation depends on the labeling of its elements. Checking the structural equivalence of the above mentioned geometric features represented by means of oriented matroids implies establishing whether two oriented matroid representations are equivalent up to relabeling of their elements. This is the oriented matroid isomorphism problem which is solved in this paper by means of a canonical labeling of the elements.

A partition of a point set in the plane is called crossing-free, if the convex hulls of the individual parts do not intersect. We prove that convex position of a planar set of n points in general position minimizes the number of crossing-free partitions into 1, 2, 3, and n − 3 , n − 2 , n − 1 , n partition classes. Moreover, we show that for all n ⩾ 5 convex position of the underlying point set does not maximize the total number of crossing-free partitions. It is known that in convex position the number of crossing-free partitions into k classes equals the number of partitions into n − k + 1 parts. This does not hold in general, and we mention a construction for point sets with significantly more partitions into few classes than into many.

This paper studies the single machine past-sequence-dependent (p-s-d) delivery times scheduling with general position-dependent and time-dependent learning effects. By the general position-dependent and time-dependent learning effects we mean that the actual processing time of a job is not only a function of the total normal processing times of the jobs already processed, but also a function of the job’s scheduled position. We consider the following objective functions: the makespan, the total completion time, the sum of the θth (θ⩾0) power of job completion times, the total lateness, the total weighted completion time, the maximum lateness, the maximum tardiness and the number of tardy jobs. We show that the problems of minimization of the makespan, the total completion time, the sum of the θth (θ⩾0) power of job completion times and the total lateness can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem, the discounted total weighted completion time minimization problem, the maximum lateness minimization problem, the maximum tardiness minimization problem and the total tardiness minimization problem can be solved in polynomial time under certain conditions.

A simple algorithm for computing an approximate parameterization of real space algebraic curves using their graphs of critical points is designed and studied in this paper. The first step is determining a suitable space graph which contains all critical points of a real algebraic space curve C implicitly defined as the complete intersection of two surfaces. The construction of this graph is based on one projection of C in a general position onto an xy-plane and on an intentional choice of vertices. The second part of the designed method is a computation of a spline curve which replaces the edges of the constructed graph by segments of a chosen free-form curve. This step is formulated as an optimization problem when the objective function approximates the integral of the squared Euclidean distance of the constructed approximate curve to the intersection curve. The presented method, based on combining symbolic and numerical steps to the approximation problem, provides approximate parameterizations of space algebraic curves from a small number of approximating arcs. It may serve as a first step to several problems originating in technical practice where approximation curve parameterizations are needed.

Let P be a set of n points in the plane in general position such that its elements are colored red or blue. We study the problem of finding two disjoint disks D"r and D"b such that D"r covers only red points, D"b covers only blue points, and the number of elements of P contained in D"r@?D"b is maximized. We prove that this problem can be solved in O(n^1^1^/^3polylogn) time. We also present a randomized algorithm that with high probability returns a (1-@e)-approximation to the optimal solution in O(n^4^/^3@e^-^6polylogn) time.

Three elements U, V, and W in the complete lattice I ( A ) of weak⁎-closed inner ideals in a JBW⁎-triple A are said to be in general position when ( U , V ) form a rigidly collinear pair, and ( U , W ) and ( V , W ) form orthogonal pairs. A complete description of the supremum U ∨ V ∨ W in I ( A ) in terms of the Peirce spaces corresponding to U, V, and W is given for the case in which all three inner ideals are Peirce and three other conditions are satisfied. By considering an example in the Albert JBW⁎-triple H 3 ( O ) it is shown that none of these is redundant and, therefore, that the result obtained is the best possible.

Let P be a set of n > 2 points in general position in the plane and let G be a geometric graph with vertex set P. If the number of empty triangles uvw in P for which the subgraph of G induced by {u,v,w} is not connected is at most n-3, then G contains a non-self intersecting spanning tree., Accepted for publication in Computational Geometry: Theory and Applications

A configuration p in r -dimensional Euclidean space is a finite collection of points ( p 1 , … , p n ) that affinely span R r . A bar framework, denoted by G ( p ) , in R r is a simple graph G on n vertices together with a configuration p in R r . A given bar framework G ( p ) is said to be universally rigid if there does not exist another configuration q in any Euclidean space, not obtained from p by a rigid motion, such that | | q i - q j | | = | | p i - p j | | for each edge ( i , j ) of G . It is known [2,7] that if configuration p is generic and bar framework G ( p ) in R r admits a positive semidefinite stress matrix S of rank ( n - r - 1 ), then G ( p ) is universally rigid. Connelly asked [9] whether the same result holds true if the genericity assumption of p is replaced by the weaker assumption of general position. We answer this question in the affirmative in this paper.

In multiple-instance learning the learner receives bags, i.e., sets of instances. A bag is labeled positive if it contains a positive example of the target. An @W(dlogr) lower bound is given for the VC-dimension of bags of size r for d-dimensional halfspaces and it is shown that the same lower bound holds for halfspaces over any large point set in general position. This lower bound improves an @W(logr) lower bound of Sabato and Tishby, and it is sharp in order of magnitude. We also show that the hypothesis finding problem is NP-complete and formulate several open problems.