Deephullnet: a deep learning approach for solving the convex hull and concave hull problems with transformer

Abstract

ABSTRACTConvex and concave hulls originating from computational geometry are widely applied in practice. For instance, to determine the boundaries of a geographical area within a group of cities, convex hulls can represent the approximate boundaries of the areas. Concave hulls can accurately describe the shape of the area. The traditional methods for solving two-dimensional convex hull problems include the Jarvis March algorithm and the Graham scanning algorithm. The K-nearest neighbours and alpha-shape methods are designed for solving the concave hull problem. Other than traditional algorithms, we consider using deep neural networks to handle the convex and concave hull problems. General neural networks cannot deal with the problem whose output is a variable-length sequence. Our study provides a machine-learning approach for solving the convex hull and concave hull problems. We combine the Pointer network (Ptr-Net) with the Transformer model and propose the DeepHullNet. The trained DeepHullNet can provide a feasible solution in the majority of cases. The experimental results show that DeepHullNet outperforms the original Ptr-Net regarding accuracy. Compared with traditional methods, DeepHullNet can generate a good solution quickly, and the running time is shortened by nearly 100 times based on GPU.

Keywords

• Convex hull problem
• concave hull problem
• deep learning
• transformer
• GeoAI