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

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

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

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 language	English
Title of host publication	Abstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010)
Editors	J. Vahrenhold
Place of Publication	Dortmund
Publisher	Technische Universität Dortmund
Pages	73-76
Publication status	Published - 2010
Event	26th European Workshop on Computational Geometry (EuroCG 2010) - Dortmund Duration: 22 Mar 2010 → 24 Mar 2010 Conference number: 26 http://eurocg.org/

Workshop

Workshop	26th European Workshop on Computational Geometry (EuroCG 2010)
Abbreviated title	EuroCG 2010
City	Dortmund
Period	22/03/10 → 24/03/10
Internet address	http://eurocg.org/

Cite this

Berg, de, M. T., Gerrits, D. H. P., Khosravi Dehkordi, A., Rutter, I., Tsirogiannis, C. P., & Wolff, A. (2010). How Alexander the Great brought the Greeks together while inflicting minimal damage to the Barbarians. In J. Vahrenhold (Ed.), Abstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010) (pp. 73-76). Technische Universität Dortmund.

@inproceedings{1ad6af8798e3447e8ed3bf789b85a4f2,

title = "How Alexander the Great brought the Greeks together while inflicting minimal damage to the Barbarians",

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.",

author = "{Berg, de}, M.T. and D.H.P. Gerrits and {Khosravi Dehkordi}, A. and I. Rutter and C.P. Tsirogiannis and A. Wolff",

year = "2010",

language = "English",

pages = "73--76",

editor = "J. Vahrenhold",

booktitle = "Abstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010)",

publisher = "Technische Universit{\"a}t Dortmund",

note = "26th European Workshop on Computational Geometry (EuroCG 2010), EuroCG 2010 ; Conference date: 22-03-2010 Through 24-03-2010",

url = "http://eurocg.org/",

}

Berg, de, MT, Gerrits, DHP, Khosravi Dehkordi, A, Rutter, I, Tsirogiannis, CP & Wolff, A 2010, How Alexander the Great brought the Greeks together while inflicting minimal damage to the Barbarians. in J Vahrenhold (ed.), Abstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010). Technische Universität Dortmund, Dortmund, pp. 73-76, 26th European Workshop on Computational Geometry (EuroCG 2010), Dortmund, 22/03/10.

How Alexander the Great brought the Greeks together while inflicting minimal damage to the Barbarians. / Berg, de, M.T.; Gerrits, D.H.P.; Khosravi Dehkordi, A. et al.
Abstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010). ed. / J. Vahrenhold. Dortmund: Technische Universität Dortmund, 2010. p. 73-76.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

TY - GEN

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

AU - Berg, de, M.T.

AU - Gerrits, D.H.P.

AU - Khosravi Dehkordi, A.

AU - Rutter, I.

AU - Tsirogiannis, C.P.

AU - Wolff, A.

N1 - Conference code: 26

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

M3 - Conference contribution

SP - 73

EP - 76

BT - Abstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010)

A2 - Vahrenhold, J.

PB - Technische Universität Dortmund

CY - Dortmund

T2 - 26th European Workshop on Computational Geometry (EuroCG 2010)

Y2 - 22 March 2010 through 24 March 2010

ER -

Berg, de MT, Gerrits DHP, Khosravi Dehkordi A, Rutter I, Tsirogiannis CP, Wolff A. How Alexander the Great brought the Greeks together while inflicting minimal damage to the Barbarians. In Vahrenhold J, editor, Abstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010). Dortmund: Technische Universität Dortmund. 2010. p. 73-76

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

Abstract

Workshop

Fingerprint

Cite this