The farthest color Voronoi diagram in the plane

The farthest color Voronoi diagram in the plane | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article The farthest color Voronoi diagram in the plane Ioannis Mantas, Evanthia Papadopoulou, Rodrigo I. Silveira, Zeyu Wang This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-4644060/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 06 Jun, 2025 Read the published version in Algorithmica → Version 1 posted 9 You are reading this latest preprint version Abstract The farthest-color Voronoi diagram (FCVD) is defined on a set of $n$ points in the plane, each of which is labeled with one of $m$ colors.The colored points can be seen as a family $\cC$ of$m$ clusters (sets) of points in the plane, whose farthest-site Voronoi diagram is the FCVD. The diagram finds applications in problems related to facility location, shape matching, imprecision in geometric data, sensor deployment, and others. In this paper we present structural properties of the FCVD, refine its combinatorial complexity bounds, and present efficient algorithms for its construction. We show that the complexity of the diagram is $O(n\alpha(n)+\str(\cC))$, where $\str(\cC)$ is a parameter reflecting the number of straddles between pairs of clusters, which is $O(m(n-m))$. The bound reduces to $O(n+ \str(\cC))$ if the clusters are pairwise non-crossing. We also present a lower bound, establishing that the complexity of the FCVD can be $\Omega(n+m^2)$, even if the clusters have pairwise disjoint convex hulls. Our algorithm runs in $O((n+\str(\cC))\log^3 n)$-time, and in certain special cases in $O(n\log n)$ time. farthest-site Voronoi diagram color Voronoi diagram point clusters color spanning disk straddles divide and conquer Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 06 Jun, 2025 Read the published version in Algorithmica → Version 1 posted Editorial decision: Revision requested 14 Feb, 2025 Reviews received at journal 04 Feb, 2025 Reviews received at journal 23 Nov, 2024 Reviewers agreed at journal 21 Oct, 2024 Reviewers agreed at journal 21 Aug, 2024 Reviewers invited by journal 19 Aug, 2024 Editor assigned by journal 12 Jul, 2024 Submission checks completed at journal 29 Jun, 2024 First submitted to journal 26 Jun, 2024 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-4644060","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":329376690,"identity":"693803b5-4a9e-42e7-ade5-d2e1e834628a","order_by":0,"name":"Ioannis Mantas","email":"","orcid":"","institution":"University of Lugano","correspondingAuthor":false,"prefix":"","firstName":"Ioannis","middleName":"","lastName":"Mantas","suffix":""},{"id":329376692,"identity":"82582eee-ac9e-4d49-a0cf-083747a2bcae","order_by":1,"name":"Evanthia Papadopoulou","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABIElEQVRIiWNgGAWjYLACxgYJKIsNRDA3MDBUgNlsOLUcRNXCCNRyhqAWGAumhbENwUUH/BLJzx5/3GEhzyDd/OzBjzKbPH6JxMbHvPMO2/MxMD97gEWL5Iw0c4ODZyQMG2SOmRv2nEsrlpyR2GzMu+1wYhsDm7kBFi0GZw6YSRxskwCGQIKZBG/b4cQNNxLbpIFaEtgYeNgksGixP3P8G0iLfYNE+jfJv3Atcw7b49JiwN4DtiWxQSLHTBphS8NhYAhg1yJxvKdM4mybRHKbzJlyYxmQX3oeNhvOOZae2MbMZoZNC38z+zaJyrY6237p9m0P34BCjD354IM3Ndb28u3Nz7BpgQOgG8CxkIAQYsanHuxEDC2jYBSMglEwCiAAAM1uX+2JmcXEAAAAAElFTkSuQmCC","orcid":"","institution":"University of Lugano","correspondingAuthor":true,"prefix":"","firstName":"Evanthia","middleName":"","lastName":"Papadopoulou","suffix":""},{"id":329376693,"identity":"03ed5672-2c00-4869-a4a0-3edd104fc93b","order_by":2,"name":"Rodrigo I. Silveira","email":"","orcid":"","institution":"Universitat Politècnica de Catalunya","correspondingAuthor":false,"prefix":"","firstName":"Rodrigo","middleName":"I.","lastName":"Silveira","suffix":""},{"id":329376694,"identity":"c4018daf-2e5a-4f00-96ad-1756c6ecdd6a","order_by":3,"name":"Zeyu Wang","email":"","orcid":"","institution":"University of Lugano","correspondingAuthor":false,"prefix":"","firstName":"Zeyu","middleName":"","lastName":"Wang","suffix":""}],"badges":[],"createdAt":"2024-06-26 16:29:28","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-4644060/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-4644060/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s00453-025-01311-1","type":"published","date":"2025-06-06T15:57:54+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":84242632,"identity":"ef3f6104-625a-4a6c-b619-325124e57239","added_by":"auto","created_at":"2025-06-09 16:10:31","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":518438,"visible":true,"origin":"","legend":"","description":"","filename":"submission.pdf","url":"https://assets-eu.researchsquare.com/files/rs-4644060/v1_covered_9c80186d-6301-480d-8f30-bc4b301c9872.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"The farthest color Voronoi diagram in the plane","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"algorithmica","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"algo","sideBox":"Learn more about [Algorithmica](http://link.springer.com/journal/453)","snPcode":"453","submissionUrl":"https://submission.nature.com/new-submission/453/3","title":"Algorithmica","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"farthest-site Voronoi diagram, color Voronoi diagram, point clusters, color spanning disk, straddles, divide and conquer","lastPublishedDoi":"10.21203/rs.3.rs-4644060/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-4644060/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"The farthest-color Voronoi diagram (FCVD) is defined on a set of $n$ points in the plane, each of which is labeled with one of $m$ colors.The colored points can be seen as a family $\\cC$ of$m$ clusters (sets) of points in the plane, whose farthest-site Voronoi diagram is the FCVD. The diagram finds applications in problems related to facility location, shape matching, imprecision in geometric data, sensor deployment, and others. In this paper we present structural properties of the FCVD, refine its combinatorial complexity bounds, and present efficient algorithms for its construction. We show that the complexity of the diagram is $O(n\\alpha(n)+\\str(\\cC))$, where $\\str(\\cC)$ is a parameter reflecting the number of straddles between pairs of clusters, which is $O(m(n-m))$. The bound reduces to $O(n+ \\str(\\cC))$ if the clusters are pairwise non-crossing. We also present a lower bound, establishing that the complexity of the FCVD can be $\\Omega(n+m^2)$, even if the clusters have pairwise disjoint convex hulls. Our algorithm runs in $O((n+\\str(\\cC))\\log^3 n)$-time, and in certain special cases in $O(n\\log n)$ time.","manuscriptTitle":"The farthest color Voronoi diagram in the plane","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-07-22 14:54:34","doi":"10.21203/rs.3.rs-4644060/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2025-02-14T16:23:57+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2025-02-04T12:55:56+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-11-23T12:47:15+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"260071883926857121114303927056934645282","date":"2024-10-21T11:44:15+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"224616787526480812383514468293744718349","date":"2024-08-21T09:51:30+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2024-08-19T07:39:12+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2024-07-12T04:08:42+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-06-29T08:25:43+00:00","index":"","fulltext":""},{"type":"submitted","content":"Algorithmica","date":"2024-06-26T16:28:16+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"algorithmica","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"algo","sideBox":"Learn more about [Algorithmica](http://link.springer.com/journal/453)","snPcode":"453","submissionUrl":"https://submission.nature.com/new-submission/453/3","title":"Algorithmica","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"e144068d-be88-4c1f-bf1f-e86648c34cf3","owner":[],"postedDate":"July 22nd, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2025-06-09T16:04:44+00:00","versionOfRecord":{"articleIdentity":"rs-4644060","link":"https://doi.org/10.1007/s00453-025-01311-1","journal":{"identity":"algorithmica","isVorOnly":false,"title":"Algorithmica"},"publishedOn":"2025-06-06 15:57:54","publishedOnDateReadable":"June 6th, 2025"},"versionCreatedAt":"2024-07-22 14:54:34","video":"","vorDoi":"10.1007/s00453-025-01311-1","vorDoiUrl":"https://doi.org/10.1007/s00453-025-01311-1","workflowStages":[]},"version":"v1","identity":"rs-4644060","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-4644060","identity":"rs-4644060","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}