A square trisection is a problem of assembling three identical squares from a larger square, using a minimal number of pieces. This paper presents an historical overview of the square trisection problem starting with its origins in the third century. We de ...
Let G be a graph with n vertices and ea parts per thousand yen4n edges, drawn in the plane in such a way that if two or more edges (arcs) share an interior point p, then they properly cross one another at p. It is shown that the number of crossing points, ...
A string graph is the intersection graph of a collection of continuous arcs in the plane. We show that any string graph with in edges can be separated into two parts of roughly equal size by the removal of O(m(3/4)root log m) vertices. This result is then ...
Given a point set P in the plane, the Delaunay graph with respect to axis-parallel rectangles is a graph defined on the vertex set P, whose two points p, q is an element of P are connected by an edge if and only if there is a rectangle parallel to the coor ...
Let P and Q be finite sets of points in the plane. In this note we consider the largest cardinality of a subset of the Minkowski sum S ⊆ P⊕Q which consist of convex independent points. We show that, if P and Q contain at most n points, then |S| = O(n^(4/3) ...
Suppose d > 2, n > d+1, and we have a set P of n points in d-dimensional Euclidean space. Then P contains a subset Q of d points such that for any p ∈ P, the convex hull of Q∪{p} does not contain the origin in its interior.We also show that for non-emp ...
