We consider two classes of higher order proximity graphs defined on a set of points in the plane, namely, the k-Delaunay graph and the k-Gabriel graph. We give bounds on the following combinatorial and geometric properties of these graphs: spanning ratio, diameter, chromatic number, and minimum number of layers necessary to partition the edges of the graphs so that no two edges of the same layer cross.

We study a new family of geometric graphs that interpolate between the Delaunay triangulation and the Gabriel graph. These graphs share many properties with β-skeletons for βin[0,1] (such as sublinear spanning ratio) with the added benefit of planarity (and consequently linear size and local routability).

We prove the following generalised empty pentagon theorem: for every integer >=2, every sufficiently large set of points in the plane contains collinear points or an empty pentagon. As an application, we settle the next open case of the Big Line or Big Clique Conjecture of Kára, Pór, and Wood [Discrete Comput. Geom. 34(3):497--506, 2005].

We study a simple geometric model of transportation facility that consists of two points between which the travel speed is high. This elementary definition can model shuttle services, tunnels, bridges, teleportation devices, escalators or moving walkways. The travel time between a pair of points is defined as a time distance, in such a way that a customer uses the transportation facility only if it is helpful. We give algorithms for finding the optimal location of such a transportation facility, where optimality is defined with respect to the maximum travel time between two points in a given set.

In this paper, we analyze the time complexity of finding regular polygons in a set of n points. We use two different approaches to find regular polygons, depending on their number of edges. Those with o(n^0.068) edges are found by sweeping a line through the set of points, while the larger polygons are found by random sampling. We can find with high probability all the polygons in O(n^(2.068+epsilon)) expected time for every positive epsilon. This compares well to the O(n^(2.136+epsilon)) deterministic algorithm of Brass. Our method can also be used to find incomplete regular polygons, where up to a constant fraction of the vertices are missing.

The region counting distances, introduced by Demaine, Iacono and Langerman, associate to any pair of points p,q the number of items of a dataset S contained in a region R(p,q) surrounding p,q. We define region counting disks and circles, and study the complexity of these objects. In particular, we prove that for some wide class of regions R(p,q), the complexity of a region counting circle of radius k is either at least as large as the complexity of the k-level in an arrangement of lines, or is linear in |S|. We give a complete characterization of regions falling into one of these two cases. Algorithms to compute ε-approximations of region counting distances and approximations of region counting circles are presented.

A new family of proximity graphs, called Region Counting Graphs (RCG) is presented. The RCG for a finite set of points in the plane uses the notion of region counting distance introduced by Demaine et al. to characterize the proximity between two points p and q: the edge pq is in the RCG if and only if there is less than or exactly k vertices in a given geometric neighborhood defined by a region. These graphs generalize many common proximity graphs, such as k-nearest neighbor graphs, Beta-skeletons or Theta-graphs. This paper concentrates on RCGs that are invariant under translations, rotations and uniform scaling. For k=0, we give conditions on regions R that define an RCG to ensure a number of properties including planarity, connectivity, triangle freeness, cycle freeness, bipartiteness, and bounded degree. These conditions take form of what we call tight regions: maximal or minimal regions that a region R must contain or be contained in to satisfy a given monotone property.

We introduce a new property for geometric graphs: the local diameter. This property is based on the use of the region counting distances introduced by Demaine, Iacono and Langerman as a generalization of the rank difference. We use it as a characterization of the local density of the vertices. We study the properties of those distances, and show that there is a strong relation between region counting distances and speed distances. We define the local diameter as the upper bound on the length of the shortest path between any pair of vertices, expressed as a function of the number of vertices in their neighborhood. We determine the local diameter of several well-studied graphs such as the Ordered Theta-graph and the Skip List Spanner. We also analyze the impact of the local diameter for different applications, such as path and point queries on geometric graphs.