Cutting Corners by Circles and Spheres

Abstract

A circle corner cut A ⊂ N o2 is a planar set of points with nonnegative integer coordinates which includes the origin and which can be separated from N o2 \ A by a circle. In this paper we show that there are O(n 3 · log n) different circle corner cuts consisting of n points. If a sphere corner cut is defined as a set A ⊂ N o3 of points with nonnegative integer coordinates which includes the origin and which can be separated from N o3 \ A by a sphere, then there are O(n 4 · (log n) 2 ) different sphere corner cuts consisting of n points.