Vassilis Kollias
email: vkollias@uth.gr

Nectarios Mamalougos

Xenia Vamvakoussi

Minna Lakkala

Vassilios Kollias

Nektarios Mamalougos

Stella Vosniadou

Teachers' attitudes to

Keywords: cooperative/collaborative learning, national school culture, evaluation methodologies, distributed learning environments

come   L'archive ouverte pluridisciplinaire

Introduction

The European Innovative Technologies for Collaborative Learning Project (ITCOLE) concentrated on creating software tools that support Web-based Collaborative Learning Environments (CLE) (see Rubens et al., this volume) and on delineating efficient pedagogical practices for CLEs, on testing and refining them and eventually disseminating them throughout European education landscape. The pedagogical partners of the project consisted of four research groups from four European countries: Finland, Greece, Italy and the Netherlands (Ligorio & Veermans, this volume).

A worldwide study of teachers' and students' practices in classrooms, where innovative pedagogical practices supported by technology have been introduced, showed that two patterns of classroom practice, "Student Collaborative Research" and "Information Management" are more likely to be associated with new pedagogical skills for teachers, and acquisition of ICT, problem solving and collaboration skills for students [START_REF] Kozma | Technology and Classroom Practices: An International Study[END_REF]. Both patterns have strong resemblances with the expected practices in the CLEs that were implemented during the ITCOLE project. Moreover, CLEs have influenced the development of the Computer Supported Collaborative Learning paradigm [START_REF] Koschmann | Paradigm shifts and Instructional Technology[END_REF][START_REF] Dimitrakopoulou | Advanced Collaborative Distance Learning Systems for Young Students: Design Issues and Current Trends on New Cognitive and Metacognitive Tools, Themes in Education[END_REF]. In recent literature, CLEs have been associated with the notion of powerful learning environments characterized by special emphasis on the development of intentional learners and the collaborative construction of knowledge within learning communities.

Other crucial parts of the developed powerful learning environments are support for metacognition, model building, and emphasis both on the process and on the product [START_REF] Vosniadou | How Children Learn[END_REF]Vosniadou & Kollias, 2003).

However, the successful implementation of CLEs depends on sensitive decisions that teachers have to make in their everyday practice. It has been pointed out that such decisions depend on teachers' conceptions of the particular learning environment [START_REF] Schulman | Paradigms and research programs in the study of teaching: A contemporary perspective[END_REF]. Therefore, the analysis of teachers' conceptions of CLEs can provide insights on the prerequisites for their successful implementation.

According to [START_REF] Dexter | Teachers' Views of Computers as Catalysts for Changes in their Teaching Practice[END_REF], "The teachers who had adopted more progressive teaching practices over time felt that computers helped them change, but they did not acknowledge computers as catalyst for change; instead they cited reflection upon experience, classes taken, and the context or culture of the school." (p.221). Therefore, if teachers' conceptions of CLEs would reveal that CLEs facilitated teachers' reflections upon their experience, awareness of the importance of the school culture towards educational innovation, and awareness for the need of professional improvement, then we would have reasons to expect that CLEs are particularly promising in facilitating teachers to adopt more progressive teaching practices.

In this study we interviewed teachers from the four countries, who implemented web-based CLEs in their own classrooms while participating in the ITCOLE project.

The interviews took place after the completion of the project and the questions referred to different aspects of the CLE implementation, as well as to the teachers' own reflections on the implementations of CLEs.

CLEs constitute activity systems which introduce transformations in collective practices. In order to specify the main dimensions that define teachers' conceptions of CLEs, we adopted the theoretical approach developed by Engeström and co-workers [START_REF] Engeström | Learning by expanding: An activity-theoretical approach to developmental research[END_REF][START_REF] Engeström | Can a School Community Learn to Master its own future? An Activity-Theoretical Study of Expansive Learning among Middle School Teachers[END_REF]. Their model of an activity system is based on cultural-historical activity theory and introduces six important dimensions, along with the dynamics among them: Subject, Object (the goal of the activity system), Norms, Division of Labour, Community and Instruments.

When examining a traditional classroom in its day to day operation, we could assign the teacher to the dimension 'Subject', the learning goals for the students to the dimension 'Object', the implicit and explicit rules that structure social interaction to the dimension 'Norms', the prescribed roles of the teacher and the student to the dimension 'Division of Labour', the group of students and teacher to the dimension 'Community' and different educational means to the dimension 'Instruments'. In the case of CLEs, however, the implementation of the innovation introduces tensions that change the content of the dimensions, at least with respect to teachers' conceptions of CLEs.

First, we expected considerable transfer of learning responsibilities from the teacher, to the students. Having both intra-group collaboration in front of the PCs and inter-group collaboration via the collaborative software, facilitates change in the division of labour inside the classroom that brings forth the 'Teacher' and the 'Student' as subjects struggling towards a new equilibrium. It was expected that the strain created between the dimensions 'Subject' and 'Division of Labour' would make the new dimensions 'Student' and 'Teacher' salient in the teachers' conceptions of CLEs. It was also expected that the teachers would perceive CLEs as learning environments that are strongly student-centred and that give affordances to students to take more learning responsibilities.

Second, we expected that the characteristics of the software would be a prominent feature in the teachers' conceptions of CLEs. Hence, we expected that the dimension 'Instruments' would appear in the teachers' conceptions of CLEs mainly as the dimension 'Software'.

Third, we hypothesized that the contradictions between CLE designs, school organization affordances, and national curricula directions would make salient in the 'Community' dimension a vertical dimension referring to CLE's position inside the institutional setting of education. The school organization and the national curriculum are structures through which the community that realizes the CLE, comprised by the teacher and the students, interacts with the larger community and its educational agenda.

Moreover, the change in the distribution of labour creates opportunities for changing attitudes between the community of teachers and the community of students. This is a horizontal dimension within the 'Community' dimension. It was expected that in case CLE implementation changed the trust that the teachers felt about students, this dimension would be represented in the teachers' conceptions of CLEs.

Fourth, we expected that the prominence of collaboration as a feature of CLEs would colour the dimensions 'Norms' and 'Object' in the teachers' conceptions.

'Norms' were going to be affected by the opportunities and challenges of establishing fruitful collaboration among students in the classroom. The 'Object' of the activity in the CLEs would be affected by expectations of accountability for the implemented innovation. The accountability would include not only reference to learning gains (in a declarative sense) but also references to the quality of collaboration and to the acquisition of different skills among which ICT skills were expected to be prominent.

The innovation might also create an awareness of the need for new kinds of assessment in order to capture the added value of the modern learning environments.

Finally, as CLEs operate they could be interpreted by the teachers as working systems, where student performances that show understanding get integrated with teachers' ongoing assessment and feedback to the students [START_REF] Perkins | Smart Schools[END_REF]. The presence of these features in the CLEs is highly valued as indicative of a qualitative change in the classroom. However, teachers know, as part of accumulated experience in their profession, of the constraints of time and experience whenever changes are tried out in the school and this knowledge is expected to be expressed in their overall conceptions of the CLEs.

Research in cognitive science [START_REF] Bransford | How People Learn: Brain, Mind, Experience and School[END_REF] points that teachers will interpret CLEs based on their prior understanding of learning environments. In the methodology section we present short accounts of the pedagogical emphasis given in the educational systems of the four participating countries and of the special emphasis given by each group of researchers in their initial contacts with the teachers who participated in the present study.

Methodology

Settings

The participating countries differed in the emphasis they gave in introducing the project to the teachers. The Finnish school culture is very autonomous even on the level of developing school curriculum, and Finnish teachers are, in general, rather used to implement new learning methods. The participating teachers were trained to apply a rather demanding pedagogical model of progressive inquiry in their CLE implementations (Hakkarainen, Rahikainen, Lakkala & Lipponen, 2001;[START_REF] Hakkarainen | Emergence of progressive inquiry culture in computersupported collaborative learning[END_REF]. In contrast, the Greek teachers often felt uncertain about how to introduce ICT in their classroom [START_REF] Vosniadou | Information and Communication Technology and the Problem of Teacher Training: Myths, Dreams and Harsh Reality[END_REF][START_REF] Kollias | The Status of CSCL research and practices in Greece[END_REF][START_REF] Kollias | Challenges of implementing CSCL designs in the Greek classrooms[END_REF]. For this reason, this project was introduced to them with a focus on students' prior knowledge, free expression and discussion of their own opinions, and new distribution of the responsibility for learning inside the classroom between students and teacher [START_REF] Vosniadou | How Children Learn[END_REF].

The educational theories in which the Italian partners referred emphasize the role of collaborative learning and co-constructivism [START_REF] Ligorio | Collaboration, Constructivism, Community: The Three "C" for the CSCL in Italy[END_REF]. During the project, the participating teachers were specially required to put in practice the principles of these theories. Finally, in the case of Dutch education, emphasis was given on skills of learning, thinking, collaboration and regulation [START_REF] Molenaar | CSCL in the Netherlands[END_REF]. The Dutch teachers showed interest towards developing authentic learner-centred learning contexts, and supporting students into 'learning how to learn' within the CLEs.

Participants

Fifty-six teachers from Finland, Greece, Italy and the Netherlands who implemented CLEs in their classrooms participated in this study. There were teachers from both primary and secondary education. Table 1 presents the number of the participating teachers from each country and some parameters describing them.

Table 1 here

Data collection

After the end of the implementation of the CLEs, the four research groups arranged meetings with the participating teachers. In these meetings, the teachers were interviewed relative to different aspects of their experience with the CLEs. The questions of the interviews did not directly ask for the teachers' conceptions of CLEs.

The teachers were asked for an account of the construction and maintenance of the CLEs, and the questions followed the unfolding of the CLEs' implementation in real time.

More precisely, the questions asked (Table 2) were divided into five categories. They represent: the management and the monitoring the CLE environment ('Leading' and 'Assessment'), the teachers' perception of some important general goals in the CLEs: collaboration and open expression of students' opinions ('Alternative Opinions and Collaboration'), the teachers' reflections on the whole project with respect to lessons learned and further planning ('Reflection), and the recollection of positive and negative experiences from the project ('Positive and Negative Experiences').

Table 2 here

Data analysis

The teachers' answers where audio-recorded, transcribed and translated in English by the researchers in each of the four participating countries. The transcribed text was divided in sections called "teachers' comments" based on the principles that a) each comment should belong to an answer of a specific question and b) each comment should belong to only one of the set of categories. In order to create the set of categories on which the comments were assigned, the following process was observed.

The main categories of comments were created based on the activity-theoretical model presented in the introduction. Due to the prominence of the change in the division of labour in CLEs, the categories 'Subject' and 'Division of labour' were replaced by the categories 'Student' and 'Teacher', which refer to the changing roles and the concerns of these main actors. The category 'Object' was replaced by the category 'Accountability' which captures the teachers concerns about the effectiveness of the whole CLE activity system. The other categories were 'Software', 'Communities', 'Norms' and a category called 'New Classroom' that refers to comments that present glimpses of qualitatively new learning processes in the classroom.

Further examination of the transcribed text resulted in the creation of subcategories leading to the final set of categories presented in Table 3. More precisely, in the main category 'Student' we distinguished comments referring to the changing division of labour and comments that were emphasizing the new motivational potential of the CLEs. In the main category 'Teachers', we distinguished comments referring to different aspects of the teacher's role. We also distinguished comments that related CLEs with broader pedagogical teacher concerns and with the development of the teacher professional exercise. In the main category 'Community', in agreement to the discussion in the introduction, a vertical and a horizontal dimension was distinguished.

In the main category 'Accountability', we distinguished comments referring to learning gains, collaboration or skills. Finally, the main category 'New Classroom' was differentiated, based on whether the comments were referring to a well-knit organization of assessment and performance, to a sense of "flow" of the classroom while performing the inquiry activity. Descriptions of the different categories are given in the Appendix. Examples of comments belonging to each category are reported in the Results section.

Table 3 here Comments that referred to issues outside of the aims of the interview were left out of the analysis. Two researchers rated the whole text, and the final agreement was above the 85% level.

The separation of the transcribed text into categorized comments was used both towards performing a quantitative analysis and towards performing a qualitative analysis. In the case of the quantitative analysis, we used the patterns and correlations of percentage distributions of teachers' comments. In the case of the qualitative analysis the categorization of the comments was used to extract the main themes that were coming out of the teachers' responses.

Results

Quantitative analysis

Table 4 presents the frequency and percent of teachers' comments for each group of questions clustered by country (The percentages add to 100% when adding all comments referring to the same country).

Table 4 here

In Table 5 the teachers' comments are grouped based on their classification into categories and are clustered by country (The percentages add to 100% when adding all comments referring to the same country).

Table 5 here In order to get common trends and differentiations among the teachers in different countries we noticed first the distribution of teachers' comments for each of the main categories, for each nationality (Totals, in Table 5). Figure 1 presents the plots of these percents (the percents of teachers' comments belonging to each of the main categories) per country.

Figure 1 here

The Greek teachers present a clearly different profile of their comments, with main differences being the prominence of the category 'Teacher', and the low presence of the categories 'Software' and 'New Classroom'. The teachers from the other three countries present similar profiles: Percents are evenly spread among 'Teacher', 'Student', 'Accountability', 'Software', 'New Classroom". The Finnish teachers have more numerous comments referring to 'Student', while the Italian teachers refer more to the 'Software'.

Paying attention to the full number of categories (Table 5), the category 'Development of Professional Expertise' should be highlighted as indicative of the reflection that is generated to the teachers through the participation in the CLEs.

We examined also how the categories of the teachers'comments were distributed among the different groups of questions in each country. Tables 6 and7 refer to two differences that come prominent out of such a comparison; they concern the main categories 'Student' and 'Accountability' respectively.

Table 6 here

In the Creek teachers' comments, the category 'Student' was prominent in the 'Reflection' group of questions. Since this question group strongly represents issues that teachers feel as ongoing struggles in their pedagogy, this is an indication that the changing role of the student was a greater concern for the Greek teachers than for the teachers from the other nationalities. For the Finnish and the Dutch teachers, the same category is prominent in the 'Positive and Negative Experiences' question group, indicating a concern for confirmatory evidence relative to educational choices (connected with empowering the student) that have been made and worked through.

Finally, in the Italian teachers' comments the category 'Student' is strongly represented in the question group 'Alternative Opinions and Collaboration', indicating an ease with sharing learning responsibility with students and concentration to the actual cognitive and social aspects of students' engagement in the CLEs.

Table 7 here From Table 7 can be concluded that the Italian and the Finnish teachers made most of their comments about 'Accountability' in the question group 'Positive and Negative Experiences'. This indicates their sense of the CLE as a functioning unit whose accountability is judged as a whole. The Greek teachers mainly mention 'Accountability' on the question group 'Assessment', indicating a fragmented understanding of the CLE and attention to accountability provided from separate aspects of the environment. For the Dutch teachers, accountability seems to be a constant concern throughout all groups of questions.

Qualitative analysis

In the case of qualitative analysis, the comments that refer to each of the categories were read and common themes were extracted that are relevant to the teachers' conceptions of CLEs. Some of these themes were common for the teachers of all nationalities and some differentiated among the teachers from different countries.

The examples mentioned are characteristic comments from different teachers. In each case the nationality, level of education and gender of the teachers are mentioned.

Teacher comments related to Students a) Division of labour: Student role

The teachers from all the countries described CLEs as student-centred environments, which give affordances for students to actually take more learning responsibilities.

"This tool has allowed students to be more independent" (Greece, primary, female) "Students understand you are there to help them if they are in troubles ...basically they do the work, they are the main actors" (Italy, secondary, female) Since the change in the student role is related to the change in teacher role, CLEs are seen as environments where the transfer of responsibility is a challenge for the teacher. This was expressed either implicitly, as a post facto wish for having given more responsibility to the students, or explicitly by describing the difficulty the teachers felt in this process.

"It is hard, especially for older teachers, to give away responsibility. You give away the complete grip! Students have to learn how to give feedback" (The Netherlands, primary, male)

In Finland and the Netherlands, CLEs were described as learning environments that are demanding for the students, where the students have to try hard to be successful. This belief came through either implicitly, by referring to the various demanding tasks that students had to perform (evaluating theirs and others work, searching information), or explicitly.

"Collaborative writing of stories was challenging. Some of the groups were successful, some of them had difficulties with finishing the process together: some students took too dominative roles and did not share responsibilities, some of the students withdrew upon their own choice. One group split into two." (Finland, primary, male) b) Motivating the students In this category, the teachers expressed, through their comments, the belief that CLEs are highly motivating for students.

"Students feel that they can participate in the lesson and that they can offer in the group. This makes it more interesting for them to participate. Moreover, even the better students, do not feel bored because even for them the task was demanding" (Greece, secondary, female) "The most positive aspect I saw is that they were enthusiastic in doing something that remains on the internet, something which leaves a trace" (Italy, secondary, female)

CLEs were also thought of as motivating for students who underachieve under usual classroom conditions or who are usually shy. There were no comments mentioning better students being bored because of being unchallenged. In the case of the Netherlands, in particular, CLEs were seen as environments where student motivation is dependent on the careful design of the learning environment. As time proceeds, initial motivation can evaporate if not supported:

"The project lasted too long. The students' interest disappeared" (The Netherlands, primary, male) Moreover, the Dutch teachers mentioned differences on how eager the students were to participate: "I think it is a problem that some students want to continue working (and deepen their knowledge) and others students have a feeling that they have seen enough" (The Netherlands, primary, male) "I think that one has to be prepared about different "scenarios" of how the interaction in the classroom may play out. This is especially critical when one takes into account the differences among students and the different speed with which they proceed in the interaction" (Greece, secondary, male) "I would take more time for the preparation" (The Netherlands, secondary, male) c) Division of labour: teacher role performance

Teacher comments related to Teachers

The teachers from the four countries differed in how specific they saw teachers' guiding role in the classroom while the project takes place. The teachers from Finland were the most articulate in this respect.

"It was challenging to see how the students learned to search, to elaborate and to deepen their knowledge and especially to focus their research questions by themselves. The students needed a lot of guidance during these phases" (Finland, secondary, male) "The fact that students' thinking is visible in the database helps me guide students better than before. As a teacher, I can also see, on what level students' thinking is, and how concretely or abstractly they can process knowledge" (Finland, primary, female)

The Greek teachers refer to specific guidance incidences, focusing on their own activities in guiding in the CLEs.

"We encouraged them to collaborate and make the best of their opportunity to communicate (turn to their fellow students for help, ask for clarifications, make their own ideas as clear as possible, explain). Occasionally, we pointed out things that needed to be better elaborated"(Greece, primary, female)

The Italian teachers did not speak specifically about this aspect of CLEs, while the Dutch teachers made only a few relative comments. It appears that the issue of teacher guidance in the CLEs was a hazy region for most teachers. This is necessary for learning. And it is very important in the rest of their life. To have an own opinion and be able to give arguments" (The Netherlands, primary, male)

The issue appeared to a lesser degree in the Greek and Italian teachers' comments, while it was very rare for the Finnish teachers.

e) Development of Professional Expertise

Finally, CLEs were seen as great facilitators of progress in professional knowledge/expertise?.

"FLE was useful for me as a teacher. I learned more about students' thoughts and I could guide students more precisely. I have got familiar with totally new way of teaching and feeling of success" (Finland, primary, female) "However I realize that now there is demand for much more work for me, that I need to master new skills and that, although I will work more, I will need to defend myself against criticism from know-it-all parents" (Greece, secondary, male)

This aspect of the teachers' experience of CLEs was unexpected to us, and it points to the CLEs' potential as instruments for developing teachers' pedagogical expertise. The students were divided into groups according to their topics. The division of labour in the groups was surprisingly well organized" (Finland, secondary, female) "Using the software and exchanging products and ideas with distant pupils, my pupils were conscious of the other pupils' presence. My pupils realized that distant pupils were like them... that they would conclude their own tales... my students were carried away by this newness" (Italy, primary, female)

Teacher comments related to

These glimpses of a qualitatively new classroom were occasionally present in the teachers' comments, with the exception of the Greek teachers.

Teacher comments related to Accountability

The teachers thought that CLEs have to be accountable along the lines that other learning environments have to. In addition to the emphasis on learning gains and skills there also appears an emphasis on the assessment of collaboration. Here, time and experience were also mentioned as important factors for the development of teacher mastery. CLEs were also seen as related to the development of ICT skills, although more general skills were mentioned as well.

"Short assignments following the process of inquiry were maybe not cognitively deep, but principles of this type of work were surely introduced and in the second time these students can see the process better and can set up better research problems" (Finland, secondary, male)

"This was of great importance, both for students and for teachers. Students came to realize themselves how they think about numbers-in some cases; they just found out that they have been making wrong use of such terms as "rational numbers". But, what was really interesting is when some of them actually realized that they had deeper misconceptions" (Greece, primary, female)

The Italian teachers were the ones who mainly pointed to new student proficiencies and potential skills to be assessed (collaboration skills, organizational and communicational skills), together with computer science and information organization skills. However they did not seem so eager for quantifiable assessment. The Greek teachers were interested in a more personalized assessment, and were concerned about (traditional) learning gains.

"You can detect an improvement in the skill of orienting within the paper material or even within the technological environments, to grasp information, to select, order it and classify" (Italy, secondary, female)

The Dutch teachers were especially concerned with the issue of assessment. They preferred quantifiable assessment and more personalized types of assessment. They also cared for end products, assessment of process and future student benefits.

"We want to do a test that belongs to the regular method.

To check what they have learned" (The Netherlands, primary, male)

Teacher comments related to Software

The nature of the software was a prominent element in the teachers' conception of CLEs. Evaluations of aesthetics, usability, speed of execution, unexpected drawbacks, referring to the software, are inherited in the CLEs.

"The login-method is very inefficient. It takes two e-mails to get them into your

project. And when something goes wrong, they end up in the public part of Synergeia, thinking that they have arrived at the correct place. Leaving that aside, it is easy to learn. If you have no fear for buttons, you'll find your way..." (The Netherlands, secondary, male) CLEs were also seen as places of design freedom with respect to software, and the teachers felt free to ask for lots of changes. This idea is in accordance with a more general feeling that ICT is connected with freedom of action. The nature of the ITCOLE project, as a development project in which the teachers were asked at various phases to give feedback and suggestions for technical developers, may have also strengthened this feature in the teachers' responses.

There were no examples of deeper thinking about the interaction between software characteristics and learning mechanisms. The teachers spoke about the software tool that was used in the CLE in very concrete terms. The functionalities are useful for specific actions.

Teacher comments related to Community a) Community: Vertical

In putting CLEs within the broader institutional setting, there appear issues of school organization and national organization.

"A negative feature was the organizational issues that had to be faced before the computer classroom could be used by students from different classes" (Greece, secondary, male) "It should be, even from our side (teachers), more co-ordination and homogeneity in planning the activity" (Italy, secondary, female) "Can this software be used really broadly in the Greek educational system? The time it needs to be realized seems extreme for the Greek educational system. It is also difficult to find equilibrium between talking face-to-face in the classroom and working in Synergeia" (Greece, secondary, female)

The implementation of the CLEs introduced strains that made salient the shortcomings of school organization and of the national curriculum.

b) Community: Horizontal

By participating in the CLEs, many teachers in all four countries felt that their trust on students' ability to direct their own learning increased, and their relationships with students strengthened.

"From my experience in the classroom I thought that students were not so interested about what other students where thinking. However when working with the project I saw a different picture. Students were really interested on what each other was thinking" (Greece, secondary, male) "For me, as a teacher that was very instructive. I learned that students are able to learn a lot from each other" (The Netherlands, primary, male) "Synergeia allowed the kids to see us as persons able to give them the opportunity to make more friends, to improve the way they used computers, which they really love to do, and first of all to create, through this software, contacts with people they don't know and that most likely think differently from them, therefore this has been very positive for them" (Italy, primary, female)

Teacher comments related to Norms

In the case of the Finish and Italian teachers, the few comments made about norms indicate that classroom norms combined well with the functioning of the CLE environment. The Greek and Dutch teachers' comments referred, occasionally, to a tension between current norms and the pedagogical principles that accompanied the CLEs.

"However in the groups some students were able to dominate the discussion. I feel that I did not manage to deal effectively with this issue" (Greece, primary, female) "Students are used to talk to each other in groups. They prefer to do this, instead of giving comments in Synergeia" (The Netherlands, primary, male)

Discussion and conclusions

Putting together the results of our study we end up with both expected and unexpected outcomes. As was expected, the teachers conceived CLEs as learning environments that are strongly student-centred, and give affordances to the students to take more learning responsibilities. They were, moreover, seen as challenging for the teacher due to the transfer of responsibility and, perhaps more surprisingly, due to a sense of danger that teachers may get stuck in the role of just giving technical advice.

CLEs were thought of as highly motivating for the students, appropriate for addressing students that are usually shy, without being boring for those who are achieving well in the more traditional school learning environments.

CLEs were conceived as environments that demand careful planning at several levels. Perhaps surprisingly, out of the teachers' comments from all countries came a message that participating in CLEs facilitates the development of professional knowledge. However, specific strategies for student guidance in the classroom were not well articulated in the teachers' CLEs conceptions.

As was expected, the software was a prominent element in the teachers' conception of CLEs. Within this dimension, the teachers mentioned issues related to aesthetics, usability, speed of execution, sensitivity of the whole CLE on drawbacks experienced in the software. Moreover, there emerged a sense of freedom to experiment with the varieties of software design. However, precise thoughts about the interplay between software design and student cognitive strategies were lacking among the teachers' comments.

In talking about accountability, the teachers argued that CLEs should be assessed along similar lines with other learning environments. The Dutch teachers were particularly persistent in this respect. In addition to the emphasis on learning products, the teachers emphasized also skills (particularly ICT skills) and effective collaboration.

There were no demands expressed for new types of assessment aiming towards new competencies.

In three of the four countries (the exception is Greece) we got glimpses of a qualitatively advanced classroom where a CLE has been integrated. In such a classroom, ongoing evaluation is well-knit with student performance and at times cases of " flow of classroom work" were described.

Finally, for the teachers of all countries, participation in the CLEs influenced their relations with the student community, and increased their trust on students' competences. Moreover, CLEs were expereienced as "factors causing crisis" to the educational system and to the school organization. It seems that all the teachers realized that combining integration of CLEs in the classrooms and taking account of the national curricula is a demanding task.

Next to these common features, the teachers of the participating countries presented also a variety of profiles that differentiated them.

The Finnish teachers described CLEs in a positive light and found them fitting to the norms of their classrooms. They conceived them as environments that put special demands on students, and they reported many instances where they saw in CLEs the glimpses of a qualitatively new classroom. They were also the most articulate with respect to the guidance provided to the students.

The Italian teachers thought of CLEs as a natural tool that resonates with a collaborative and constructive pedagogy that they already espoused and practiced. In addition, they reported glimpses of a new classroom in CLEs, and felt possibly most at ease with sharing learning responsibilities with their students. The Italian teachers did not find that CLEs were too demanding for the students and felt at ease to propose many different variations for the software tools that supported the CLEs in the ITCOLE project, in order to make them more effective.

The Finnish and Italian teachers were the ones who felt most comfortable with the pedagogy supporting CLEs. The two countries, however, differed strongly in the availability of PCs in order to implement the CLEs. As a result, the advantages or disadvantages of the software had greater consequences for the Italian teachers, and were more strongly commented upon.

The Dutch teachers were the ones who mostly stressed that CLEs have to be assessed according to similar principles as other learning environments. It is possible that their strong concern about accountability is related to the many innovations introduced in the Dutch education, and to their own effort to have a control on the influx of innovation based on clear assessment. However, this concern is tempered by references on new practices in the classrooms and the teachers' interest about the possibility of changing the distribution of learning labour between teachers and students in the CLEs. Although the Dutch teachers saw CLEs as motivating to the students, they were concerned about the duration of the enthusiasm.

The results of both quantitative an qualitative analyses indicate that the Greek teachers' conceptions of CLEs were still dominated by the teachers' role and the actions that teachers do. The Creek teachers did not state that CLEs are too demanding for the students, neither did they report glimpses of a new classroom in the CLE environments, and their statements of accountability followed traditional lines. The Greek teachers' conceptions of CLEs were the ones that appear most distant from the features of powerful learning environment. It could be claimed that for the Creek teachers there was the biggest gap between the principles that guided the implementation of the CLEs and the hierarchical and authoritative national school culture. However, even in this case, CLEs were appreciated; the Creek teachers were concerned with the division of labour between teachers and students, as can be concluded from both the qualitative and the quantitative analysis of the data, and the category "Development of Professional Expertise" was strongly represented in the teachers' comments.

On the whole, the tension that the change in the division of labour between teachers and students creates is well represented in the teachers' conceptions about CLEs. The teachers realized the need for stronger student centeredness, and they tried to accommodate for it. It is interesting that the teachers paid attention to the signs of a new classroom culture, and that even in the cases of the teachers who did not mention that (i.e. the Greek teachers), there was positive acceptance of CLEs and a responsible attitude towards better planning. Moreover, participation in the CLEs made salient the issues of professional development for the teachers in all the participating countries, and issues of the current handicaps of school and national curriculum. All these factors resonate with the "reflection upon experience, classes taken, and the context or culture of the school" mentioned by [START_REF] Dexter | Teachers' Views of Computers as Catalysts for Changes in their Teaching Practice[END_REF], making CLEs particularly promising candidates for an introduction of ICT in the schools in order to catalyze pedagogical innovation.

In the side of concern, the teachers were not very reflective on the precise strategies by which they guided the students in the classrooms, and on the relation between specific features of the software used and student cognitive strategies.

Moreover, although CLEs were found motivating even for students who are usually shy, some teachers were aware of the fragility of the students' interest. Hence, teachers will need more support in understanding the guidance of student learning and the social structure of the classroom when CLEs are implemented. But it can be concluded by the teachers' awareness of the need for careful planning when implementing CLEs that participation in the CLEs creates conditions for becoming aware of the need for this kind of support.

Finally, the teachers looked forward to clear assessments of the CLEs.

Traditional measures like learning gains and skills were enlarged by the assessment of collaboration. However, contrary to our expectations, few teachers expressed demands for better assessment of the new competencies that may characterize student performance in the CLEs. Therefore, teachers need support in order to distinguish, in a precise way, the new qualitative characteristics of the CLE classrooms, before understanding the need for new assessment guidelines. This is necessary for learning. And it is very important in the rest of their life.

FIGURE CAPTIONS

To have an own opinion and be able to

  a) Division of labour: teacher role technicalIn all countries, CLEs were seen as presenting the danger for teachers to be overwhelmed by students' need for technical advice. Usually, this was interpreted as a challenge that they can face. "Only afterwards I realized that I had to use almost all the project time for technical guidance; even though I had time to guide in information search and process of inquiry, I did not have time to participate in knowledge building discourse, and I read the discussions later on during my free time" (Finland, secondary, female) "In the beginning I had to spend a lot of time guiding students in the use of Synergeia. As they used it for a longer time, the courage to use it more freely increased" (The Netherlands, primary, male) b) Division of labour: teacher role planning All the teachers expressed the feeling of conviction that CLEs demand careful planning."This type of learning environment demands careful preparation and a possibilityto carry out a project within a tight schedule"(Finland, secondary, male) Planning refers to having the computer room free, taking care of the social organization of the classroom (composition of groups), considering the different learning paths possible (differentiation among students), and creating the supportive structures necessary for the students to stay focused.

  d) Long term pedagogical concerns Discussion about CLEs brings forth long term pedagogical concerns, putting the CLEs in a broader perspective. This dimension concerned, in an explicit way, mainly the Dutch teachers. "These are basic skills. Students have to feel autonomous, appreciated and safe.

  New classrooms a) Accountability: Integrated In many comments by the Finnish, Italian and Dutch teachers, CLEs were seen as environments where assessment and instruction are integrated. This dimension was nearly nonexistent in the comments of the Greek teachers. "I always asked the following questions in the next lesson after the FLE3 sessions: 1. What was good in your work? 2. What aspects of your working could you still develop? 3. What was the usefulness of the starting question for you? In the final exam I asked, what issues helped you with your learning" (Finland, secondary, female) "Synergeia is the place where the teacher does not grade students; you assess together with them the collective work" (Italy, primary, female) b) Activity System In certain occasions, speaking about CLEs brought forth the implemented vision of a new classroom: there were descriptions of the classrooms as a whole, and images of classroom "in flow"."The groups worked enthusiastically, and searched information for each other.

Figure 1 :

 1 Figure 1: Percent of teachers' comments belonging to each of the main categories of teachers' comments per country.

  that now there is demand for much more work for me, that I need to master new skills and that, although, I will work more I will need to defend myself against criticism from know-it-all parents (Greece) This was of great importance, both for students and for teachers. Students came to realize themselves how they think about numbers-in some cases; they just found out that they have been making wrong use of such terms as "rational numbers". But, what was really interesting is when some of them actually realized that they had deeper misconceptions (Greece) , they had to collaborate anyway, and now they are doing this through Synergeia. So they were doing it anyway. But I think Synergeia helps for this. They have more contacts with other groups, when everything is running correctly. But it will take a lot more experience for the students. (The Netherlands) Accountability: Skills Refers to skills that teachers find You can detect an improvement in the skill of orienting within the paper method is very inefficient. It takes two e-mails to get them into your project. And when something goes wrong, they end up in the public part of Synergeia, thinking that they have arrived at the correct place. Leaving that aside, it is easy to learn. If you have no fear for buttons, you'll find your way....(the Netherlands) that they do not comment on each other very much. If they have a question, this question is not answered by peers. I don't know what it takes to accomplish that, but now, it doesn't work. That would be the ideal situation, when they start thinking about questions of classmates. But as long as I keep posting myself, then it's very effective. I get positive response then. It's very useful for them, especially to have a look at it when they are at home. It resembles a class situation, where students are also shy to answer each others' questions." (The Netherlands)

Table 1

 1 Number of participating teachers for each country and their distributions relative to educational level, gender, age, years of teaching and experience in CLEs

	TABLES
	Nationality	Number	Level:	Gender:	Age:	Years of	Experience
		of	Primary-	Male-	Average-	Teaching:	in CLEs:
		teachers	Secondary	Female	StDev	Average-	Much-Some-None
						StDev
	Finland	15	6 -9	5 -10	38 -7	10 -6	4 -5 -6
	Greece	9	2 -7	7 -2	40 -9	12 -9	2 -2 -5
	Italy	22	16 -6	1 -21	45 -7	15 -9	3 -2 -17
	Netherlands	10	5 -5	7 -3	*	*	0 -1-9

* Data not have available

Table 2

 2 Questions asked in the interviews clustered in Groups.

	Groups	Exact Questions
	Leading	1. As a teacher, how did you help and guide students during the project?
	Assessment	2. Carrying out the project how did you deal with the issue of assessment?
		What did you choose to assess?
		3. Can the software tool facilitate you in the way you are usually assessing
		your students? Does it offer new possibilities for carrying out the
		assessments?
	Alternative Opinions	4. Do you think the project succeeded in getting the students to collaborate?
	and Collaboration	Was there a benefit in collaboration? If yes, what exactly was the benefit?
		5. Do you think that the project succeeded in getting the students to express
		their alternative opinions more openly? What were the advantages or
		disadvantages (if any)?
	Reflection	6. Now that you have implemented the project, what would you do differently
		next time?
		7. Did the use of the software change your usual teaching practices in any
		way?
		8. Did the project make you reconsider any of your beliefs about teaching and
		learning?
	Positive and Negative	9. What were your positive and negative experiences during the project?
	Experiences

Table 3

 3 Main Categories and final Categories (including subcategories) of teachers' comments

	Main Categories Categories
	Student	Division of labour: Student role
		Motivating the student
	Teacher	Division of labour: teacher role technical
		Division of labour: teacher role planning
		Division of labour: teacher role performance
		Long term pedagogical concerns
		Development of Professional Expertise
	New Classroom	Accountability: Integrated
		Activity System
	Accountability	Learning gains
		Collaboration
		Skills
	Software	Software
	Community	Community: Vertical
		Community: Horizontal
	Norms	Norms

Table 4

 4 Frequency and Percent of teachers' comments for each group of questions, clustered by country and group of questions

	Group of Questions	Number of	Percent of the
		comments	total number
			in each group
			of questions
	Finland
	1. Leading	11	10 %
	2. Assessment	17	15 %
	3. Alternative opinions and collaboration 20	15 %
	4. Reflection	21	15 %
	5. Positive and Negative Experiences	57	45 %
	Greece
	1. Leading	12	10 %
	2. Assessment	18	20 %
	3. Alternative opinions and collaboration 19	20 %
	4. Reflection	28	30 %
	5. Positive and Negative Experiences	17	20 %
	Italy
	1. Leading	17	15 %
	2. Assessment	7	5 %
	3. Alternative opinions and collaboration 28	25 %
	4. Reflection	24	20 %
	5. Positive and Negative Experiences	44	35 %
	The Netherlands
	1. Leading	8	10 %
	2. Assessment	11	10 %
	3. Alternative opinions and collaboration 17	20 %
	4. Reflection	28	30 %
	5. Positive and Negative Experiences	30	30 %

Table 5

 5 Frequency and percent of teachers' comments in each category of teachers' comments clustered by country

		Finland	Greece	Italy	The Netherlands
	Student
	Division of labour: Student role	10% (13)	4% (4)	5% (6)	7% (7)
	Motivating the student	11% (14)	5% (5)	10% (12)	7% (7)
	Totals	21%	10%	15%	15%
	Teacher
	Division of labour:
	teacher role technical	3% (4)	4% (4)	0% (0)	2% (2)
	Division of labour:
	teacher role planning	6% (8)	11% (10)	9% (11)	7% (7)
	Division of labour:
	teacher role performance	10% (13)	13% (12)	4% (5)	4% (4)
	Long term pedagogical concerns	1% (1)	4% (4)	4% (5)	9% (8)
	Development of
	Professional Expertise	3% (4)	12% (11)	12% (15)	11% (10)
	Totals	24%	45%	30%	33%
	New Classroom
	Accountability: Integrated	7% (9)	2% (2)	7% (8)	6% (6)
	Activity System	10% (12)	1% (1)	7% (8)	9% (8)
	Totals	17%	3%	13%	15%
	Accountability
	Learning gains	6% (8)	9% (8)	4% (5)	4% (4)
	Collaboration	2% (2)	10% (9)	8% (10)	6% (6)
	Skills	6% (8)	0% (0)	2% (2)	3% (3)
	Totals	14%	18%	14%	14%
	Software
	Software	13% (16)	5% (5)	20% (24)	12% (11)
	Community
	Community: Vertical	7% (9)	3% (3)	3% (4)	2% (2)
	Community: Horizontal	2% (2)	8% (7)	2% (2)	4% (4)
	Totals	9%	11%	5%	6%
	Norms

Table 7

 7 Frequency and Percent of teachers' comments belonging to the 'Accountability' main

	category of teachers' comments, along the different groups of questions according to
	nationality
	ACCOUNTABILITY	Finland	Greece	Italy	The Netherlands
	Leading	0% (0)	0% (0)	0% (0)	0% (0)
	Assessment	11% (2)	63% (10) 6% (1)	23% (3)
	Alternative opinions
	and collaboration	11% (2)	25% (4)	22% (4)	31% (4)
	Reflection	0% (0)	0% (0)	6% (1)	23% (3)
	Positive and Negative Experiences 79% (15) 13% (2)	67% (12) 23% (3)

Acknowledgements

This research was conducted under the funding of the European Union for the Project ITCOLE in the Information Society Technologies (IST) framework; IST-00-III.2 'School of Tomorrow': http://www.euro-cscl.org

We are grateful to all the teachers and students who participated in the ITCOLE-project, and to our colleagues that collaborated with us in this project: Philip Dean, Teemu Leinonen, Giedre Kligyte, Kai Hakkarainen, Minna Lakkala, Marjaana Veermans-Rahikainen, Jiri Lallimo, Essi Ryymin-Haatainen, Kati Korhonen, Wilfred Rubens, Bruno Emans, Henk Sligte, Beatrice Ligorio, Donatella Cesareni, Alessandra Talamo, Ilaria Mancini, Rudolf Ruland, Wolfgang Appelt, Antonio Gomez Skarmeta, Toni Martinez Carreras, José Antonio Pérez Sánchez, Pedro Garcia Lopez, and Gerry Stahl.

APPENDIX

The teachers' comments were categorized by using the following definitions. The Examples are sentences extracted from the interviews.

Category


Pegah Kamousi

Sylvain Lazard

Anil Maheshwari

Stefanie Wuhrer

Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph

Keywords: Farthest Point Sampling, Approximate Geodesics, Shortest Paths, Planar Graphs, Approximation Algorithms

A standard way to approximate the distance between two vertices p and q in a graph is to compute a shortest path from p to q that goes through one of k sources, which are well-chosen vertices. Precomputing the distance between each of the k sources to all vertices yields an efficient computation of approximate distances between any two vertices. One standard method for choosing k sources is the socalled Farthest Point Sampling (FPS), which starts with a random vertex as the first source, and iteratively selects the farthest vertex from the already selected sources.

In this paper, we analyze the stretch factor F FPS of approximate geodesics computed using FPS, which is the maximum, over all pairs of distinct vertices, of their approximated distance over their geodesic distance in the graph. We show that F FPS can be bounded in terms of the minimal value F * of the stretch factor obtained using an optimal placement of k sources as F FPS 2r 2 e F * + 2r 2 e + 8r e + 1, where r e is the length ratio of longest edge over the shortest edge in the graph. We further show that the factor r e is not an artefact of the analysis by providing a class of graphs for which F FPS 1 2 r e F * .

Introduction

In the context of shape analysis, it is commonly required to compute and analyze geodesics between many pairs of vertices on a shape that is represented by a connected undirected graph G with n vertices and m edges. To compute shortest-path queries from a single-source on G, Dijkstra's algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF] takes O(n log n + m) time. To compute a Département d'Informatique, Université Libre de Bruxelles, Belgium, E-mail: pegahk@gmail.com b Inria, Loria, Nancy, France, E-mail: sylvain.lazard@inria.fr c School of Computer Science, Carleton University, Canada, E-mail: anil@scs.carleton.ca d Inria Grenoble Rhône-Alpes, France, E-mail: stefanie.wuhrer@inria.fr all-pairs shortest-paths, we can run Dijkstra's algorithm starting from each of the n vertices and, while there are more efficient methods, this problem has a trivial Ω(n 2 ) lower bound.

To reduce this complexity, the problem of efficiently approximating the distance between any two vertices is often considered. A very recent method efficiently computes a (1 + )-approximation to a single such query in a planar graph in O((log log n) 3 / 2 + log log log log((log log n)/ 2 )/ 2 ) time and O(n((log log n) 2 / +(log log n)/ 2 ))) space [START_REF] Wulff-Nielsen | Approximate distance oracles for planar graphs with improved query time-space tradeoff[END_REF].

In contrast to this work that builds a carefully chosen data structure, we are interested in a class of simple algorithms, commonly used in practice, that compute in a preprocessing phase a set S = {s 1 , . . . , s k } of k vertices, called sources, in G and runs Dijkstra's algorithm from each of them in O(k (n log n + m)) total time. Then, the distance between any two vertices p and q is approximated as the minimum, over all k sources, of the distance from p to q through one of the sources. The quality of the worst approximation is characterized by the stretch factor, defined as the maximum, over all pairs of distinct vertices, of their approximated distance over their geodesic distance in the graph, that is

F = max (p,q)∈V, p =q min s i ∈S d(p, s i ) + d(s i , q) d(p, q) ,
where V denotes the set of vertices of G and where the function d(., .) measures the shortest geodesic distance between two vertices. Throughout this paper, we use for simplicity the notation max p,q for max (p,q)∈V, p =q .

A natural problem is thus to compute an optimal placement of k sources that yields a minimum stretch factor, denoted F * . We refer to this problem as the k-center path-dilation problem. This problem is NP -complete even for planar graphs because the existence of at most k sources so that the stretch factor is 1 is trivially equivalent to the existence of a vertex cover of size at most k, which is NP -complete even for planar graphs [START_REF] Garey | The Rectilinear Steiner Tree Problem is NP-Complete[END_REF]. 1 Furthermore, we show in [START_REF] Kamousi | Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph[END_REF] that the k-center path-dilation problem is also NP -complete in the case of planar triangle graphs (i.e., connected graphs whose faces have three edges and whose edges are incident to at most two faces), which are of particular interest for shape analysis.

For computing a set of at most k sources, Könemann et al. [START_REF] Könemann | An approximation algorithm for the edge-dilation k-center problem[END_REF]Thm. 3] present a simple algorithm that yields a stretch factor

F K 2F * + 1 + in time O(k (n log n + m) log(n r e /
)) for any > 0, where r e is the lengths ratio of the longest over the shortest edges in G. For convenience of the reader, we detail in Section 2 their algorithm and proof because they missed the term and did not state the complexity.

In this work, we analyze the stretch factor of the even simpler and commonly used Farthest Point Sampling (FPS) heuristic for selecting a set of k sources [START_REF] Gonzalez | Clustering to minimize the maximum intercluster distance[END_REF][START_REF] Moenning | Fast marching farthest point sampling[END_REF]. FPS starts by selecting a random vertex and iteratively selects a vertex that has the largest geodesic distance to its closest already selected source, until k sources are picked. Running Dijkstra's algorithm from each of the sources directly yields a total running in O(k (n log n + m)).

To the best of our knowledge, no theoretical results are known on the quality of the stretch factor, F FPS , obtained by an FPS of k sources, compared to the minimal stretch factor F * . In this paper, we prove that for any connected undirected graph and any choice of k sources obtained by the FPS algorithm,

F FPS 2r 2 e (F * + 1) + 8r e + 1,
where r e is the lengths ratio of the longest over the shortest edges in G (Theorem 1). We further show that the factor r e is not an artefact of the analysis by providing a family of graphs for which F FPS 1 2 r e F * (Theorem 6). This shows that if the ratio r e is large, F FPS can be much larger than the optimal stretch factor F * but, on the other hand, F * is likely to be large as well. Indeed, consider a graph with k + 1 arbitrarily small edges such that all their adjacent edges are long enough: at least one of these edges is not incident to a source and for the endpoints of this edge, their approximated distance over their geodesic distance is arbitrarily large. Note that all our bounds also hold in the case where the edge lengths ratio r e is defined only by pairs of edges that belong to one and the same shortest path in G.

The relevance of our bounds on F FPS is to give some theoretical insight on why FPS has been used successfully in heuristics for shape processing. However, it should be stressed that the edge lengths ratio r e appears in the upper and lower bounds on F FPS but not on F K . Still, r e appears in the running time for the latter and not for the former, but since it appears in logarithmic form, it is fair to expect that Könemann et al.'s algorithm would give better results in terms of the combination of stretch factors and running times than the widely used FPS algorithm. Nevertheless, we are not aware of any experimental study on the subject.

After discussing related work in Section 2, we prove our main results, Theorems 1 and 6 in Sections 3.1 and 3.2 respectively.

Related Work

Computing geodesics on polyhedral surfaces is a well-studied problem for which we refer to the recent survey by Bose et al. [START_REF] Bose | A survey of geodesic paths on 3d surfaces[END_REF]. While much work on surface processing compute geodesics that are allowed to pass through the interior of faces, much work also restrict geodesics to go through vertices and edges, as they are easy to compute. In this paper, we restrict geodesics to be shortest paths along edges of the underlying graph.

The FPS algorithm has been used for a variety of surface processing tasks. The algorithm was first introduced for graph clustering [START_REF] Gonzalez | Clustering to minimize the maximum intercluster distance[END_REF], and later independently developed for 2D images [START_REF] Eldar | The farthest point strategy for progressive image sampling[END_REF] and extended to 3D meshes [START_REF] Moenning | Fast marching farthest point sampling[END_REF]. This sampling strategy has been used to efficiently compute approximate geodesic distances [START_REF] Ben Azouz | Approximations of geodesic distances for incomplete triangular manifolds[END_REF][START_REF] Giard | From mesh parameterization to geodesic distance estimation[END_REF], to recognize the class of an input shape [START_REF] Elad | On bending invariant signatures for surfaces[END_REF][START_REF] Mémoli | Comparing point clouds[END_REF], and to compute point-to-point correspondences between surfaces [START_REF] Bronstein | Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching[END_REF][START_REF] Wuhrer | Posture invariant correspondence of incomplete triangular manifolds[END_REF][START_REF] Ruggeri | Isometry-invariant matching of point set surfaces[END_REF]. In practice, F FPS and r e are typically reasonably small. For instance, for the Greek head model consisting of 6607 vertices used by Ruggeri and Saupe [START_REF] Ruggeri | Isometry-invariant matching of point set surfaces[END_REF], it is r e = 15.4 and F FPS = 18.8 for k = 500. In our implementation, we computed F FPS by averaging over five sets of randomly chosen sources computed using FPS.

The problem we study is closely related to the k-center problem, which aims at finding k centers (or sources) S = {s 1 , . . . , s k }, such that the maximum distance of any point to its closest center is minimized. With the notation defined above, the k-center problem aims at finding S , such that max p (min i d(p, s i )) is minimized. This problem is NP -hard and FPS gives a 2-approximation, which means that k centers S = {s 1 , . . . , s k } found using FPS have the property that max p (min i d(p, s i )) 2 max p (min i d(p, s i )) [START_REF] Gonzalez | Clustering to minimize the maximum intercluster distance[END_REF].

In the context of isometry-invariant shape processing, we are interested in bounding the stretch induced by the approximation rather than ensuring that every point has a close-by source. A related problem that has been studied in the context of networks by Könemann et al. [START_REF] Könemann | An approximation algorithm for the edge-dilation k-center problem[END_REF] is the edge-dilation k-center problem. Here, every point p is assigned a source, denoted by s p , and the distance between two points p and q is approximated by the length of the shortest path through p, s p , s q , and q. The aim is then to find a set of sources that minimizes the worst stretch, and Könemann et al. show that this problem is NP -hard and propose an approximation algorithm to solve the problem. Könemann et al. [START_REF] Könemann | An approximation algorithm for the edge-dilation k-center problem[END_REF]Theorem 3] also study a modified version of the above problem, which is similar to our problem. In particular and as mentioned in Section 1, they present an algorithm for computing at most k sources that yields a stretch factor of at most 2F * + 1 + in time O(k (n log n + m) log(n r e / )) for any > 0, where r e is the lengths ratio of the longest over the shortest edges in G. Their algorithm and proof go as follows.

For any value α, their basic routine iteratively includes in a set S(α) an endpoint of the shortest edge that cannot yet be approximated with a stretch factor 2α + 1, until no such edges are left or |S(α)| > k [12, §3.3]. 2 Then, denoting diam(G) the diameter of the graph and min the length of its shortest edge, they perform a binary search in )), which is also O(log(n r e / )), calls to the basic routine. 2 If |S(α)| k, the fact that S(α) induces a stretch factor of at most 2α + 1 is not discussed in [START_REF] Könemann | An approximation algorithm for the edge-dilation k-center problem[END_REF] but it follows from Lemma 2 below. 3 The binary search is stated without stopping criteria in [12, Proof of Lemma 2], which is why the term is missing from their approximation factor. 4 Although not mentioned in [START_REF] Könemann | An approximation algorithm for the edge-dilation k-center problem[END_REF], this follows from the same arguments used in the proof of [START_REF] Könemann | An approximation algorithm for the edge-dilation k-center problem[END_REF]Lemma 3].

Approximating Geodesics with Farthest Point Sampling

We start this section with some definitions and notation. We consider a connected graph G in which the edges have lengths from a positive and finite interval [ min , max ], and r e denotes the ratio max / min . We require the graph to be connected so that the distance between any two vertices is finite. In this section, we do not require the graph to satisfy any other criteria, but observe that if it is not planar, the running time of FPS will be

O(k(m + n log n))
, where m is the number of edges.

Given k vertices (sources) S = {s 1 , . . . , s k } in the graph, let s p denote the (or a) closest source to a vertex p and let d(p, S, q) denote the shortest path length from p to q through any source in S, that is min i (d(p, s i ) + d(s i , q)). Let S * = {s * 1 , . . . , s * k } be a choice of sources that minimizes the stretch factor F * = max p,q d(p, S * , q)/d(p, q). Furthermore, let S = {s 1 , . . . , s k } be a choice of sources that minimizes max p d(p, s p ). In other words, the set S * is an optimal solution to k-center path-dilation problem and the set S is an optimal solution to the k-center problem.

This section provides upper and lower bounds for F FPS .

Upper Bound

In this section, we prove the following theorem.

Theorem 1. For any set of k sources returned by the FPS algorithm on a connected graph G with edge lengths of ratio at most r e , F FPS 2r 2 e (F * + 1) + 8r e + 1.

Let S = {s 1 , . . . , s k } be a set of sources returned by the FPS algorithm on a connected graph G. In order to prove this theorem, we first show that, for any set of sources, the stretch factor max p,q d(p,S,q) d(p,q) is realized when p and q are adjacent in the graph (Lemma 2). We use this property to bound this stretch factor in terms of max p d(p, s p ) (Lemma 3). On the other hand, we bound the stretch factor of any set of sites in terms of the stretch factor of an optimal set of sources for the k-center problem (Lemma 5). We then combine these results to prove Theorem 1.

Lemma 2. For any sources S = {s 1 , . . . , s k } and any given vertex q in G, the maximum ratio max p d(p,S,q) d(p,q) is realized for some p that is adjacent to q in G. It follows that the maximum ratio max p,q d(p,S,q) d(p,q) is realized for some p and q that are adjacent in G.

Proof. For the sake of contradiction, let q be any fixed vertex and let p be a non-adjacent vertex that realizes the maximum max p d(p,S,q) d(p,q) and such that among all the vertices p that realize this maximum, the shortest path from p to q has the smallest number of edges.

Let p be the immediate neighbor of p along the shortest path from p to q. As before, d(p, S, q) denotes the shortest path length from p to q through any source in S. Let be the length of the edge pp (see Figure 1). We have d(p, S, q) d(p, S, q) -. Dividing by d(p, q) = d(p, q)we get d(p, S, q) d(p, q) d(p, S, q) d(p, q) -d(p, q) .

On the other hand, by multiplying d(p, q) = d(p, q) + by d(p,S,q) d(p,q)d(p,q) we have

d(p, S, q) d(p, q) - = d(p, S, q) d(p, q) + d(p, S, q) d(p, q) • d(p, q) ,
and therefore

d(p, S, q) d(p, q) d(p, S, q) d(p, q) + d(p, q) • d(p, S, q) d(p, q) -1 d(p, S, q) d(p, q) ,
which contradicts our assumption. Indeed, either the inequality is strict and d(p,S,q) d(p,q) was not maximum, or the equality holds and the shortest path from p to q has fewer edges than the shortest path from p to q. p q p s i s j The property of the previous lemma that max p,q d(p,S,q) d(p,q) is realized when p and q are neighbors allows us to bound it as follows.

Lemma 3. For any sources S = {s 1 , . . . , s k }, we have

2 max max p d(p, s p ) -1 max p,q d(p, S, q) d(p, q) 2 min max p d(p, s p ) + 1.
Proof. For the upper bound, we have d(p, S, q) d(p, s p ) + d(s p , q) 2d(p, s p ) + d(p, q). Therefore, d(p,S,q) d(p,q) 2 d(p,q) d(p, s p ) + 1. This holds for any vertices p and q and thus for those that realize the maximum of d(p,S,q) d(p,q) . Furthermore, d(p, q) min and d(p, s p ) max p d(p, s p ). Hence, max p,q d(p, S, q) d(p, q)

2 min max p d(p, s p ) + 1.
For the lower bound, we have by the triangle inequality that, for any i, d(q, s i ) d(p, s i )d(p, q). Adding d(p, s i ) on both sides, we get d(p, s i )+d(q, s i ) 2d(p, s i )-d(p, q). By the definition of s p , d(p, s i ) d(p, s p ) for any i, thus d(p, s i ) + d(q, s i ) 2d(p, s p )d(p, q). This holds for any i and thus for the i such that d(p, s i ) + d(q, s i ) is minimum, hence d(p, S, q) 2d(p, s p )d(p, q). Dividing by d(p, q), we get d(p,S,q) d(p,q) 2 d(p,q) d(p, s p ) -1. This holds for any p and q and thus for the vertex p that realizes the maximum of d(p, s p ); let p denote such a vertex. We then have that d(p,S,q) d(p,q) 2 d(p,q) max p d(p, s p ) -1. This holds for any q and in particular for the one that realizes max q d(p,S,q) d(p,q) . By Lemma 2, the maximum is realized for a q that is adjacent to p in G, thus, for such a q, 2 d(p,q)

2 max . It follows that max p,q d(p, S, q) d(p, q) max q d(p, S, q) d(p, q) 2 max max p d(p, s p ) -1.
The following lemma bounds the path length between two vertices u and v passing through s u in terms of the shortest path between u and v through any source.

Lemma 4. For any sources S = {s 1 , . . . , s k }, and vertices u, v we have

d(u, s u ) + d(s u , v) d(u, S, v) + 2d(u, v).
Proof. Denote by s i the source that realizes the minimum d(u, S, v) = min i (d(u, s i ) + d(s i , v)). Since by definition d(u, s u ) d(u, s i ), we only have to show that d(v, s u ) d(s i , v) + 2d(u, v). Using the triangle inequality twice, we have

d(v, s u ) d(v, u) + d(u, s u ) d(v, u) + d(u, s i ) d(v, u) + d(u, v) + d(v, s i ),
which concludes the proof.

These results allow us to bound the stretch factor corresponding to the sources returned by the FPS algorithm with respect to the stretch factor corresponding to an optimal choice of sources for the k-center problem.

Lemma 5. Let S = {s 1 , . . . , s k } be a set of sources returned by the FPS algorithm and S = {s 1 , . . . , s k } be an optimal set of sources for the k-center problem. Then

max p,q d(p, S, q) d(p, q) 2r e max u,v d(u, S , v) d(u, v) + 6r e + 1.
Proof. Since S is a set of sources returned by the FPS algorithm, this choice of sources provides a 2-approximation for the k-center problem compared to an optimal solution S ; in other words, max p d(p, s p ) 2 max p d(p, s p ) [START_REF] Gonzalez | Clustering to minimize the maximum intercluster distance[END_REF].

By definition, d(p, S, q) is the minimum over all (fixed) sources s i of d(p, s i ) + d(s i , q). Thus, d(p, S, q) d(p, s p ) + d(s p , q). Moreover, by the triangle inequality, d(s p , q) d(s p , p) + d(p, q) thus d(p, S, q) 2d(p, s p ) + d(p, q). One the other hand, d(p, s p ) max u d(u, s u ), which is less than or equal to 2 max u d(u, s u ) by the 2-approximation property. For clarity, denote by u the vertex that realizes the maximum max u d(u, s u ).

We then have d(p, S, q) 4d(u, s u ) + d(p, q). Now, by the triangle inequality, d(u, s u ) d(u, v) + d(v, s u ) for any vertex v. Thus 2d(u, s u ) d(u, v) + d(v, s u ) + d(u, s u ) which implies, by Lemma 4, that 2d(u, s u ) 3d(u, v) + d(u, S , v). Thus, d(p, S, q) 2d(u, S , v) + 6d(u, v) + d(p, q) and d(p, S, q) d(p, q)

2 d(u, v) d(p, q) d(u, S , v) d(u, v) + 6 d(u, v) d(p, q) + 1.
This inequality holds for any distinct p and q, and any v distinct from u (recall that u is fixed). Thus it holds for the vertices p and q that realize max p,q d(p,S,q) d(p,q) and for the v that realizes max v d(u,S ,v) d(u,v) . Such a v is a neighbor of u by Lemma 2, thus it satisfies d(u, v) max . Since d(p, q) min for any distinct p and q, and max

v d(u,S ,v) d(u,v) max u,v d(u,S ,v) d(u,v) , we get max p,q d(p, S, q) d(p, q) 2 max min max u,v d(u, S , v) d(u, v) + 6 max min + 1.
This finally allows us to prove the main theorem.

Proof of Theorem 1. By Lemma 5 and using the same notation, we have max p,q d(p, S, q) d(p, q) 2r e max d(p, S * , q) d(p, q) + 2r 2 e + 8r e + 1.

Lower Bound

We prove in this section the following theorem.

Theorem 6. For any n 3k, there exists a connected graph on n vertices with edge lengths of ratio at most r e such that, for any set of k sources returned by the FPS algorithm, F FPS d(p, S, q) d(p, q) r e /2.

Proof. We first show that, among any k sources returned by the FPS algorithm on G, at most one is in C. We can trivially assume that k > 1. Let S denote a set of k < k sources computed at some point during the FPS algorithm and assume that S contains exactly one source s in C. Then, any new source is chosen in D \ {p 1 } because max Proof. Consider k specific sources (in red in Figure 2), one of every two vertices in C starting from p 1 . For any two distinct vertices p and q in G, the shortest path from p to q goes through at least one source and thus max p,q d(p,S,q) d(p,q) = 1. Hence, there exists a choice of k sources so that the stretch factor is 1 and so F * = 1.

  [1, 2diam(G)/ min ] to obtain an interval [a, b] of length at most /2 so that |S(a)| > k and |S(b)| k, and they output S(b). 3 They prove that |S(F * )| k F * k, where k F * is the minimum number of sites that can realize the stretch factor F * [12, Lemmas 1 and 3]. Furthermore, since |S(α)| is non-increasing, 4 a < F * and thus b < F * + /2. Hence, S(b) is a set of at most k sites that realize a stretch factor of at most 2 F * + 1 + . Finally, the above complexity is straightforward since every call to the basic routine essentially amounts to O(k) calls to Dijkstra's algorithm and the binary search performs O(log( diam(G)min

Figure 1 :

 1 Figure 1: For the proof of Lemma 2.

1 2 1 FanC 1 Figure 2 : 1 2 r e F * . Lemma 7 .

 111217 Figure 2: Graph G for which F FPS

v∈D\{p 1 }Lemma 8 .

 18 d(v, S ) max and max v∈C d(v, s) 2k -1 < max . Now, as shown in Figure 2, consider in C two distinct vertices a and b that are the closest to p 1 and two distinct vertices a and b that are the farthest from p 1 . If no sources of S are in C, then d(a, S, b) = 2 max +1. Otherwise, there is exactly one source in C, say s. Let C left (resp., C right ) be the subgraph of C that consists of the k -1 edges (and their incident vertices) that are the closest (resp., farthest) to p 1 . If s is in C left , then d(a , S, b ) 2k -1 k = max /2 and if s is in C right , then d(a, S, b) min(2 max + 1, 2k -1) max /2. We thus have max p,q d(p,S,q) d(p,q) max 2 min since d(a, b) = d(a , b ) = 1 = min . An optimal placement of k sources in G yields a minimal stretch factor F * = 1.

  By definition, S is an optimal set of sources for the k-center problem, that is argmin s 1 ,...,s k max p d(p, s p ) and thus min s 1 ,...,s k max p d(p, s p ) = max p d(p, s p ) max p d(p, s * p ).

						u,v	d(u, S , v) d(u, v)	+ 6r e + 1.
	Using the upper bound in Lemma 3 on max u,v	d(u,S ,v) d(u,v) , we have
	max p,q	d(p, S, q) d(p, q)	2r e	2
	We now apply the lower bound of Lemma 3 to S * = {s * 1 , . . . , s * k } which gives
			2 max	max p	d(p, s * p ) -1 max p,q	d(p, S * , q) d(p, q)
	and thus
	max p,q	d(p, S, q) d(p, q)	2r e	max min	(max p,q	d(p, S * , q) d(p, q)	+ 1) + 1 + 6r e + 1
				2r 2 e max p,q

min max p d(p, s p ) + 1 + 6r e + 1.

A NP -hardness proof for general graphs can also be found in[11, §2] but, as it comes as a corollary of another NP -hardness reduction, it is less trivial and it inherently uses non-planar graphs.

Acknowledgments

We thank David Mount for suggesting the addition of a lower bound and for providing an initial construction. This research was initiated at Bellairs Workshop on Geometry and Graphs, March 10-15, 2013. We are grateful to Prosenjit Bose, Vida Dujmovic, Stefan Langerman, and Pat Morin for organizing the workshop and to the other workshop participants for providing a stimulating working environment.