License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2018.6
URN: urn:nbn:de:0030-drops-87035
Go to the corresponding LIPIcs Volume Portal

Blin, Guillaume ; Blondin Mass√©, Alexandre ; Gasparoux, Marie ; Hamel, Sylvie ; Vandomme, √Člise

Nearest constrained circular words

LIPIcs-CPM-2018-6.pdf (0.6 MB)


In this paper, we study circular words arising in the development of equipment using shields in brachytherapy. This equipment has physical constraints that have to be taken into consideration. From an algorithmic point of view, the problem can be formulated as follows: Given a circular word, find a constrained circular word of the same length such that the Manhattan distance between these two words is minimal. We show that we can solve this problem in pseudo polynomial time (polynomial time in practice) using dynamic programming.

BibTeX - Entry

  author =	{Guillaume Blin and Alexandre Blondin Mass{\'e} and Marie Gasparoux and Sylvie Hamel and {\'E}lise Vandomme},
  title =	{{Nearest constrained circular words}},
  booktitle =	{Annual Symposium on Combinatorial Pattern Matching  (CPM 2018)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-074-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{105},
  editor =	{Gonzalo Navarro and David Sankoff and Binhai Zhu},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-87035},
  doi =		{10.4230/LIPIcs.CPM.2018.6},
  annote =	{Keywords: Circular constrained alignments, Manhattan distance, Application to brachytherapy}

Keywords: Circular constrained alignments, Manhattan distance, Application to brachytherapy
Collection: Annual Symposium on Combinatorial Pattern Matching (CPM 2018)
Issue Date: 2018
Date of publication: 18.05.2018
Supplementary Material: A Haskell implementation of the algorithms discussed in this paper is available at

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI