## Abstract

We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of n vertices and h holes. We introduce a graph of oriented distances to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in O(min(n^{ω},n^{2}+nhlogh+χ^{2})) time, where ω<2.373 denotes the matrix multiplication exponent and χ∈Ω(n)∩O(n^{2}) is the number of edges of the graph of oriented distances. We also provide an alternative algorithm for computing the diameter that runs in O(n^{2}logn) time.

Original language | English |
---|---|

Article number | 101685 |

Number of pages | 11 |

Journal | Computational Geometry |

Volume | 92 |

DOIs | |

Publication status | Published - Jan 2021 |

### Funding

An extended abstract appeared at the 29th International Symposium on Algorithms and Computation (ISAAC 2018) [3]. EA was supported by the SNF Early Postdoc Mobility grant P2TIP2-168563, Switzerland, F.R.S.-FNRS, Belgium, and by the Foundation for the Advancement of Theoretical Physics and Mathematics ?BASIS? Grant Leader 19-7-1-31-2, Russia. MC, AvR and MR were supported by JST ERATO Grant Number JPMJER1201, Japan. MC was also supported in part by ERC StG 757609. MK was supported in part by KAKENHI No. 17K12635, Japan and NSF award CCF-1422311. AM was supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 024.002.003. YO was partially supported by JSPS KAKENHI Grant Number 15K00009 and JST CREST Grant Number JPMJCR1402, and Kayamori Foundation of Informational Science Advancement Grant Number K28-XXI-48. AO was supported by the Fund for Research Training in Industry and Agriculture (FRIA) Grant Numbers 5112416F and 5203818F.

Funders | Funder number |
---|---|

F.R.S.-FNRS | |

Fund for Research Training in Industry and Agriculture | |

JST CREST | |

JST ERATO | |

National Science Foundation | CCF-1422311 |

Horizon 2020 Framework Programme | 757609 |

Kayamori Foundation of Informational Science Advancement | K28-XXI-48 |

European Research Council | 17K12635 |

Japan Society for the Promotion of Science | 15K00009 |

Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung | P2TIP2-168563 |

Fonds De La Recherche Scientifique - FNRS | |

Fonds pour la Formation à la Recherche dans l’Industrie et dans l’Agriculture | 5203818F, 5112416F |

Nederlandse Organisatie voor Wetenschappelijk Onderzoek | 024.002.003 |

Core Research for Evolutional Science and Technology | JPMJCR1402 |

Exploratory Research for Advanced Technology | JPMJER1201 |

Foundation for the Advancement of Theoretical Physics and Mathematics | 19-7-1-31-2 |

## Keywords

- Diameter
- Polygonal domain
- Radius
- Rectilinear link distance