2026-07-20T05:10:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3885 2024-03-06T10:34:35Z ddc:004 open_access

Minimum Enclosing Circle with Few Extra Variables De, Minati Nandy, Subhas C. Roy, Sasanka Minimum enclosing circle space-efficient algorithm prune-and-search Asano et al. [JoCG 2011] proposed an open problem of computing the minimum enclosing circle of a set of n points in R^2 given in a read-only array in sub-quadratic time. We show that Megiddo's prune and search algorithm for computing the minimum radius circle enclosing the given points can be tailored to work in a read-only environment in O(n^{1+epsilon}) time using O(log n) extra space, where epsilon is a positive constant less than 1. As a warm-up, we first solve the same problem in an in-place setup in linear time with O(1) extra space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Minati De and Subhas C. Nandy and Sasanka Roy 2012 Is Part Of LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2012.510 urn:nbn:de:0030-drops-38855 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.510 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode