NICOGRAPH International 2015, pp.

55 – 61

The Development of an Application for Art Gallery Planning

Mikael Fridenfalk Masaki Hayashi Leo Sandberg

Department of Game Design, Uppsala University

{mikael.fridenfalk, masaki.hayashi, leo.sandberg} (at) speldesign.uu.se

Abstract
A system is presented for the algorithmic placement of, for example, artworks in a gallery, based on an arbitrary
number of predefined categories by which each artwork can be numerically appraised. By the provision of
a weight value for each category set by a visitor, a personalized experience is thus created that effects the
placement of the artworks. To verify the system, a 3D simulation environment was built to enable the visitor to
experience the personalized art gallery. The algorithm for artwork placement was based on a simplified version
of a nearest insertion algorithm, providing for an approximate solution of the traveling salesman problem, with
the objective to either minimize the differences between the exhibited artworks along the path, or to invoke a
predefined amount of variation between the artworks.

1 Introduction calculation of the physical path along predetermined

positions in, e.g., art museums, where the actual se-
The Traveling Salesman Problem (TSP) [3], is one quence by which each artwork is visited is of minor
of the most popular problems within computer sci- importance, the method presented in this paper solves
ence, associated with many methods for approximate rather the reverse problem, namely given the physi-
solutions, but also with exact solutions, however in cal positions in advance, e.g., how artworks may be
the general case considered to be computationally too placed for a personalized experience.
expensive for practical applications [1]. A common Although the new method presented in this paper
case of TSP consists of the evaluation of the mini- in theory can be used for instance by a curator for the
mal route through M cities on a 2D map, where each automatic placement of artworks, it is however pri-
city is only visited once, and where the cost to travel marily intended for use in a virtual art gallery or mu-
from one city to another is defined as the regular (also seum, to enable the visitor to walk through the gallery
known as the Euclidean) distance between the cities. in a virtual 3D environment without the need of phys-
ical presence, time pressure [7], or from the perspec-
This paper presents a system for the placement of
tive of the curator, in the case of highly valuable art-
works of art in a gallery based on (1) the appraisal
works, without the risk of possible degradation of the
of each artwork within any predefined category by,
artworks.
e.g., a curator, along with (2) the setting of a weight
value for each category by the visitor, depending on
the preference on the significance of each category. 2 Proposal
TSP is often suggested as a viable method for the
calculation of personalized paths in physical muse- This paper proposes a method for the arrangement of,
ums [2, 16], given a gallery of a certain predefined for instance, artworks in a gallery, where a predeter-
configuration. We could however not find any work mined route for the visitor already exists. An exam-
where TSP was used for the placement of the art- ple of such route is presented in Figure 1. Here, each
work itself. Since TSP seems to be considered for the wall section has been labeled by a number, marking

– 55 –
 NICOGRAPH International 2015, pp. 55 – 61

the estimated sequential order by which the artworks weight assigned to each category by the visitor, i.e.,
are expected to be visited. totally N weight values, preferably each set to a value
not smaller than 0.1 or larger than 10, depending on
the significance of the category. As a higher weight
20 21 23 25 40
19 26 39
value wn increases the distance between the nodes
22 24 (along the n:th dimension of the N -dimensional TSP
15 14 model), the result is that while change comes easier
18 13 28 27 38 37
(along the path) to categories with lower weight val-
17 16
ues, change is applied more gradually to categories
4 5
3 6 12 11 30 29 36 35
assigned higher weight values. However, at imple-
mentation, wn may for the purpose of optimization
be used at a preprocessing stage, by the application of
1 2 7 10 31 34
umn ← wn · umn , for all cities, to relocate the cities
8 9 32 33
accordingly, thereby eliminating the need for the ex-
Figure 1: Configuration of gallery section.
plicit incorporation of wn in (2).
Regarding the categories themselves, a few exam-
The proposed method consists of the application of ples by which each artwork may be numerically ap-
a TSP model, based on the assignment of values to praised follows as: (1) physical (coloring, size, com-
each artwork, contingent of at least two independent position, etc.) [14], (2) thematic, (3) emotional, (4)
variables (since the use of one variable would reduce psychological, and (5) historical (from the point of
the problem into a sorting problem). The variables, art history). Such categories require however, in gen-
or in this context, categories (or more specifically, in eral, some level of expertise for accurate numerical
a mathematical context, spatial dimensions, translat- estimations. A more detailed example of how cate-
ing the problem into an N -dimensional TSP), yields gories may be selected, and artwork values assigned
an M × N matrix, here denoted as U, where M des- and scaled, is presented in Section 4.
ignates the number of artworks, synonymous with the
number of cities in TSP, or the number of nodes in 3 Implementation
graph theory, and where each element umn in U, in
the nominal case, is expected to be assigned a per- The application was developed and implemented in
centage value between 0 and 100. C++ using OpenGL [12], Simple DirectMedia Layer
Regarding the distance function in our TSP model, (SDL 2.0) [15] and Xcode [18].
given the Euclidean distance in RN :
v
uN 3.1 Virtual 3D Environment
uX
DN = t (∆xn )2 (1) Each wall section (here defined as a place holder for
n=1 a single artwork), is dimensioned 3 × 3 meters. The
the distance between two cities, i and j, is in our pro- gallery section used in the 3D simulation experiments
posed model defined as: is presented in Figure 1. The camera in the virtual en-
vironment is, in a visitor mode, positioned at the ex-
v
uN pected height of the sight of the visitor. All measure-
uX
2
dist(i, j) = t wn · (uin − ujn ) − c (2) ments in the simulation environment are designed to
n=1 be accurate compared to the real world. The exhibited
paintings are thus displayed by their accurate size, ob-
where c denotes the distance offset, which by default tained in millimeters by the application, to which all
is set to zero. If a constant amount of variation is images are rescaled. The paintings are loaded into the
preferred instead of minimization of the differences application in jpg-format, and for high performance,
between the artworks along the path, c may be set internally saved and rendered as textures, using the
to a higher value. The coefficient wn denotes the graphics memory. The 3D system enables user con-

– 56 –
 NICOGRAPH International 2015, pp. 55 – 61

void TSP::InsertionSearch(int M){

for (int c = 0; c < M; c++){
double d, p = 1e50; int a, b, m = 0;
for (int i = 0; i < c; i++){
a = mPath[i], b = mPath[(i+1)%c];
d = dist(a,c) + dist(b,c) - dist(a,b);
if (p > d){p = d; m = i;}
}
for (int i = c - 1; i > m; i--) mPath[i+1] = mPath[i];
mPath[m+1] = c;
};
};
Figure 2: The implementation of a simplified version of the Nearest Insertion Algorithm.

trol in two modes: a visitor mode for nominal walk 3.2 TSP Algorithm
around in the gallery, and an examination mode, pri-
marily intended for taking a closer look at 3D art- The algorithm that was developed for the approximate
works. solution of TSP in this work, showed to be in practice
identical to one proposed in [8]. As a note on com-
putational costs, the average complexity is O(n2 ),
which is not untypical for relatively concise algo-
3.1.1 Visitor Mode rithms for approximate solutions of TSP. A slight up-
date to this algorithm was suggested a few years later,
In the visitor mode, the user is able to walk in the called the Nearest Insertion Algorithm [13], which in
3D gallery in the same way that most 3D-based com- addition played a role in the assignment of the work-
puter games enable motion. The keys W-S-D-A cor- ing name “Insertion Search” for the implemented al-
respond to forward/backward motion, versus rotation gorithm in this work.
to right/left. Similarly, dragging the mouse while
In the Nearest Insertion Algorithm, at each stage, a
holding the left mouse button pressed, enables rota-
Hamiltonian circuit containing a subset of the nodes
tion up/down (camera tilt), versus right/left (camera
(synonymous with cities in TSP) is built up, and a
pan).
new node is inserted into the circuit between two ad-
jacent nodes. Given the distance function, dist(i, j),
between any two nodes, i and j, the algorithm may
3.1.2 Examination Mode according to the original formulation be expressed as
follows:
In the examination mode, the user is able to right-
click the mouse button on any point in the 3D sys- 1. Start with a subgraph consisting of a single node,
tem, which by this action will be assigned as the new say node i.
look-at position, defining the direction of the camera
from the point of the view of the user. This method 2. Find a node k, such that dist(i, k) is minimal.
is based on the inverse calculation of 3D projections Add this node to the subgraph, and construct a
in the scene, depending on the mouse cursor location Hamiltonian circuit (for the subgraph) consisting
on the screen, using the depth buffer in OpenGL to of two occurrences of the edge (i, k).
evaluate the requested position in 3D. Zooming is in
this context performed by dragging the mouse by the 3. Given a Hamiltonian circuit containing a subset
right mouse button. Rotation of the scene around the of the nodes, find the uncontained node k clos-
look-at position, up/down (camera tilt) and left/right est to any contained node, i.e., find a minimal
(camera pan), is additionally performed by dragging dist(m, j) such that node m is in the circuit and
the mouse by the left mouse button. j is not, and take k = j.

– 57 –
 NICOGRAPH International 2015, pp. 55 – 61

4. Given k, find an edge (i, j) in the Hamiltonian the replacement of the edge (i, j) with (i, k) and
circuit for the subgraph such that dist(i, k) + (k, j), in such way that dist(i, k) + dist(k, j) −
dist(k, j) − dist(i, j) is minimal. This can be in- dist(i, j) is minimized, where i and j denote any
terpreted as finding a place in the circuit where two adjacent nodes in the circuit.
node k can be inserted at minimum cost.
3. Stop when all nodes have been inserted into the
5. Given k and the edge (i, j), obtain a new Hamil- Hamiltonian circuit, otherwise go to step 2.
tonian circuit by replacing edge (i, j) with edges
(i, k) and (k, j). In Figure 2, dist(i, j) is defined by (2), and the percent
sign (%) designates the mod operator. Briefly put, the
6. If there are any remaining nodes not in the rationalization behind the presentation of the imple-
Hamiltonian circuit, go to step 3. Otherwise, the mented code in for instance C++, is that as a principal
algorithm is finished. rule, it simplifies the implementation and the testing
of the code by the reader, particularly in the case of
The TSP algorithm implemented in this paper was de- algorithms where small errors in the pseudocode may
veloped independently of the one in [8], and the Near- be difficult to detect.
est Insertion Algorithm [13] (and similar formulations
of the Nearest Insertion Algorithm, such as in [5]),
partly in context with the development of an assign-
ment selector for the automatic generation of exami-
nation papers in discrete mathematics [6], in principle
to maximize the difference between subsequent as-
signments, from one examination to another, belong-
ing to the same assignment category.
Although the algorithm suggested in [8], is similar
to the Nearest Insertion Algorithm, the main differ-
ence is that this algorithm accepts any node, k, out-
side the Hamiltonian circuit in step 3 (according to
above), as demonstrated in Figure 2, which while still
effective, provides for a concise implementation. In-
sertion Search is greatly similar to Insertion Sort [4],
which also inserts, not a presorted, but in principle an Figure 3: Example of a 2D TSP application with 300 cities,
arbitrary node (or in this context element) k, during using a simplified version of the Nearest Inser-
tion Algorithm.
each loop. Given the distance dist(i, j) between any
two nodes, i and j, and a vector declared in C++, that
represents the outcome of the algorithm after execu- 4 Experiments
tion (as shown in Figure 2):
The main experiments were performed in three steps.
int mPath[MAX_CITIES]; In a first step, the implemented TSP algorithm was
verified. An example of such verification in a 2D case
The TSP algorithm implemented in this work may
with 300 cities is presented in Figure 3, where the
thus briefly be expressed as follows:
starting point of the algorithm is marked by a slightly
1. Given a vector, select the third element (i.e., in- enlarged dot. In a second step, the basic functionali-
dex 2), and build a Hamiltonian circuit by the ties of the 3D graphics simulation system was verified
selection of the first three nodes (i.e., the nodes by the use of enumerated paintings.
with index 0, 1, and 2). In a third and final step, a wide range of paintings
were considered [9, 17], and among these, 40 paint-
2. Select the next vector element, and denote it as ings from the years 1400 to 1780 were selected from
k. Add node k to the Hamiltonian circuit, by the Kress Collection [10,11], as shown in Figures 4-5.

– 58 –
 NICOGRAPH International 2015, pp. 55 – 61

Figure 4: The virtual 3D environment for walk-around in the personalized gallery.

Four categories were selected: size, year, portrait and the religious factors, the estimations were performed
religious factors (many paintings in the Kress Collec- directly in a scale from 0 to 100%. The portrait factor
tion consist of Christian motifs), and each painting denotes in this context the extent by which a painting
was assigned a numerical value based on either data is focused on the depiction of a person. The assigned
retrieved from the US National Gallery of Art [11], or value was thus 100% for a painting with a sole fo-
personal estimations. cus on a person, and 0% for the depiction of a motif
In the case of production year, defined as the first without one, such as an artifact or a sole landscape.
category, the following formula for an artwork, i, was Similarly, for the religious category, a purely religious
used, to linearly map each production year, yi , to a motif was assigned the value of 100%.
value between 0 and 100%: In addition to the experiments above, as a comple-
yi − ymin mentary note to the average complexity of the algo-
ui,1 = 100 · (3) rithm implemented in this work, which as previously
ymax − ymin
noted is O(n2 ), speed trials showed that for 100 trial
where ymin and ymax denote the earliest work versus runs of the algorithm for each parameter setting, the
the latest. In the case of size, defined as the second average execution time (on a single core of a 2.66
category, the square root of the area, ai , of each paint- GHz Intel Core i7 processor) was for two categories,
ing was used: estimated to 78 µs for 40 cities and 4.10 ms for 300
√ √ cities (such as in Figure 3). For five categories, the
ai − amin
ui,2 = 100 · √ √ (4) corresponding average execution time was estimated
amax − amin
to 145 µs for 40 cities and 6.02 ms for 300 cities.
As a note, the areas of the paintings showed to range
between 0.059 - 4.7 m2 . In the case of the portrait and

– 59 –
 NICOGRAPH International 2015, pp. 55 – 61

Figure 5: Visitor mode.

5 Conclusion References
The new method suggested in this paper for the au- [1] D. L. Applegate, The Traveling Salesman Prob-
tomatic placement of, e.g., artworks in a gallery (to lem: A Computational Study, ISBN 978-0-691-
either assist the curator, or to create a personalized 12993-8, Princeton University Press, Princeton,
experience for the visitor), showed in a few exper- 2006.
iments to work correctly, by either minimization of
the change in the assigned values of each category for [2] L. Aroyo, Y. Wang, R. Brussee, P. Gorgels, L.
each artwork along the predefined path, or in the gen- Rutledge, N. Stash, Personalized Museum Ex-
eration of a sequence of artworks with a predefined perience: The Rijksmuseum Use Case, Proceed-
amount of variation along the path. ings of Museums and the Web 2007, Archives &
The algorithm for approximate solution of TSP, Museum Informatics, San Francisco CA, USA,
developed in this work (and here called “Insertion April 2007.
Search”, due to great similarities with the sorting al-
gorithm Insertion Sort), was found to be in practice [3] N. L. Biggs, E. K. Lloyd, R. J. Wilson, Graph
identical to one in [8]. Implemented in C++, this al- Theory 1736-1936, ISBN 978-0-19-853916-2,
gorithm showed to be concise. In computer science Clarendon Press, Oxford, 1986.
as well as in mathematics, brief solutions are as a rule
preferred to complex ones, which is applicable to this [4] A. Drozdek, Data Structures and Algorithms in
work, where the accuracy of such solution is not con- C++, 4th ed., ISBN 978-1-133-60842-4, Cen-
sidered to be a significant issue. gage Learning, 2012.

[5] Y. Fang, G. Liu, Y. He, Y. Qiu, Tabu Search

Algorithm Based on Insertion Method, Pro-
ceedings of the IEEE International Conference

– 60 –
 NICOGRAPH International 2015, pp. 55 – 61

on Neural Networks and Signal Processing, Accessed: 2015-04-06.

pp. 420-423, Nanjing, China, December 2003.
[12] OpenGL, Silicon Graphics International Corp.
[6] M. Fridenfalk, System for Automatic Genera- https://www.opengl.org. Accessed: 2015-04-24.
tion of Examination Papers in Discrete Math-
ematics, Proceedings of IADIS International [13] D. J. Rosenkrantz, R. E. Stearns, P. M.
Conference on e-Learning 2013, IADIS Multi Lewis, Approximate Algorithms for the Travel-
Conference on Computer Science and Informa- ing Salesperson Problem, Proceedings of IEEE
tion Systems, pp. 365-368, Prague, Czech Re- 15th Symposium on Switching and Automata
public, July 2013. Theory, pp. 33-42, New Orleans, USA, October
1974.
[7] M. Hayashi, S. Bachelder, M. Nakajima, A
New Virtual Museum Equipped with Automatic [14] L. Sandberg, Imagine: Creating Art for Enter-
Video Content Generator, Proceedings of Cy- tainment, ISBN 978-91-633-3664-5, FabPics,
berworlds 2014, pp. 377-383, Santander, Spain, 2009.
October 2014. [15] SDL. https://www.libsdl.org. Accessed: 2015-
[8] R. L. Karg, G. L. Thompson, A Heuristic Ap- 04-27.
proach to Solving Travelling Salesman Prob- [16] A. Smirnov, N. Shilov, A. Kashevnik, Context-
lems, Management Science, vol. 10, no. 2, pp. Oriented Knowledge Management for Intelli-
225-248, 1964. gent Museum Visitors Support, Proceedings of
[9] F. S. Kleiner, C. J. Mamiya, Gardner’s Art Third International Conference on Advances in
Through the Ages, 12th ed., ISBN 978-0-15- Future Internet, pp. 120-125, Nice, France, Au-
505090-7, Thomson Wadsworth, 2004. gust 2011.

[10] Kress Foundation. http://www.kressfoundation. [17] B. Wands, Art of the Digital Age, ISBN 978-0-
org. Accessed: 2015-03-30. 500-28629-6, Thames & Hudson, 2007.

[11] National Gallery of Art, USA. https://images. [18] Xcode, Apple Inc. https://developer.apple.com/
nga.gov/en/page/show_home_page.html. xcode/. Accessed: 2015-04-27.

– 61 –