2026-08-17T07:42:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8703 2024-03-06T10:43:00Z ddc:004 open_access

Nearest constrained circular words Blin, Guillaume Blondin Massé, Alexandre Gasparoux, Marie Hamel, Sylvie Vandomme, Élise Circular constrained alignments Manhattan distance Application to brachytherapy 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guillaume Blin and Alexandre Blondin Massé and Marie Gasparoux and Sylvie Hamel and Élise Vandomme 2018 Is Part Of LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2018.6 urn:nbn:de:0030-drops-87035 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.6 eng https://creativecommons.org/licenses/by/3.0/legalcode