Charlotte Brown
email: c.brown1@lancaster.ac.uk

Rationality and Foolishness: Alternative Forecasting Systems in a Manufacturing Firm

Keywords: Forecasting, organizations, rationality, forecasting support systems

Forecasters in firms are expected to employ mathematical techniques encoded in information systems in order to predict the future demand for a firm=s goods. In practice, many forecasters have eschewed statistical methods of forecasting and depend instead on human expertise. This resistance to the ideals and technologies of forecasting has largely been understood in the literature as a failure of rationality in firms. This paper provides a social and political analysis of forecasting in a case study firm, and examines alternative rationalities present in the firm that legitimate what appears to the forecasting literature as foolish practices. The case study organization, a large manufacturing firm, undertook a process of reform of the forecasting process during the course of the study. This paper explores how resistance to a new forecasting support system was shaped by the local equilibrium that had been reached between rationalities in the firm.

Introduction

Foolishness and rational choice exist side by side in every organization. It is easy to theorize about one while ignoring the other. The challenge is to reconcile them (Freeman 1999, p. 164).

When manufacturing firms think about the future, they do so not only on the grand, sweeping scale of product or market (r)evolution, led by CEOs, strategists or consultants; they also think about the future in a much more pragmatic and short term way. These short-term predictions relate to the demand for their goods and/or services from customers in the immediate future: in the next week, month, or quarter. The employees responsible for this task are often known as forecasters or demand planners, and they typically work within the supply chain department or sales, or in a separate department with links to both functions [START_REF] Fildes | The Organization and Improvement of Market Forecasting[END_REF]. The job of forecasters is to gather information about the past (usually the sales history), about the present (market conditions), and about the future (anticipated promotions or seasonal changes) and synthesize these, often using a specialist information system, into a description of the quantity the firm could sell of each product in the future. This is then put to use by a variety of organizational actors: manufacturing departments use it to determine what to produce and when; sales departments may use it to set targets; senior managers may use it to make decisions about resource allocation [START_REF] Makridakis | Forecasting: Methods and Applications[END_REF].

Research into forecasting assumes, mostly tacitly, that organizations are rational, profit-maximizing organizations. Better forecasts are expected ultimately to reduce costs and increase revenue by informing decision-making about, for example, optimal production scheduling and inventory management. However, predicting the future, even this relatively near-term and pragmatic aspect of the future, is a notoriously difficult task, made more so by the volume of data that has become available to the forecaster in recent decades. Researchers have, therefore, sought systematic answers to this problem, narrowing attention to the complex but mathematically tractable problem of extrapolating potential futures from trends in historical data [START_REF] Whitley | The Fragmented State of Management Studies: Reasons and Consequences[END_REF]. They have accordingly developed and elaborated a set of techniques intended to assist the forecaster that are increasingly encoded in specialist forecasting support systems (FSS). Firms are thought to be motivated to purchase and implement these forecasting support systems by the potential for cost savings [START_REF] Armstrong | Principles of Forecasting: A Handbook for Researchers and Practitioners[END_REF].

Successful implementation of the technologies of forecasting is thus positioned within the literature on forecasting as a rational choice that precedes good forecasting, and thus good business decisions, and thus profit maximization. However, surveys reveal a rather different picture of forecasting support systems in use [START_REF] Mccarthy | The Evolution of Sales Forecasting Management: A 20-Year Longitudinal Study of Forecasting Practices[END_REF][START_REF] Mentzer | Familiarity, Application, and Performance of Sales Forecasting Techniques[END_REF][START_REF] Mentzer | Forecasting Technique Familiarity, Satisfaction, Usage, and Application[END_REF]. The uptake of forecasting support systems has, it seems, been relatively slow, despite the availability of computing resources in the workplace (Sanders andManrodt 1994, 2003). Moreover, these surveys suggest that many firms continue to use primarily humanBexpertisebased approaches to forecasting. They prefer to rely on individuals within the firm, often sales and marketing personnel, to provide opinions about the future that are then used as the basis for forecasts. Even those firms that do use more information technology often seem to do so in ways unintended by the technology developers. They often ignore or misuse the many embedded mathematical techniques that forecasting researchers and experts would consider to be cornerstones of effective practice. This divergence of practice from theory is highly frustrating to forecasting researchers, who are unable to explain this seemingly foolish antagonism of organizations to the proper use of the technologies of forecasting [START_REF] Mahmoud | Bridging the Gap between Theory and Practice in Forecasting[END_REF]. This paper will draw upon a case study of a manufacturing firm in the fast moving consumer goods market to attempt to unpick and reconcile the Arational@ and Afoolish@ choices of a firm that implemented a forecasting system. It will explore how changing ideas of what constituted a successful forecasting practice impacted upon the firm and disrupted forecasting processes.

At the start of the study, the firm maintained two distinct forecasting practices, each very different in approach to the problem of predicting the future. One adhered closely to statistical notions of Agood forecasting@ while the other was almost wholly deviant from it. We will suggest that forecasters in the case study organization were caught in organizational circumstances that created a very different view on the most rational way to produce forecasts, and their use (or failure to use) quantitative technologies in their forecasting information systems reflected these different rationalities. The paper will then consider how forecasting practices, and thus the balance between rationalities, were then disrupted by the forced introduction of a new forecasting support system by senior managers intent upon imposing a single rational system on the whole firm.

This case study will be laid out in more detail in the third of four further sections below. First, however, this paper will briefly review the literature on forecasting in organizations and relate this to ideas of success and failure within the IS literature. The second section will consist of a short discussion of the methodology used to generate the case study. The third section will introduce and discuss the case study firm, a large alcoholic beverages firm that will be described under the pseudonym of Global Beverages UK. Finally, the paper will reach some conclusions about the problem of the rational in forecasting practice, and consider some future extensions of this research.

2

Literature Review

The Rational Ideal in the Forecasting Literature

The success or failure of systems is a major theme in the information systems literature. This manifests itself particularly in analyses that locate an IS failure within an organization and then attempt to unravel its origins. This research historically originated in discussions of mechanical deficiencies [START_REF] Lyytinen | Different Perspectives on Computer Systems: Problems and Solutions[END_REF]), but has increasingly focused on issues not of simple failure to function, but rather of mismanagement, misuse, and abandonment [START_REF] Wilson | Re-conceptualising Failure: Social Shaping Meets IS Research[END_REF].

Epistemologically, two approaches have emerged within this debate, the first of which attempts to isolate the factors that predict and/or permit success. This literature has developed normative descriptions of idealized development and implementtation processes, and proposes multiple tools and techniques to mitigate the risk of failure (DeLone andMcLean 1992, 2003). Research of this type suggests that methods can be found to identify, manage, and/or avoid potentially failure-inducing issues related to the organization, human participants, and the organizational culture in which the technology is to operate [START_REF] Mitev | Towards Social Constructivist Understandings of IS Success and Failure: Introducing a New Computerized Reservation System[END_REF]. Much of the existing forecasting literature falls within this category, where success is defined as the implementation and diffusion of the Arational ideal@ of the quantitative forecasting system.

Even the most cursory inspection of the academic literature on forecasting reveals a discipline deeply rooted in the science of statistics. The dominant research topic in this field is the development, elaboration, and testing of the technologies of fore-casting. This research has produced a set of statistical models and algorithms intended to extrapolate a description of the future from information about the past. The limited capacity of humans for this type of analysis has led to a strong interest in embedding these techniques within forecasting support systems [START_REF] Hogarth | Forecasting and Planning: An Evaluation[END_REF]. One of the central concerns of this work is the measurement of statistical accuracy, or the correspondence between the forecast and the actual data for a given period. Much of the forecasting literature assumes straightforwardly that the success of a forecasting process in practice is synonymous with and proportional to the statistical accuracy of the forecast that is produced, with one or two notable exceptions [START_REF] Lawrence | A Field Study of Sales Forecasting Accuracy and Processes[END_REF].

A strand of the forecasting literature has explicitly dealt with the problem of forecasting in organizations. This literature is generally highly sympathetic to the outcomes of those studies done in laboratories that suggest that the systematic application of forecasting techniques and technologies, combined with carefully controlled integration of humanBexpertise, produces the best, which is to say the most statistically accurate, forecasts [START_REF] Armstrong | Principles of Forecasting: A Handbook for Researchers and Practitioners[END_REF]. Legitimacy is expected to accrue to the forecasting support system and its outputs from the rigor of the underlying mathematics and the integrity of the flow of data to and from the system. The organization itself is broadly understood as a more or less hostile host for this technology. Success, therefore, depends in part on the willingness that the organization evinces to change to accommodate the needs of the new technology and to accord authority to the outputs of the new, more accurate system [START_REF] Moon | Conducting a Sales Forecasting Audit[END_REF].

The neutrality of the forecasting system is never called into question in this literature. Indeed, an unexamined teleology of forecasting practices is tacit in much of this work. These works envisage forecasting practices as moving toward greater accuracy, and thus greater success, through the gradual replacement of the human and judgmental with the systematic and mathematical. As a consequence of this, much of this literature is normative. It seeks to outline the organizational arrangements that best support the successful integration of this machinery of forecasting into the firm. For example, these models of Abest practice@ call for specific efforts to develop systems of communication and data gathering [START_REF] Fildes | The Organization and Improvement of Market Forecasting[END_REF]; suggest that specialist forecasters be employed to operate forecasting systems and be provided with a position in the organizational hierarchy that provides them with political capital [START_REF] Moon | Conducting a Sales Forecasting Audit[END_REF]; and demand the creation of a set of policies and rules in the organization that discourage and stigmatize unnecessary human intervention in forecast outputs [START_REF] Galbraith | The Politics of Forecasting: Managing the Truth[END_REF]. More critical viewpoints query whether the particular organizational Aimprovements@ that are proposed have ever been shown empirically proven to improve forecasts, let alone produce the better business decisions that are thought to flow from them [START_REF] Fildes | Researching Sales Forecasting Practice: Commentaries and Authors= Response on AConducting a Sales Forecasting Audit@ by[END_REF]. However, the notion of a need for improvements of some kind is largely unexamined.

One response to the problem of the inconveniently flawed organization has been to suggest that if organizations are unable or unwilling to mold themselves into good hosts for forecasting systems, the software should be used to impose good policy [START_REF] Fildes | The Design Features of Forecasting Support Systems and Their Effectiveness[END_REF]. At a minimum, for example, this ideal of rational forecasting practice requires interested non-forecasters to recognize significant limits to their expertise and to accord authority to the analytical systems that have replaced them. As human judgment Aadjustments@ are often used to modify statistical forecasts unscientifically and to the detriment of accuracy, it has been suggested that forecasting support systems limit and warn against such adjustments, or even Acorrect@ them as they are made [START_REF] Davydenko | Judgemental Adjustments to Demand Forecasts: Accuracy Evaluation and Bias Corrrection[END_REF].

This literature, therefore, positions quantitative forecasting methods, and the systems they are embedded within, as the rational choice for resolving the problem of predicting the future. Once implemented in firms, the focus shifts to defending these technologies from the distortions and subversions that arise out of the imperfections of the particular firm. It is assumed that the foolishness these imperfections create can and should be designed away, or at least mitigated, either through direct intervention in organizational design and/or policy or else through the design of the technology itself.

The Forecaster as Systems Expert

This description of the design and implementation of forecasting technologies is strongly reminiscent of Hirschheim and Klein=s (1989) description of Athe analyst as systems expert,@ with the same fundamental assumption that the primary concern of the forecaster is the means of production, rather than the end product itself. Forecasters, like Hirschheim and Klein=s information systems developers, are expected to concern themselves first and foremost with the task of choosing and applying techniques and models that produce authoritative, accurate forecasting outputs. The extraction of meaning from these forecasts is assumed to be the province of non-forecasters, usually sales and production employees who take decisions based on their interpretation of the information. Much of the frustration expressed in the forecasting literature concerns the vitiation of the methods of production of forecasts by non-forecasters and/or the reluctance of non-forecasters to cede authority for describing the future to the forecasting system. [START_REF] Kling | Social Analyses of Computing: Theoretical Perspectives in Recent Empirical Research[END_REF] describes analysis of this type as a Atraditional management-science approach,@ imagining how forecasting systems would work in an idealized world. Kling further suggests that it is often followed up by a Ahuman relations@ analysis of the same problem which encourages system designers to consider this problem of resistance productively. Kling describes this as a belief that a technical solution can be found that permits the needs of a number of organizational actors to be met, including both the managers requiring information and the various contributors to the system. This manifests itself in the forecasting literature in the various recommenddations on how to realize the perfect world of forecasting practice by reform of the organization.

2.3

The Analyst as Facilitator

An alternative perspective of the activities of forecasters within the firm, however, is one consistent with Hirschheim and Klein=s notion of the Aanalyst as facilitator.@ This attempts to understand the forecast not simply as the output of an objective information process that is strictly geared toward producing the forecast, but rather focuses on the method of this production as a meaningful activity in itself. This approach is useful because it allows us to understand differences between theory and practice as more than delinquency. Instead they can be understood as indicative of some meaningful need or desire of participants in the firm. This stance takes the less critical position that forecasting systems develop in an organization in a particular form because this provides the greatest utility to one or more organizational actors. Consequently, we are no longer constrained to treat organizational arrangements as either rational or foolish, but rather to explore and investigate them as the effects of particular organizational attitudes and processes. In this approach we leave it to organizational participants to determine who extracts meaning from forecasts and how they do so, and what measure of success might be applied to these activities. In particular, it suggests that the disinterested, objective measurement of statistical accuracy may be only one measure of success relevant to forecasters and forecast users. This position is consistent with a second thread of the information systems success/failure debate, which argues that normative and instrumental approaches to understanding the failure of information systems rely on a faulty assumption that technology is inherently neutral [START_REF] Mitev | Towards Social Constructivist Understandings of IS Success and Failure: Introducing a New Computerized Reservation System[END_REF]. The second type of research, by contrast, broadly identifies with constructivist schools of thought. Success or failure of information systems is understood in this view to be socially constituted. It is determined by the dominant narrative that emerges from organizational participants, irrespective of the extent to which the project conforms to checklists of success [START_REF] Wilson | Re-conceptualising Failure: Social Shaping Meets IS Research[END_REF]. This type of analysis, therefore, relies on investigating the relationship between value-laden technological change and patterns of interests and power within the firm. Recent examples include [START_REF] Brown | Doomed to Failure: Narratives of Inevitability and Conspiracy in a Failed IS Project[END_REF], who consider narratives of doom that emerged in a failed IS project at a UK hospital; [START_REF] Fincham | Narratives of Success and Failure in Systems Development[END_REF], who considers the emergence of different dominant success/failure narratives within two financial services firms; and [START_REF] Bartis | A Multiple Narrative Approach to Information Systems Failure: A Successful System That Failed[END_REF], who discussed the impact of managers Adisguising@ a failure as a success in order to save face or secure power in a case study firm.

In this paper, the intention is to apply these ideas to a single case study as an example of this approach. It aims to examine how rationality, so clear cut in the mathematical approaches to forecasting, is in fact contingent upon the firm and the socio-political processes that surround the initiation, processing, outcome, and interpretation of forecasts. In this view, behaviors and outcomes from a forecasting system, which might appear foolish under functionalist viewpoints, can be construed alternatively as rational. We are also able to explore how an established practice was recast from successful to failing by means of the interpolation of a technology controlled and promoted by a group with particular organizational power. Before describing this case in detail, however, the next section will briefly outline the methodology used to generate data about the firm in question.

Methodology

This investigation into the problem of forecasting practice sought to explore the experiences and behavior of forecasters within an organizational context. This study, therefore, took an interpretive case study approach [START_REF] Walsham | Interpretive Case Studies in IS: Nature and Method[END_REF]. The firm chosen for this case study was a large multinational manufacturing firm that produces alcoholic beverages. The firm was considered to be a useful example of forecasting practice as it has a relatively stable and well-documented forecasting process. Data was generated from 2008 to 2010 through a set of 15 semi-structured interviews with two forecast managers and two senior forecasters at the UK headquarters of the firm, as well as two non-forecasters: a supply manager and an inventory manager. Interviews were conducted primarily with a single interviewee, with one extended interview involving both forecasting managers, and typically lasted between one and one and a half hours. The interview guide consisted of a set of queries intended to elicit details about the day to day creation, revision, dissemination, and review of forecasts in the firm. Forecasters, for example, were asked to describe their routine interacttions with forecast inputs and outputs, forecast users and other data related to forecasts, as well as their use of the forecasting support system. Forecast managers were asked questions that related to these issues, and to issues surrounding the measurement and perception of forecasts and forecasters in the firm. All but one of the interviews was recorded, transcribed, and the transcripts, or notes in the case of the one unrecorded interview, were shared with the interviewees for further clarification and checking. Additionally, the organization supplied internal documents related to forecasting outcomes, processes, and hierarchies within the firm.

It is also useful to consider the role of the researcher in conducting this research. This case study forms part of ongoing research undertaken as part of my doctoral studies. Prior to undertaking this research I worked in a firm in a different industry that was nevertheless experiencing some similar challenges in terms of the implementation and use of forecasting techniques. In the course of interviews at the case study firm, I disclosed my previous work experience, and this revelation of my own history may have affected their description of practice in particular ways unknown to me, or to have influenced their choice of terminology or the topics, within the bounds of the semi-structured nature of the interviews, that they chose to discuss. As with all interpretive cases, I must note the contingent nature of this description, which is necessarily constructed in ways consistent with my understanding of the world, both tacit and explicit.

With these caveats, in the next section the forecasting practices of the case study firm, which will be called Global Beverages UK, will be described in detail, followed by analysis and discussion of the case in order to explore the issues raised in earlier sections of this paper.

4

Case Study

An Introduction to Global Beverages UK 1

Global Beverages UK is the British subsidiary of a global alcoholic beverage manufacturer and distributor. The parent organization, Global Beverages Worldwide, operates in most parts of the world where alcoholic beverages are consumed.

At the time of the study, the Global Beverages Worldwide parent company was divided for managerial purposes into several geographic groups known internally as business units, each of which had a regional headquarters site and employed a number of employees dedicated to certain centralized functions as well as senior managers responsible for the entire region.

Global Beverages UK was part of the European Business Unit (EBU), which had physical headquarters in mainland Europe and was responsible for operations throughout the European Union and Scandinavia, although the UK, France, and Germany were the largest markets. The UK market for Global Beverages= goods was fiercely competitive, made more so by a long-term decline in sales volumes and a gradual erosion of profit margins. In response to these trends, Global Beverages UK was focused on reducing costs to maintain profitability in shrinking sectors.

Historically, the managerial oversight provided by the EBU in national markets was fairly limited, with major markets like the UK permitted considerable control over their own operations. Over the period from about 2005 to 2010, however, a series of cost saving programs were initiated by supply chain managers at the EBU with the aim of eliminating or at least reducing duplication of activities between the various national organizations. These functions were in some cases consolidated into a multinational team based in the EBU headquarters or else, most recently, to a new service center based in a lower labor cost country in Eastern Europe. Although several related supply chain functions were affected by these changes, responsibility for demand planning had, for the time being, remained with the local Global Beverages organization. However, EBU supply chain managers were increasingly interested in forecasting outcomes and intervened regularly in processes, metrics, and systems related to forecasting. This included an EBU-initiated project to review and streamline forecasting in the UK under the aegis of a well-known management consultancy firm. A particularly critical element of these interventions was a series of redefinitions within the firm of the meaning of Asuccess@ as it related to both forecasting practice and forecasting outcomes.

Forecasting at Global Beverages UK

At the time of the study, forecasters in Global Beverages were split into two teams, each serving a distinct customer group which represented approximately half the total revenue of the firm. Each team consisted of a number of forecasters and a forecasting manager with overall responsibility for the forecasts and the team. The two customer segments were known as (1) the licensed trade and (2) the at-home or retail trade. These segments differed very significantly in both customer profile and their treatment by the firm for forecasting purposes.

The Licensed Trade

The licensed trade consisted of sales to business premises where customers consumed beverages on site. In the UK, this sector included a large pub, bar, and club trade, as well as licenses held by, for example, the operators of large sporting stadia. While there were some large accounts in the licensed trade, no single customer was felt to be critical to the on-going success of this side of the business.

The licensed trade was seasonal, with spikes and troughs in demand related to major sporting events (such as the football World Cup) and calendar events. However, there was little significant promotional activity in this segment, and much of the seasonal variation could be foreseen months ahead based on historical sales patterns. Moreover, a relatively small number of stock-keeping units (SKUs), at most two dozen, accounted for the vast majority of sales to all licensed trade customers nationwide, including promotional sales. These factors together produced a relatively stable and predictable demand pattern. From a forecasting perspective, this was seen as an ideal situation in which to use statistical forecasting techniques and the forecasters, therefore, employed a software package to produce forecasts. These were reviewed only by exception or when specific information was provided to them (for example, about a forthcoming promotion). Forecasters in this department consistently produced the most accurate forecasts of any in the EBU countries throughout the period of the study, and were considered to be the Abest practice@ forecasting department in the EBU and beyond.

4.2.2

The At-Home Trade

The at-home trade consisted of sales to premises where customers purchased beverages to consume at home. This was further divided, organizationally, into (1) wholesale accounts that purchased in bulk and then resold goods to smaller retail outlets and (2) multi-store retailers, notably three to four large and fiercely competitive national supermarket chains. This latter group was by far the most significant set of customers in the at-home trade side of the business. One retailer in particular, a very large multi-store grocer, was identified as business critical. Meeting the demand from this customer was, therefore, an organizational priority, even if doing so resulted in disappointing other customers.

At the total volume level (i.e., the total number of liters of product, however packaged), sales of most brands were reasonably predictable in this channel, with seasonal and event driven spikes and troughs that were not dissimilar to those observed in the licensed trade. However, at the level of the physical product, demand in the at-home trade was chaotic, with multiple packaging types producing hundreds of different SKUs, some of them customer and/or promotion specific. In addition, forecasters had to factor in several SKU-specific promotions every month, both major and minor, many agreed with retailers in the same month or even week that they occurred. The dynamics of the competitive multi-store grocer market made the outcome of these promotions particularly difficult to predict. At the SKU level, therefore, historical data was thought to provide little clue to future demand for particular package types and sizes. The department had consequently come to rely heavily on judgmental, which is to say humanBexpertise-based, methods of forecasting. The basis of forecasts for these products was a set of views collected from sales and marketing personnel about their sales and promotion expectations for the next several months.

The Global Beverages UK at-home team had the worst forecasting accuracy in the EBU throughout the period of the study, much worse than comparably sized at-home markets in France and Germany. This produced additional costs for manufacturing and supply planning departments, and occasionally led to difficult customer service situations when demand could not be met from Global Beverages= inventory. Historically, however, the at-home team were also understood to be highly successful. Despite their relatively poor forecasting accuracy, market conditions were such that tolerance for error was much greater, and the ability of forecasters to negotiate between the needs of the production departments and sales teams at the mercy of demanding retail customers was held in high esteem.

However, during the course of this study, the definition of what it meant to be a successful at-home forecaster at Global Beverages UK changed. Senior EBU supply chain managers were keen to improve forecasting accuracy to something closer to that achieved in France and Germany, if not to the level of the UK licensed trade segment. Additionally, the means of production of forecasts became more important. Part of a review of the UK forecasting process in 2010 was intended to determine how to implement the statistical forecasting techniques in the at-home trade, despite previous failures at this task and the of both the forecasting managers and UK sales managers.

Change at Global Beverages

During the course of the study at Global Beverages, the EBU stepped up the pace of a long-standing project of integration and harmonization of supply chain processes across the member countries. The forecasting function was affected by multiple rounds of reform over the course of the study. In 2008, the FSS that the licensed trade team had used for many years was abandoned in favor of a single software platform, SAP APO. This was to be used by all forecasters in EBU countries and integrated with the enterprise resource planning software already in use in production departments, although by 2010 only the UK had completed the transition. In 2010, a major consulting project undertaken at the behest of supply chain managers at the EBU examined forecasting processes in several of the major markets. This project determined that too few products were forecast using statistical techniques in the UK. This latter project coincided with the departure from the firm of the at-home forecasting manager and one further forecaster, who were made redundant in a related cost-saving program. This removed a major obstacle to statistical forecasting in the at-home division. The forecasting manager had been vehement in his rejection of these methods for his department and had previously worked with the licensed premises forecasting manager and senior sales managers in the UK to preserve the status quo. These reforms produced little change for forecasters in the licensed premises team. However, forecasters in the at-home market side of the business were told that henceforth a majority of forecasts were to be completed first in the FSS, which used statistical models, and then adjusted for managerial information such as promotions. The aim was, therefore, to move away from a situation in which human experts forecast half the revenue and more than 80 percent of all SKUs qualitatively, to a new regime in which no more than 20 to 25 percent of SKUs would be forecast manually and the remainder would be produced statistically. The level of accuracy that was acceptable was also reset at a significantly higher level.

Forecasters were skeptical about the change in methods and reluctant to abandon previous ways of working in the at-home segment. It was argued that because of the volatility created by promotional activities, most SKUs could not be forecast with any more success using statistical methods than they had been using human judgment, and in many cases these forecasts were actually worse than the forecasts produced using judgment. However, as new measures introduced by the EBU now reviewed not only the accuracy of forecasts, but also the way in which they were produced, forecasters had no option but to acquiesce. In the short-term, forecasters were committed to a course of action that involved producing both judgmental and system forecasts and choosing whichever seemed more plausible given sales histories. Although forecasters as required, now disseminating forecasts from within the mandated software, a line in the forecasting software had been enabled that allowed forecasters to overwrite the Asystem forecast@ with a Amanual@ alternative, which they produced judgmentally in the same manner they had always done.

Discussion

The striking thing about the Global Beverages UK example was that there were two forecasting practices operational within the same firm that used diametrically opposed forecasting techniques, and which experienced wildly different accuracy outcomes.

It is even more remarkable that despite the disparity in the accuracy of outputs, managers in these teams saw no contradiction in the coexistence of these practices. It was not until new narratives, backed by the organizational power of the regional headquarters, began to emerge about what constituted successful, legitimate forecasting processes that this status quo was called into question.

The Functionalist Perspective on Global Beverages

Forecasters throughout the organization described themselves as being squeezed between cost-minimizing supply chain managers and revenue-maximizing sales directors, their role one of go-between, translator, and whipping boy all at once. Forecasters in both departments thought of their role as providing a neutral middle ground between these two sets of interests, with one forecasting manager remarking that he thought only forecasters had any sense of the organization=s over-arching desire for profit maximization, rather than one or another of the components of this goal. This is consistent with many of the descriptions in the functionalist literature that emphasizes the importance of objectivity. This functionalist position appeared to triumph in Global Beverages, as EBU managers mandated the harmonization of forecasting practices, arguing that the reasons provided by the at-home forecasters for their deviation from these methods were no longer sufficient to explain the failure to use statistical techniques. From the forecasting research perspective, this change at Global Beverages represents a natural, rational evolution of forecasting practice toward a desirable end. The decision of forecasters to circumvent the system in the early stages of deployment appears both baffling and foolish.

A Facilitative Interpretation of Global Beverages

Examining this situation from a different perspective, however, it is useful to consider how information technologies in use in the two forecasting practices reflect a perception of rational choice within the department, irrespective of the dysfunction this may have created in outputs.

In the licensed premises segment, demand was relatively stable, predictable, and involved a relatively small number of products. There were many low-volume customers, and a combination of the market strategy these customers pursued and national regulations on the sale of alcohol inhibited promotions. There were additionally some barriers for customers who wanted to switch between vendors in the licensed premises trade that further discouraged volatility. Relationships with customers were consequently relatively long-term and slow to change. Although the sector was still competitive, forecasting in this segment of the market was relatively undemanding. Forecasters described the data sets as regular and predictable, and the decision to use quantitative techniques was described as has having followed the determination that the data set supported their use.

Even in this department, with a pattern of respectable, technical forecasting, forecasters were passionate about the development of credible forecasts, and about the importance of personal relationships with contributors to forecasts, forecast users, and even with the data itself in producing credible forecasts. Despite their emphasis on the importance of their role as the neutral information broker between supply chain and sales, in this department, forecasters viewed their role as more strongly oriented toward the needs of the production department, and therefore closely aligned with the cost-minimizing inventory, efficiency, and planning goals of manufacturing managers.

In the at-home trade, by contrast, the scenario with regard to customer relationships was much more complex. A small number of customers exerted enormous influence over the visibility and availability of Global Beverages= products to end consumers. Switching costs for the retailer were relatively low, particularly since there were two or three highly competitive firms offering similar and, it was felt, increasingly commoditized products in most categories. The retailers, moreover, were themselves thought to be positioning their resources to be highly responsive to the end-consumers they served. They demanded a supply relationship that would permit rapid responses to small changes in demand arising from weather changes, competitive dynamics, and the like.

Against this background of an extremely dynamic customer base who perceived their needs to change on a weekly, if not daily, basis, sales people working in Global Beverages were equally active and responsive. The comfortable certainty of business in the licensed trade sector was absent, and instead sales people were described as under constant pressure to maintain and increase sales to a small number of demanding and capricious customers. There was a sense among forecasters that failure to meet those demands would result in not only the loss of that volume to a competitor, but also a damaging black mark against the business that would result in the loss of future sales. Forecasters, therefore, understood their role as sales focused and revenue-maximizing, rather than cost-minimizing. The perceived chaotic nature of the historical data had resulted in disinclination toward quantitative techniques. Perhaps more importantly, however, the sense that individual sales people, or at least the customers they represented, could make or break the revenue expectations of the division resulted in a significant reliance on their qualitative expertise. The appeal of the objective measure of accuracy was much lower than more subjective measurements of customer satisfaction and willingness to purchase.

In this customer-led environment, therefore, formal statistical methods were understood as an intrusion upon the agency and importance of the salesperson and his or her people skills. Consequently, the forecaster had become a collector rather than a producer of information, a historian of sales information. The authority of the forecast derived from the ability of the forecaster to render many narratives about the future into a single, credible narrative consistent with the past.

The Impact of Disruptions to Practice

The position taken by the forecasters, therefore, that the separation of their function into two distinct pieces was adapted to the needs of the organization was then disrupted by the change in the definition of successful forecasting that occurred. The investigations of the consultancy firm into forecasting at Global Beverages UK produced, without any particular investigation of the data set, the recommendation that the firm should achieve cost savings by forecasting more SKUs using quantitative methods within an FSS. It was too early at the conclusion of the research project to determine the accuracy of this statement, although forecasters at the firm initially claimed that it was not the case. However, it is interesting to consider the motivation of EBU managers in mandating this change.

It seems unlikely that an ideological commitment to statistical forecasting was strongly felt among supply chain managers at the EBU. A forecasting manager noted instead that the drive toward quantitative forecasting appeared to arise at least partly from a desire for systems integration among member countries. More cynically, the forecasting manager also expressed a belief that that a revolution in forecasting practice that forced the at-home practice onto the same technical footing as other groups would permit further cost savings in future. In particular, the manager pointed to the changes in other supply chain functions, where activities were first rationalized, then moved on to a common platform, and then finally moved to a service center in a lower labor cost country in Eastern Europe as an example of how these cost savings might be achieved in later years.

EBU supply chain managers, therefore, seem to have taken the position that expertise in forecasting ought primarily to be of a technical nature, de-emphasizing the idea of the forecaster as a neutral go-between. This position assumed also that the forecast would have a claim to authority and validity as a result of the system from which it originated, a system that EBU managers now controlled. This was in sharp contrast to the expressed belief of all the forecasters that the credibility of their forecasts depended in part upon the long-term relationships they had built with users and the data. The forecasting literature would regard this change in practice as neutral, part of the natural evolution of forecasting processes. However, in Global Beverages, this change was far from neutral; it represented a significant shift in the relative power of the forecasters and the EBU supply chain managers at regional headquarters.

A further demonstration of this issue was observed when EBU managers began to question the role promotions played in the department, challenging the perception that the UK had special market conditions that resulted in the use of promotions. Instead, UK managers were asked whether the use of promotions had created the market conditions they faced. It was suggested that customers could be Aretrained@ to expect fewer promotions and a more favorable trading environment for Global Beverages. The revenue-maximizing rationale of the sales department is entirely absent from this discourse: EBU managers were in effect asking Global Beverages UK sales people to conduct business in a way that made forecasting easier, and therefore reduced costs.

If forecasters under the original regime felt themselves to be squeezed between the complementary rationales of revenue-maximization and cost-minimization before, these reforms imposed upon them by EBU substantially increased the pressure. In the early stages of the implementation, it is hard to say what equilibrium will eventually be reached. However, even as a classic rational, technical forecasting package was apparently implemented in the at-home trade department, there were unintended consequences: qualitative forecasts were now written into a line in the technical forecast, taken from an unregulated set of spreadsheets put together by forecasters; and sales managers had taken steps to shelter forecasters within their own departments, with unknown consequences.

Reflecting back on the forecasting literature, it is easy to understand the frustration of rationalist expert forecasters confronted with this determined delinquency from the rational course of action. Here, the firm has taken one of the necessary steps to reform forecasting practices only to experience resistance and subversion of the new system. The perspective of the forecaster-as-facilitator, however, makes sense of some of these apparently foolish behaviors. What has been rendered in the forecasting literature as resistance to the technology occasioning from ignorance, self-interest, or stubbornness can be understood from this perspective as arising instead from the disruption of a finely balanced equilibrium of interests. The forecasting support system intrudes upon the forecaster=s position as mediator between the cost minimizers and revenue maximizers, and upon the salesperson=s agency and expertise. It attempts to establish the credibility of forecasts as being obtained through the means of their production, rather than from the process of collecting, sharing, and making sense of this information. Although neither practice is entirely functional, it is clear that at least within the organization what forecasting experts might code as folly appears rational.

Conclusions and Future Research

The problem of practice in the forecasting literature has typically been presented as a failure by firms to diffuse the technologies of forecasting in a way forecasting experts have deemed adequate. This paper examined forecasting practice from a more social and political perspective, using the example of Global Beverages UK in order to explore how the practices dismissed as foolish by the rationalist approach persist in firms. This discussion of two different forecasting practices within the same firm found that, in each case, forecasters had developed a practice that most effectively mediated between pressures to minimize cost and to maximize revenue in markets of different levels of uncertainty. When a topBdown process of reform, intended to diffuse forecasting technologies more widely, was implemented, it produced a conflict between the forecaster=s sense of the role salespeople and forecasters played in forecasting processes, and the paradigm of the uninvolved technical forecaster. These conflicts play out in the organization as resistance to and subversion of the rational forecasting support system, but are indicative of the balance that has been struck between rational interests that participants see no alternative but to preserve. A paper of this length provides little scope to explore further some of the questions raised by this case study. This description of forecasting in a firm raises further questions about the role of information systems in creating and legitimating a view of the future. In Global Beverages, different levels of uncertainty produced various degrees of reliance on human judgment, and the question of how uncertainty affects the use of forecasting support systems bears further investigation. Finally, this is just one case study, and while useful as a description of the conditions that can affect firms, further exploration of this notion of alternative rationalities as they affect forecasting practice in other firms would no doubt be enlightening.

Names and some minor identifying details have been changed to preserve the anonymity of participants.

About the Author


Iordan Iordanov

Monique Teillaud

Implementing Delaunay Triangulations of the Bolza Surface

Keywords: 1998 ACM Subject Classification I.3.5 Computational Geometry and Object Modeling hyperbolic surface, Fuchsian group, arithmetic issues, Dehn's algorithm, cgal

The cgal library offers software packages to compute Delaunay triangulations of the (flat) torus of genus one in two and three dimensions. To the best of our knowledge, there is no available software for the simplest possible extension, i.e., the Bolza surface, a hyperbolic manifold homeomorphic to a torus of genus two.

. We describe the representation of the triangulation, we detail the different steps of the algorithm, we study predicates, and report experimental results.

Introduction

Motivated by applications in various fields, some packages to compute periodic Delaunay triangulations in the Euclidean spaces E 2 and E 3 have been introduced in the cgal library [START_REF] Caroli | 3D periodic triangulations[END_REF][START_REF] Kruithof | 2D periodic triangulations[END_REF] and have attracted a number of users. To the best of our knowledge, no software is available to compute periodic triangulations in a hyperbolic space. This would be a natural extension: periodic triangulations in E 2 can be seen as triangulations of the two-dimensional (flat) torus of genus one; similarly, periodic triangulations in the hyperbolic plane H 2 can be seen as triangulations of hyperbolic surfaces. The Bolza surface is a hyperbolic surface with the simplest possible topology, as it is homeomorphic to a genus-two torus. First steps in computing Delaunay triangulations of hyperbolic surfaces have recently been made [START_REF] Bogdanov | Delaunay triangulations on orientable surfaces of low genus[END_REF]. Due to lack of space, we refer the reader to that paper for examples of applications. All previous work mentioned above is generalizing the well-known incremental algorithm introduced by Bowyer [START_REF] Bowyer | Computing Dirichlet tessellations[END_REF], which has proved to be reasonably easy to implement and very efficient in practice. For each new point p, the set of conflicting simplices, i.e., simplices whose circumscribing ball contains p, are removed; then their union is triangulated by simply filling it with new simplices with apex p. This simple update operation relies on the fact that the union of conflicting simplices is always a topological ball. As proved earlier [START_REF] Bogdanov | Delaunay triangulations on orientable surfaces of low genus[END_REF], for an input set S on a closed hyperbolic surface M , this property is ensured as soon as sys(M ) > 2δ S , [START_REF] Balazs | Chaos on the pseudosphere[END_REF] where sys(M ) denotes the systole of M , i.e., the length of a shortest non-contractible loop on M , and δ S denotes the diameter of the largest disks that do not contain any point of S

44:2

Implementing Delaunay Triangulations of the Bolza Surface in their interior. This condition ensures that there is no cycle of length one or two in the 1-skeleton of the Delaunay triangulation. Two ideas have been proposed to fulfill this condition [START_REF] Bogdanov | Delaunay triangulations on orientable surfaces of low genus[END_REF]. The first one consists in increasing the systole by using covering spaces of M , but it was shown to require at least 32 sheets for the Bolza surface, so this does not lead to a practical method. A more practical idea was quickly sketched in the last section of the same paper; it consists in initializing the triangulation with a set of "dummy" vertices that ensure that largest empty disks are small enough so that inequality (1) holds. As the diameter of largest empty disks cannot increase when new points are inserted, the condition will still be fulfilled when inserting points. If sufficiently many reasonably well-distributed points are inserted, then the dummy vertices can be removed from the triangulation without violating condition [START_REF] Balazs | Chaos on the pseudosphere[END_REF]. In this paper, we elaborate on this approach and propose a first implementation.

We recall some background for the Bolza surface in Section 2. In Section 3 we propose a representation for Delaunay triangulations of the Bolza surface. Then we present the various steps of the construction in Section 4. We investigate the algebraic complexity of the algorithm in Section 5. Finally, we present some results of our implementation.

The source code, all Maple sheets, and the appendix are publicly available at https://members.loria.fr/Monique.Teillaud/DT_Bolza_SoCG17/.

The software package will be submitted for integration in cgal as soon as the documentation is completed.

The Bolza surface

Details and references for the background given in this section can be found in [START_REF] Bogdanov | Delaunay triangulations on orientable surfaces of low genus[END_REF].

As the Poincaré disk model of the hyperbolic plane H 2 is conformal, it is often used in applications. The hyperbolic plane is represented as the open unit disk B of the Euclidean plane E 2 . The boundary of B represents the set of points at infinity, denoted as H ∞ . Hyperbolic lines, or geodesics, are represented as diameters of B or as arcs of circles orthogonal to H ∞ . A hyperbolic circle is represented as a Euclidean circle contained in B and its hyperbolic center is the limit point of the pencil of circles that it generates with H ∞ .

We denote the group of orientation-preserving isometries on H 2 as Isom + (H 2 ). By identifying E 2 with the complex plane C, each g ∈ Isom + (H 2 ) is a mapping in the form

g(z) = αz+β βz+α , z ∈ C with matrix g = α β β α
, where α, β ∈ C and |α| 2 -|β| 2 = 1. We are only interested here in one type of orientation-preserving isometries: the hyperbolic isometries, also called translations. A hyperbolic translation fixes two points at infinity and no point inside B. The geodesic X g through the two fixed points of a translation g is called the axis of g. Points lying on X g are all translated along X g by the same fixed distance (g) called the translation length. The length can be computed from the matrix as (g) = 2 • arcosh 1 2 Tr(g) , where Tr(g) denotes the trace of the matrix of g. A point that does not lie on X g is translated by a distance greater than (g) along a curve equidistant from X g (of course the distance between a point and its image is measured on the geodesic containing them). See Figure 1-Left.

A hyperbolic surface is a connected 2-dimensional manifold such that every point has a neighborhood isometric to a disk of H 2 . A closed (i.e., compact) and orientable hyperbolic surface is isometric to a quotient of H 2 under the action of a Fuchsian group Γ (i.e., a discrete subgroup of Isom + (H 2 )) that contains only translations (and the identity). The Bolza surface is the simplest possible closed orientable hyperbolic surface. Consider the 1 For simplicity, we also denote as g the image gO of the origin by a translation g of G.

The Bolza surface is defined as the quotient of H2 under the action of the group G:

M = H 2 /G.
The projection map Π : The fact that G is non-Abelian leads to interesting difficulties. Among other properties, the Dirichlet regions D p (G) and D q (G) of two different points p and q do not always have the same combinatorics. The set of points GO is quite degenerate: all vertices of VD H (GO) have degree eight. See Figure 2-Left. The octagon D O is in fact the Dirichlet region D O (G) of the origin. Figure 2-Right illustrates notation that will be used throughout this paper: the vertices of D O are denoted as V 0 , . . . , V 7 and their associated Delaunay circles are denoted as C 0 , . . . , C k .

H 2 → M = H 2 /G
Each Dirichlet region D p (G) is a fundamental domain for the action of G on H 2 , i.e., (i) D p (G) contains at least one point of the preimage by Π of any point of M, and (ii) if it contains more than one point of the same preimage, then all these points lie on its boundary.

The group G has the following finite presentation: The matrices of the elements g k , k = 0, 1, . . . , 7, are

G = a, b, c, d | abcdabcd ,
C 0 O V 0 V 1 V 2 V 3 V 4 V 5 V 6 V 7 M 0 M 1 M 2 M 3 M 4 M 5 M 6
g k = ξ 2 e ikπ/4 √ 2 ξ e -ikπ/4 √ 2 ξ ξ 2 , where ξ = 1 + √ 2. ( 2
)
The translations g k all have the same length, which is the systole of M:

sys(M) = (g k ) = 2 • arcosh 1 + √ 2 ≈ 3.05714, k = 0, 1, . . . , 7.

Representation of the triangulation

As mentioned in the introduction, the use of dummy points allows us to always assume that the set P of input points satisfies inequality [START_REF] Balazs | Chaos on the pseudosphere[END_REF] for the Bolza surface M. We introduce the original domain D ⊂ D O for M, which contains exactly one point of the fiber under Π of each point on the surface M. See Figure 2-Right: D consists of the interior of D O , its four "solid" sides, and one vertex of the octagon (chosen to be V 0 ). 2We can consider that all points of P lie in D. Similarly, we will now define a unique representative of each face of the Delaunay triangulation DT M (P) of M defined by P.

Canonical representative of a face

The definition of the canonical representative of a face will rely on Theorem 2, which is reminiscent of the result proved for the flat torus by Dolbilin and Huson [START_REF] Dolbilin | Periodic Delone tilings[END_REF] and recalled in [START_REF] Caroli | Delaunay triangulations of closed Euclidean dorbifolds[END_REF]Lemma 6.3].

We denote the hyperbolic distance between two points p and q in H 2 as dist H (p, q) and the (hyperbolic) segment with endpoints p and q as [p, q]. Let us recall our abuse of notation: g denotes both a translation and the point gO. The points M k , k = 0, . . . , 7 visible on Figure 2-Right are defined as the midpoints of V k and V k+1 (indices are meant modulo 8).

Let U D be the union of the disks bounded by the circles C k , k = 0, 1, . . . , 7, and let C D be the boundary of U D . See Figure 3

-Left. O C k C D g k 1 2 sys (M) O M k g k V k p B k π 8

Lemma 1. The distance between C D and ∂D

O is equal to dist H (M k , g k ) = 1 2 sys (M), k = 0, 1, . . . , 7.
Proof. Using symmetries, we get (see Figure 3

-Right): dist H (C D , ∂D O ) = min p∈[V k ,M k ], q∈C k ∩C D dist H (p, q) .
The hyperbolic circle B k centered at M k and passing through O also contains the points Proof. Let σ be a face in DT H (GP) with at least one vertex in D O . By definition of δ P , the circumscribing disk of σ has diameter smaller than δ P , which is smaller than 1 2 sys (M) by inequality [START_REF] Balazs | Chaos on the pseudosphere[END_REF]. Lemma 1 allows us to conclude that this disk is contained in U D .

V k , g k and V k+1 : indeed, by definition of the Dirichlet region of O, segment [V k , V k+1 ] lies on the bisecting line of O and g k , moreover [O, g k ] lies on the bisecting line of V k and V k+1 ; in addition, dist H (M k , V k ) = dist H (O, M k )
V k , M k ] is a radius of B k , so for any point q ∈ C k ∩ C D and for any p ∈ [M k , V k ], dist H (p, B k ) ≤ dist H (p, q). Equality is attained when q = g k , so: dist H (C D , ∂D O ) = min p∈[V k ,M k ] dist H (p, g k ) . For every point p ∈ [V k , M k ], dist H (g k , p) ≥ dist H (g k , M k ) because the angle g k M k p is
d ā¯bc d ā¯b d ā O K E k+1 K E k K E k-1 K E k-2 O κ k γ ω k C k ρ l k V k V k+2 V k-2
We will now prove that

U D is contained in D N , by proving that each circle C k , for k ∈ {0, 1, . . . , 7} is contained in D N . A circle C k is centered at the Voronoi vertex V k ; it
passes through the origin O and its images under the action of seven consecutive elements of N . Rotating C k around V k by π/4 maps each of these eight points (and its Voronoi region) to the next one along C k . This rotational symmetry shows that in order to prove that C k ⊂ D N , it is enough to prove that C k intersects only the two sides of D O that are incident to its hyperbolic center V k .

Indices below are again taken modulo eight, e.g., we write

V k+1 instead of V k+1 mod 8 . Let us first show that C k intersects the sides [V k-1 , V k ] and [V k , V k+1 ] of D O . Consider a hyperbolic triangle (O, V k , V k+1 ).
Its angle at O is π/4, while the angles at the vertices V k and V k+1 are π/8. From the Hyperbolic law of sines, 3 we conclude that the length of

[V k , V k+1 ] is larger than the length of [O, V k ]. The result follows, since the segment [O, V k ] is a radius of C k . Consider now the line segment l k = [V k-2 , V k+2 ], k = 0,

Quantity Notation Expression Approximation

radius of K E j γ √ 2-1 2 0.4551 center of K E j κj e ijπ/4 √ 2+1 2 - radius of C k ρ (2 - √ 2)( √ 2 -1) 0.4926 center of C k ω k e i(2k+7)π/8 3 √ 2 -4 - Figure 5
Examples of faces of DT H (GP) with one, two and three vertices in D, that project to the same face on M. Their respective vertices drawn as a dot project to the same vertex on M (same for cross and square). The canonical representative is the shaded face. Let P ⊂ D be a set of points satisfying inequality (1) for M. The rest of this section is dedicated to the choice of a unique canonical representative σ c in DT H (GP) for each face σ in DT M (P).

dist E C k , K E k+1 = dist E (ω k , κ k+1 ) -ρ -γ. Maple calculations yield: dist E C k , K E k+1 = √ √ 2-1 2 3 √ 2 - √ 2 4 -2 √ 2 -1 . The last factor is positive: 3 √ 2 -1 2 = 19 -6 √ 2, √ 2 4 -2 √ 2 2 = 8 -4 √ 2,
Let σ be a face in DT M (P). By definition of D, each vertex of σ has a unique preimage by Π in D, so, the set

Σ = σ ∈ Π -1 (σ) | σ has at least one vertex in D (3)
contains at most three faces. See Figure 5. When Σ contains only one face, then this face is completely included in D, and we naturally choose it to be σ c . Let us now assume that Σ contains two or three faces. From Theorem 2, each face

σ ∈ Σ is contained in D N . So, for each vertex v of σ, there is a unique translation ν(v, σ) in N ∪ {1} such that v lies in ν(v, σ)D.
We consider all faces in DT H (GP) oriented counterclockwise. For σ ∈ Σ, we denote as v first_out σ the first vertex of σ (in the counterclockwise order) that is not lying in D. Using the indexing on N defined above, we can now choose σ c as the face of Σ whose first vertex lying outside D is "closest" to the region abcdD in the counterclockwise order around O:

S
c ∈ Σ such that index N (ν(v first_out σ c , σ c )) = min σ∈Σ index N (ν(v first_out σ , σ)).

Data structure in CGAL

General two-dimensional triangulation data structures in cgal store the vertices and faces of the triangulation. Each vertex stores a point and a pointer to one of its incident faces. Each face stores three pointers to its vertices v 0 , v 1 , and v 2 , as well as three pointers to its three adjacent faces. Edges are not explicitly stored.

As mentioned above, we can assume that all input points of P lie in D. We adapt the cgal structure to store a triangulation of the Bolza surface. Each vertex v of DT M (P) represents an orbit under the action of G; it stores the point of Π -1 (v) that belongs to D. Faces of DT M (P) are stored through their canonical representative in DT H (GP). Concretely, in addition to the pointers to vertices and neighbors, each face σ c stores the three translations ν(v i , σ c ) ∈ N , i = 0, 1, 2 defined at the end of Section 3.1. In this way, for a given face σ c in the structure, the corresponding canonical representative is the triangle in H 2 whose vertices are the images by ν(v i , σ c ) of the point in D stored in v i for i = 0, 1, 2. The translations ν(v i , σ c ) play a similar role as the so-called "offsets" of the cgal Euclidean periodic triangulations.

We choose to represent translations in the faces of the triangulation data structure as words. This is detailed below.

Translations as words.

We consider the cyclical sequence A formed by generators of G (see Section 2) as an alphabet, and we denote the set of words on A as A * . Each translation g in G can be seen as a word in A * , also denoted as g. For two translations g ∈ G, the composition (or multiplication) gg corresponds to the concatenation of the two words g and g . Recall that composition is not commutative. We have seen in the two previous sections that we only need to store translations in N . Let us note here that N is closed under inversion, but not under composition.

The finite presentation of G captures the fact that a translation g ∈ G does not have a unique representation in terms of the generators (see Section 2). To obtain a unique representation of the translations that are involved in our algorithm, we slightly modify Dehn's algorithm. Dehn's algorithm solves the word problem (i.e., the problem of deciding whether a given word on the generators of a group is equal to the group identity) in the case of fundamental groups of closed orientable surfaces of genus at least 2 [START_REF] Dehn | Transformation der Kurven auf zweiseitigen Flächen[END_REF][START_REF] Greendlinger | Dehn's algorithm for the word problem[END_REF]. 4Let us present our implementation, tailored to our specific case. We encode each element g k , k = 0, 1, . . . , 7 of A as its index k. By concatenation, each word of A * is encoded as a sequence of integers.

Let w be a non-trivial word in A * . The first step of the reduction consists in freely reducing w, i.e., removing all sub-words of the form gg or gg for g ∈ A. With our encoding, two elements g i and g j of A are inverses in G if i = (j + 4) mod 8.

The relation R G = abcdabcd is encoded as 05274163. Let us note that any cyclical permutation of R G or of its inverse R G is equal to 1 in G. This can be viewed in another way by considering R ∞ G , the infinite word formed by infinitely many concatenations of R G : In our implementation, to find the sub-word w µ , we use the fact that a sequence of letters (g kj ) j=0,1,...,n , g kj ∈ A, is a sub-word of R ∞ G of length n if, for every j from 0 to n -1, k j+1 = (k j + 5) mod 8. Similarly, (g kj ) is a sub-word of R ∞ G of length n if for every j from 0 to n -1, k j+1 = (k j -5) mod 8. It holds that |R| < 2 |w|, so all words in A * with length less than 2 |w| can be listed in order to find such a word R.

any subsequence R of R ∞ G or R ∞ G with |R| = |R G | is a relation in G, i.
The two steps are repeated until w = 1 or until w cannot be further reduced. In the original algorithm by Dehn, words of length |R G | /2 are not reduced. In order to have a unique representations of words of length four, we introduce a small modification to the algorithm: whenever we get an irreducible word w with |w| = 4, we check whether w is a sub-word of R ∞ G . If so, we return w; in all other cases, we return w. Dehn's algorithm terminates in a finite number of steps and its time complexity is polynomial in the length of the input word. Note that we reduce words that are formed by the concatenation of two or three words in N ; this will become clear in Section 4.2. Since the longest word in N has four letters, the longest words that we reduce have length 12.

Constructing the triangulation

Let us now describe the steps of our implementation of the incremental algorithm that was quickly recalled in the introduction.

Initialization

The set Q of 14 dummy points proposed in [2, Section 4.2] is as follows: the origin O; the eight midpoints P k of the hyperbolic segments [O, V k ], k = 0, 1, . . . 7; the midpoints M k , k = 4, 5, 6, 7 of the closed sides of D; the vertex V 0 of D. The canonical representatives of the 32 faces forming the Delaunay triangulation of Q are shown in Figure 6-Left. They can be constructed in four iterations (i = 0, 1, 2, 3) by using the numbering shown in Figure 6-Right (but faces are not numbered in the code).

The coordinates of the dummy points are algebraic numbers, as reported in Table 2. They have been computed using Maple. These exact coordinates would increase the algebraic degree of the predicates (studied in Section 5) in an artificial way; therefore, we introduce a set Q of rational approximations of the points in Q. See the third column of Table 2. We have verified that DT M (Q) and DT M (Q ) have identical combinatorial structures. We initialize the triangulation as DT M (Q ).5

Finding faces in conflict with a new point

Let p ∈ P ⊂ D be a new point to be inserted in the Delaunay triangulation. Consider σ a face in DT M (P), and the set Σ defined in [START_REF] Bowyer | Computing Dirichlet tessellations[END_REF]. We say that σ c is in conflict with the input point p if there exists a face σ ∈ Σ whose circumscribing disk contains p.

V 0 i + 4 i i + 12 2 ( i + 1 2 ) 2( i + 8) i + 8 2 (i + 8 ) + 1 2 (i + 1 2 ) + 1 0 1 2 3 4 5 6 7 V 6 V 7 M 4 M 5 M 6 M 7 P 0 P 1 P 2 P 3 P 4 P 5 P 6 P 7 O O P i P i+1 g i M i+4 M i+4 P i+4 P i+5 g i P i+5 g i P i+4 V i V i+1 V 1 V 2 V 3 V 4 V 5 V i+4 V i+5
Recall that, since hyperbolic circles are Euclidean circles, a Delaunay triangulation in H 2 has exactly the same combinatorics as the Euclidean Delaunay triangulation of the same points. Consequently, the Euclidean Delaunay triangle containing p gives us a hyperbolic Delaunay face in conflict with p; the Euclidean and hyperbolic faces will both be denoted as σ p , which should not introduce any confusion. To find this triangle, we adapt the so-called visibility walk [START_REF] Devillers | Walking in a triangulation[END_REF]. This walk starts from an arbitrary face, then, for each visited face, it visits one of its neighbors, until a face containing p is found. Before specifying how the neighbor to be visited is specified in the case of the Bolza surface, we introduce the notion of neighbor translation.

Definition 4 (Neighbor translation). Let σ, τ be two adjacent faces in DT M (P) and σ, τ two of their preimages by Π in DT H (GP). We define the neighbor translation ν nbr (σ, τ ) from σ to τ as the translation of G such that ν nbr (σ, τ ) τ is adjacent to σ in DT H (GP).

Let v be a vertex common to σ and τ , and let v σ and v τ the vertices of σ and τ that project on v by Π. We can compute the neighbor translation from σ to τ as

ν nbr (σ, τ ) = ν(v τ , τ ) ν(v σ , σ).
(σ, τ ) = ν(v, τ ) ν(v, σ) = ν(v, σ) ν(v, τ ) = ν nbr (τ, σ).
We define the location translation ν loc as follows: let σ p be the Euclidean Delaunay triangle containing p. ν loc is the translation that moves σ c p to σ p . The location procedure starts from a face incident to O. Then, for each visited face σ of DT H (GP), we consider the Euclidean edge e defined by two of the vertices of σ. With a simple orientation test, we can check whether the Euclidean line supporting e separates p from the vertex of σ opposite to e. If this is the case, the next visited face is the neighbor τ of σ through e, and we repeat the process, until

Point Expression

Rational approximation

V0 2 3/4 √ 2+ √ 2 4 , - 2 3/4 √ 2- √ 2 4
(97/125, -26/81)

M4 - √ 2 -1, 0 (-9/14, 0) M5 - √ 2 √ √ 2-1 2 , - √ 2 √ √ 2-1 2 (-5/11, -5/11) M6 0, - √ 2 -1 (0, -9/14) M7 √ 2 √ √ 2-1 2 , - √ 2 √ √ 2-1 2
(5/11, -5/11)

P0 2 1/4 √ 2+ √ 2 2 √ 2+2 √ 2- √ 2 , - 2 1/4 √ 2- √ 2 2 √ 2+2 √ 2- √ 2 (1/2, -4/19) P1 2 3/4 √ 2+ √ 2+ √ 2- √ 2 4 √ 2+4 √ 2- √ 2 , 2 3/4 √ 2+ √ 2- √ 2- √ 2 4 √ 2+4 √ 2- √ 2 (1/2, 4/19) P2 2 1/4 √ 2- √ 2 2 √ 2+2 √ 2- √ 2 , 2 1/4 √ 2+ √ 2 2 √ 2+2 √ 2- √ 2 (4/19, 1/2) P3 2 3/4 √ 2- √ 2- √ 2+ √ 2 4 √ 2+4 √ 2- √ 2 , 2 3/4 √ 2+ √ 2+ √ 2- √ 2 4 √ 2+4 √ 2- √ 2 (-4/19, 1/2) P4 - 2 1/4 √ 2+ √ 2 2 √ 2+2 √ 2- √ 2 , 2 1/4 √ 2- √ 2 2 √ 2+2 √ 2- √ 2 (-1/2, 4/19) P5 - 2 3/4 √ 2+ √ 2+ √ 2- √ 2 4 √ 2+4 √ 2- √ 2 , 2 3/4 √ 2- √ 2- √ 2+ √ 2 4 √ 2+4 √ 2- √ 2 (-1/2, -4/19) P6 - 2 1/4 √ 2- √ 2 2 √ 2+2 √ 2- √ 2 , - 2 1/4 √ 2+ √ 2 2 √ 2+2 √ 2- √ 2 (-4/19, -1/2) P7 2 3/4 √ 2+ √ 2- √ 2- √ 2 4 √ 2+4 √ 2- √ 2
, -

2 3/4 √ 2- √ 2+ √ 2+ √ 2 4 √ 2+4 √ 2- √ 2 (4/19, -1/2)
either we find the Euclidean Delaunay face σ p containing p by visiting only faces that do not cross the border of D; then σ p is a (canonical) face of DT H (GP) in conflict with p, and ν loc = 1. or, at some point, we visit a (canonical) face σ D included in D and its (non-canonical) neighbor τ that crosses the border of D. Then the walk continues in non-canonical faces, until we find the Euclidean triangle σ p containing p. Then ν loc is ν nbr (σ D , τ c ) and the canonical face in conflict with p is σ c p = ν loc σ p . If a (Euclidean) face with edges e 1 , e 2 , and e 3 is entered through e 1 during the walk, and if none of e 2 and e 3 separates its opposite vertex from p, then the face contains p. So, two orientation tests are enough to conclude that a face contains p (except for the starting face).

The location translation ν loc is also used when looking for all other faces in conflict with p. Starting from σ c p and for each face in conflict with p, we recursively examine the translated image under ν loc of each neighbor (obtained with a neighbor translation) that has not yet been visited. We store the set Z c of canonical faces in conflict with p. Note that Z c is not necessarily a connected region.

Insertion

It remains to create the new faces and delete the faces in conflict. The translation ν loc computed in the previous step will again be used. We know that p lies in ν loc σ c p . We first create a new vertex v new and store p in it.

By construction, the union of all translated faces ν loc ν nbr σ c p , τ c τ c , τ c ∈ Z c is a topological disk Z in H 2 . We identify the sequence of edges E on the border of Z; each edge e is incident to one face in Z and one face that is not in Z. For each face τ c in Z c , S o C G 2 0 1 7

44:12

Implementing Delaunay Triangulations of the Bolza Surface we temporarily store the translations ν loc ν nbr (σ c , τ c ) ν(v i , τ c ), i = 0, 1, 2 directly in its three vertices (not in τ c , since it will be deleted). Since Z is a topological disk, the result for a given vertex v is independent of the face of Z incident to v that is considered. We store 1 in vertex v new .

For each edge e ∈ E, we create a new face τ e having e as an edge and v new as third vertex. The neighbor of τ e outside Z c is the neighbor through e of the face in Z c incident to e. Two new faces consecutive along E are adjacent. We can now delete all faces in Z.

All that is left to do now is to compute the translations to be stored in the new faces. Let τ new be a newly created face. We retrieve the translations temporarily stored in its vertices v 0 , v 1 , v 2 and we store them in τ new . Equipped with these translations, τ new is not necessarily canonical. If all translations stored in τ c new are equal to 1, then τ new is contained in D, so it is actually canonical. Otherwise, one of the vertices of τ new is v new ; without loss of generality, v 0 = v new , and ν(v 0 , τ new ) = 1. For i = 0, 1, 2 we can easily compute ∆ i = index N (ν(v first_out τi , τ i )), where τ i is the image of τ new under ν(v i , τ new ): in each face, v first_out τi is the first vertex of τ i such that ν(v first_out τi , τ i ) = 1. Note that we do not actually compute the images of τ new , we only compute translations (as words). We then find the index k for which ∆ k is minimal, and in τ new we store the translations ν(v k , τ new )ν(v i , τ new ), i = 0, 1, 2. The face τ new has now been canonicalized. Once this is done for all new faces, temporary translations can be removed from the vertices.

Algebraic complexity

We follow the so-called Exact Geometric Computation paradigm pioneered by Chee Yap [START_REF] Yap | The exact computation paradigm[END_REF].

As can be seen in Section 4, the correctness of the combinatorial structure DT M (P) relies on the exact evaluation of three predicates: SideOfOctagon, which checks whether an input point lies inside D. This predicate is used as a precondition for the insertion of each point. Orientation, which checks whether an input point p in D lies on the right side, the left side, or on an oriented Euclidean segment. This predicate is used when looking for the Euclidean triangle containing an input point.

InCircle, which checks whether an input point p in D lies inside, outside, or on the boundary of the disk circumscribing an oriented triangle. It is used when looking for all faces in conflict with an input point. Let the coordinates of a point p i ∈ H 2 be denoted as x i and y i . The last two predicates can be expressed as signs of determinants:

Orientation (p1, p2, p3) = sign x1 y1 1 x2 y2 1 x3 y3 1 , InCircle (p1, p2, p3, p4) = sign x1 y1 x 2 1 + y 2 1 1 x2 y2 x 2 2 + y 2 2 1 x3 y3 x 2 3 + y 2 3 1 x4 y4 x 2 4 + y 2 4 1 . ( 4
)
We assume that all input points (which lie in D) have rational coordinates (recall that this holds for the initial dummy points, see Section 4.1). So, in the above determinants, at least one point (x i , y i ) is rational. However, the points against which the predicates are testing the new input point are vertices of some face of DT H (GP) contained in U D , so they are images of some input points by translations in N ∪ {1}. Therefore, the evaluation of the two predicates (4) boils down to determining the sign, considered as an element of {-1, 0, 1} of polynomial expressions in rational variables, whose coefficients are lying in some extension field of the rationals, as made precise below. V k g k g k+3 g k g k+3 g k+6 g k g k+3 g k+6 g k+1 g k+1 g k+6 g k+1 g k+6 g k+3

Figure 8 Elements of N around a vertex V k .

Table 3 Matrices of translations around a vertex V k , k. Recall that ξ = 1 + √ 2.

g k = 1 + √ 2 e ikπ/4 √ 2ξ e -ikπ/4 √ 2ξ 1 + √ 2 (see (2)) g k g k+3 = 1 + √ 2 1 -i √ 2 e ikπ/4 1 + i 1 + √ 2 ξ e -ikπ/4 1 -i 1 + √ 2 ξ 1 + √ 2 1 + i √ 2 g k g k+3 g k+6 = -1 + √ 2 (1 + 2i) e ikπ/4 1 + √ 2 (-1 + i) ξ -e -ikπ/4 1 + √ 2 (1 + i) ξ -1 + √ 2 (1 -2i) g k g k+3 g k+6 g k+1 = -2 √ 2 -3 -e ikπ/4 2 + √ 2 + i √ 2 ξ -e -ikπ/4 2 + √ 2 -i √ 2 ξ -2 √ 2 -3 g k+1 g k+6 g k+3 = 1 + √ 2 (-1 + 2i) -e ikπ/4 2 + √ 2 iξ e -ikπ/4 2 + √ 2 iξ -1 + √ 2 (1 + 2i) g k+1 g k+6 = 1 + √ 2 + 2 + √ 2 i e ikπ/4 1 + √ 2 -i ξ e -ikπ/4 1 + √ 2 + i ξ 1 + √ 2 -2 + √ 2 i g k+1 = 1 + √ 2 e ikπ/4 (1 + i) ξ e -ikπ/4 (1 -i) ξ 1 + √ 2
The evaluation of the degree of the predicates requires to perform a case analysis on the different possible positions of the faces in U D , i.e., on the possible translations of N that can be involved in each predicate. The following property shows how we can take symmetries of D into account to reduce the number of possible cases. Lemma 5. Let σ be a face in DT M (P). Then, for any edge uv of its canonical representative σ c , such that ν(u, σ c ) = 1 and ν

(v, σ c ) = 1, index N (ν(u, σ c )) -index N (ν(v, σ c )) ≤ 7.
Proof. We can assume that σ c ⊂ D, otherwise all its three translations are equal to 1. Reusing the proof of of Lemma 1 and the notation therein, we see that σ c is either contained in the disk bounded by B k , or in the disk bounded by C k , for some k ∈ {0, . . . , 7}. So σ c can only intersect D and the seven octagons around some V k . The result follows.

Figure 8 shows the possible translations of N involved in a given canonical representative, for some k ∈ {0, . . . , 7}. Their matrices are given in Table 3.

For k even, the sine and cosine of ±kπ/4 have values in {-1, 0, 1}, while for k odd they are both equal to ± √ 2/2. Therefore, up to sign, the above matrices are divided into two "classes". Due to the symmetries of D O , we actually only need to examine one case in each class, therefore we can focus on the two cases k = 0 and k = 1.

Proposition 1. All predicates can be evaluated by determining the sign of rational polynomial expressions of total degree at most 72 in the coordinates of input points.

Proof. We examine the complexity of the Orientation predicate and refer the reader to the appendix for other ones. As mentioned above, at least one point is inside D. Without loss of generality, we assume that p 3 ∈ D. Let us consider the possible cases for the other two points.

All three points are inside D. In this case, all the arguments of the predicate are rational, so from (4) we get a polynomial with rational coefficients of total degree 2 in the coordinates of the input points. Point p 2 is also in D, and p 1 is outside D. In this case, p 1 can be the image of an input point by 14 possible different translations in N (seven around V 0 and seven around V 1 ). Only p 3 is inside D. In this case, both p 1 and p 2 can be images of input points under the translations around V 0 and V 1 . Of course, we avoid redundancies: if we examine the case Orientation(g i p 1 , g j p 2 , p 3 ), p i , p j ∈ D, we do not examine the case Orientation(g j p 1 , g i p 2 , p 3 ) since it would have the same degree. This amounts to 56 cases in total -28 cases around V 0 and another 28 around V 1 .

We have found with Maple that in all cases, the expressions produced by ( 4) have denominators that are strictly positive and numerators that can be brought into the form

A √ 2 + B ξ + C √ 2 + D, ξ = 1 + √ 2, (5)
where A, B, C, D are rational polynomial expressions in the input coordinates. Moreover, the maximum total degree of A, B, C, D is 5. By squaring twice (to eliminate square roots coming from ξ), we get a rational polynomial of degree 20 in rational variables.

The degree itself, as well as the high number of cases (in spite of the reduction) that would need to be considered, show that giving a complete implementation for all polynomial expressions involved in the predicates is hardly feasible. Therefore, we use the type CORE::Expr [START_REF] Yap | The CORE Library Project[END_REF] included in the cgal distribution to compute the coordinates of translated points and directly evaluate the signs of determinants (4). This number type guarantees that predicates are exact.

Our implementation handles degeneracies using symbolic perturbations [START_REF] Devillers | Perturbations for Delaunay and weighted Delaunay 3D Triangulations[END_REF]. Note that there are no degeneracies in the initial triangulation DT M (Q ).

Experimental results

Experiments are run on a MacBook Pro with CPU Intel Core i5 @ 2.9 GHz, 16 GB RAM @ 1867 MHz running the master version of cgal from GitHub, compiled in release mode with clang-700.1.81. We insert random points uniformly distributed with respect to the hyperbolic metric in D. As mentioned in introduction, dummy points are removed after the insertion of new points. Averaged over 10 executions, the running time is 34 seconds for one million points. This is slower than the computation of 2D Euclidean Delaunay triangulations with cgal, which takes around 12 seconds on average for the same sets of points, using CORE::Expr as number type (and about one second with double number type). This is due in particular to the much higher arithmetic demand in our case (Proposition 1), as confirmed by preliminary profiling, which shows that almost two thirds of the running time is spent in computations of predicates. For the insertion of one million points, only 0.76% calls to predicates involve images of rational points under translations in N , but these calls account for 36% of the total time spent in predicates.

We have also executed tests in which we insert random points in the triangulation and progressively remove dummy points whenever doing so does not violate condition [START_REF] Balazs | Chaos on the pseudosphere[END_REF]. Over

Figure 1

 1 Figure 1 Left: Action of translation a on H 2 . Right: Regular octagon DO and generators of G.

  is a local isometry and a covering projection. The Dirichlet region D p (G) for G centered at p is defined as the the closure of the open cell of p in the Voronoi diagram VD H (Gp) of the infinite set of points Gp in H 2 . From the compactness of M, D p (G) is a compact convex hyperbolic polygon with finitely many sides.

  which denotes the quotient of the group a, b, c, d generated by a, b, c, and d, by the normal closure (i.e., the smallest normal subgroup) in a, b, c, d of the element R G = abcdabcd, called the relation of G. Here and throughout the paper, g denotes the inverse of an element g ∈ G. We use 1 to denote the identity of G: ∀ g ∈ G, gg = gg = 1, and R G = 1 in G.The Bolza surface M is homeomorphic to a double torus. Its area (which is also the area of D O ) is equal to 4π(genus(M) -1) = 4π. The generators of G are naturally ordered around

Figure 2

 2 Figure 2 Left: Voronoi diagram of the infinite set of points GO. Right: The original domain D and the images of O around the vertex V0 of DO.

Figure 3

 3 Figure 3 Left: Curve CD (in bold). Right: The distance between CD and ∂DO is realized as the distance of the points g k and M k .

  since the angles of the triangle (O, V k , M k ) at O and at V k are both equal to π/8. The points O and g k are the intersections of C k and C k+1 , and the segment [O, g k ] is a diameter of B k , so B k is contained in the union of the disks bounded by C k and C k+1 . The segment [

Theorem 2 .

 2 right. The result follows. Let D g denote the closure of the region of g in VD H (GO); D g is the image of D O by the translation g. The infinite set of regions D g , for g ∈ G, form a tiling of the plane H 2 (it was shown on Figure 2-Left.) We define N as the set of translations g in G for which D g ∩ D O = ∅. The set N has 48 elements; it is naturally ordered counterclockwise around O, following the boundary of D O . Each element ν of N has an index index N (ν) in this sequence. We choose abcd as the first element for the sequence N , i.e., index N (abcd) = 0. See Figure 4-Left. We define D N as D N = g∈N D g . Let P ⊂ H 2 be a set of points such that inequality (1) holds for M. If a 2-face σ of DT H (GP) has at least one of its vertices in D O , then σ is contained in D N .From now on, 2-faces will simply be named faces, as done in cgal.

Figure 4 Left:

 4 Figure 4 Left: The translations in N . Right: Proof of Theorem 2.

  1, . . . , 7, which cuts the octagon into two halves. See Figure 4-Right. Both l k and C k contain O; moreover l k is perpendicular to the segment [O, V k ], which is supported by a diameter of C k . So l k and C k are tangent at O and l k separates C k from the other half of the octagon, thus C k cannot intersect any side [V k+j , V k+j+1 ] of D O for j = 2, 3, 4, 5. Using the fact that hyperbolic circles in the Poincaré disk model are Euclidean circles (see Section 2), we continue the proof and the computations in the Euclidean plane E 2 . The sides of D O are supported by the Euclidean circles K E j = (κ j , γ), j = 0, 1, . . . , 7 shown on Figure 4-Right. The centers and radii of K E j , as well as the Euclidean centers ω k and radii ρ of C k are given in

3 (

 3 Canonical representative). With the notation defined above, the canonical representative of a face σ of DT M (P) is the face σ

  e., it reduces to 1. (Here |•| denotes the length of a word.) The next step of the reduction consists in detecting a factorization of the (now freely-reduced) word w of the form w = w λ w µ w κ , where w µ t is a relation R for some t ∈ A * with |t| < |w µ |. Then |w µ | > |R G | /2 = 4 and w µ can be substituted in w by t, which yields the word w λ tw κ with length shorter than |w|.

Figure 6

 6 Figure 6 Left: Delaunay triangulation of M defined by the dummy points. Right: Zooming in on the faces created in iteration i. Note the identification of the marked edges.

Figure 7

 7 Figure 7 Translating τ c by ν = ν nbr (σ c , τ c ) gives a face adjacent to σ c .

Figure 7

 7 Figure 7 illustrates the neighbor translation of the canonical representatives of σ and τ . It can be easily seen that ν nbr(σ, τ ) = ν(v, τ ) ν(v, σ) = ν(v, σ) ν(v, τ ) = ν nbr (τ, σ).We define the location translation ν loc as follows: let σ p be the Euclidean Delaunay triangle containing p. ν loc is the translation that moves σ c p to σ p . The location procedure starts from a face incident to O. Then, for each visited face σ of DT H (GP), we consider the Euclidean edge e defined by two of the vertices of σ. With a simple orientation test, we can check whether the Euclidean line supporting e separates p from the vertex of σ opposite to e. If this is the case, the next visited face is the neighbor τ of σ through e, and we repeat the process, until

Table 1

 1 Table 1 and computed with Maple. What is left to do is to show that C k does not intersect either K E k+1 or K E k-2 . By symmetry, it suffices to consider K E k+1 . The signed Euclidean distance of the circles C k and K E k+1 is 3 If A, B, C are the sides of a hyperbolic triangle and ϑ A , ϑ B , ϑ C the angles opposite to each side, then Expressions for the Euclidean radii and centers of K E j and C k , i, k = 0, 1, . . . , 7.

	sin(ϑ A ) sinh(A)	=	sin(ϑ B ) sinh(B)	=	sin(ϑ C ) sinh(C)	.

Table 2

 2 Exact and rational expressions for the dummy points.

The octagon is rotated compared to[START_REF] Bogdanov | Delaunay triangulations on orientable surfaces of low genus[END_REF]. The notation adopted now seems to be more standard in the literature, see for instance[START_REF] Balazs | Chaos on the pseudosphere[END_REF].S o C G

0 1 7

Π(V k ) = Π(V0), k = 1, . . . , 7: V5 = aV0, V2 = bV5, V7 = cV2, V4 = dV2, V1 = aV4, V6 = bV1, V3 = cV6, V0 = dV3.

For interesting historical facts on this topic, see[START_REF] Joseph | The MacTutor History of Mathematics archive[END_REF]. Software solving the word problem can be found for instance in[START_REF]GAP -Groups, Algorithms, and Programming[END_REF][START_REF]Magma Computational Algebra System[END_REF].

Note that any other set of points that satisfies condition (1) could be used to initialize the triangulation.S o C G 2 0 1 7

44:15

100 executions, all dummy points are removed with the insertion of at least 17 and at most 72 random points.

Due to lack of space, pictures showing some Delaunay triangulations are shown on the web page.