New and improved results for packing identical unitary radius circles within triangles, rectangles and strips

The focus of study in this paper is the class of packing problems. More specifically, it deals with the placement of a set of N circular items of unitary radius inside an object with the aim of minimizing its dimensions. Differently shaped containers are considered, namely circles, squares, rectangles, strips and triangles. By means of the resolution of non-linear equations systems through the Newton-Raphson method, the herein presented algorithm succeeds in improving the accuracy of previous results attained by continuous optimization approaches up to numerical machine precision. The computer implementation and the data sets are available at http://www.ime.usp.br/similar to egbirgin/packing/. (C) 2009 Elsevier Ltd, All rights reserved.

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

Impossible triangles: flat actors in telematic theatre

In fact, in this scene, both A and B are online. A is in a classroom at the University of Amsterdam in The Netherlands, and B is in a television studio at Deakin University in Melbourne, Australia. The two locations are connected through video conference and, in each space, a local audience watches the local performer in the room, and the remote performer projected on a screen. The performers are captured in profile, and appear to be looking at computer screens in front of them but cannot actually see one another. The text is consciously banal, composed to replicate the broken rhythms and sequences, flattened tone and repetitions of scrolling words in a text box on a screen. Information about presence and absence (A or B is offline or online) is spoken as text. Although the two performers speak in accents that declare their different language/ cultures, the vernacular is generic 'internetslang'. The relatively monotonous and unpunctuated delivery of the textual rhythms is interrupted and counterpointed by a sound lag of nearly a second, and by a faint audio echo as one voice 'lands' in the second location. Its orchestration allows the sound fracture and dispersal in some moments. In other moments, the actors anticipate or absorb the gaps in transmission, driving the speech rhythms through so that the utterance 'arrives' precisely at the end of the prompt line.