How Alexander the Great brought the Greeks together while inflicting minimal damage to the Barbarians

M.T. Berg, de, D.H.P. Gerrits, A. Khosravi Dehkordi, I. Rutter, C.P. Tsirogiannis, A. Wolff

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

2 Downloads (Pure)

Abstract

Let R be a finite set of red point sites in R^d and let B be a set of n blue point sites in R^d. We want to establish "safe" connections between the red sites by deleting a minimum number of blue sites such that the region controlled by the red sites is connected. More precisely, we want to find a minimum-size subset B_del \subseteq B such that the red cells in the Voronoi diagram of R \cup B \ B_del form a connected region. For |R| = 2 we present an optimal O(n log n)-time algorithm for d = 2, and an O(n^(d-1))-time algorithm for d \geq 3; we also show that the problem is 3SUM-hard for d = 3. Furthermore, we show that the general problem, where the number of red sites is not a constant, is NP-hard.
Original languageEnglish
Title of host publicationAbstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010)
EditorsJ. Vahrenhold
Place of PublicationDortmund
PublisherTechnische Universität Dortmund
Pages73-76
Publication statusPublished - 2010
Event26th European Workshop on Computational Geometry (EuroCG 2010) - Dortmund
Duration: 22 Mar 201024 Mar 2010
Conference number: 26
http://eurocg.org/

Workshop

Workshop26th European Workshop on Computational Geometry (EuroCG 2010)
Abbreviated titleEuroCG 2010
CityDortmund
Period22/03/1024/03/10
Internet address

Fingerprint Dive into the research topics of 'How Alexander the Great brought the Greeks together while inflicting minimal damage to the Barbarians'. Together they form a unique fingerprint.

Cite this