Affordable Access

Access to the full text

A natural extension to the convex hull problem and a novel solution

Authors
  • Mao, Xiao
Type
Preprint
Publication Date
Dec 04, 2020
Submission Date
Dec 02, 2020
Identifiers
DOI: 10.4230/LIPIcs
Source
arXiv
License
Green
External links

Abstract

We study a natural extension to the well-known convex hull problem by introducing multiplicity: if we are given a set of convex polygons, and we are allowed to partition the set into multiple components and take the convex hull of each individual component, what is the minimum total sum of the perimeters of the convex hulls? We show why this problem is intriguing, and then introduce a novel algorithm with a run-time cubic in the total number of vertices. In the case that the input polygons are disjoint, we show an optimization that achieves a run-time that, in most cases, is cubic in the total number of polygons, within a logarithmic factor.

Report this publication

Statistics

Seen <100 times