The Paintbrush Coverage Problem

Scott C.H. Huang, Elaine Y.N. Sun, Hsiao Chun Wu, Costas Busch

Research output: Contribution to journalArticlepeer-review


Autonomous vehicles become more and more popular in our daily life. Mobile computing schemes to be installed on these vehicles have drawn a lot of recent research interest. In this paper, we address the important path-planning problem for autonomous vehicles. We introduce and formulate the novel paintbrush coverage problem. We present a theoretical study on the minimum trajectory length of a paintbrush to cover an arbitrary convex region, which is derived as a function of the area of the region and the size of the cover. Three commonly-used patrolling/scouting methods, namely boustrophedon, spiral, and sector, are manifested in details as the potential solutions to the paintbrush coverage problem. The theoretical minimum trajectory lengths any algorithm can achieve are also demonstrated as the benchmarks for different shapes of regions.

Original languageEnglish (US)
Pages (from-to)3239-3250
Number of pages12
JournalIEEE Transactions on Mobile Computing
Issue number11
StatePublished - Nov 1 2021
Externally publishedYes


  • Autonomous vehicles
  • autonomous navigation
  • autonomous patrolling
  • disk covering problem
  • paintbrush coverage problem

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'The Paintbrush Coverage Problem'. Together they form a unique fingerprint.

Cite this