UIST '02

Paris, France

 

15th annual symposium

27-30 oct. 2002

User Interface Software &Technology

uist.org


The Second ACM UIST Interface-Design Contest

Trisha Brady, Joe Marks, and Kathy Ryall
Mitsubishi Electric Research Laboratories & Harvard University Extension School


Contest Overview
Problem Description
Contest Details
Location
How To Enter
- [ July 31: new info! ]
Downloads
- [ October 14: new versions! ]
Appendices
Contact Information

Contest Overview

UIST 2002 will feature the second UIST Interface-Design Contest. Teams will have an opportunity to design and implement an interface to solve a challenging real-world problem prior to the symposium. The problem has been crafted to accommodate a wide range of possible interfaces. During the competition teams will use their interfaces to solve a variety of problem instances, competing against other teams in a tournament. Prizes worth an estimated $1000 will be awarded to the winners. The goal of the contest is to encourage participants to explore interface software and technology in an applied setting, and to provide an opportunity for participants to showcase their work to the UIST community in an exciting and entertaining format.

Packing problems arise frequently in industry. While much effort has been expended on the development of algorithms for various packing tasks, some very important packing problems are still solved better by humans than by computers. Consider the 2D polygon packing in Figure 1: it consists of polygons that represent panels of cloth from which pants will be made. Rotating and translating the polygons to minimize the wasted cloth is a problem of major economic importance in the garment industry. Similar 2D packing problems arise in many other industries. And perhaps surprisingly, human experts still perform better at some of these packing tasks than computers, even after years of algorithm development in the computational-geometry community.


Figure 1. A polygon packing from the clothing industry. Reproduced from K.M. Daniels and V.J. Milenkovic, "Column-Based Strip Packing using Ordered and Compliant Containment," Proc. of the First ACM Workshop on Applied Computational Geometry, May 1996, pp. 33-38.


One of the most promising practical approaches to the 2D polygon-packing problem is the development of computer-assisted packing systems. However, the variety of computer-assisted approaches is very great. What does the human do? What does the computer do? And what is the interface between human and computer? These are the questions that will be posed to contestants in the Second UIST Interface-Design Contest!

Back to Top



Problem Description

An instance of the contest packing problem is given as an ordered quadruple of integers, (a, b, c, d), where 0 < a,b,c,d < 100. The numbers a, b, c, and d refer respectively to the number of 2x2, 3x3, 4x4, and 5x5 squares to be packed. The squares are to be divided into three lots; the squares in each lot are to be packed into the smallest square bin that holds them. The score of a layout is given as a quadruple (s1, s2, s3, t), where s1, s2, and s3 are the side lengths of the square bins in descending order of size, and t is the time of the submission in seconds. Scores are ranked lexicographically, with smaller being better. For example, Figure 2 contains a solution to the problem instance (2, 6, 6, 6). Assuming it was submitted at elapsed time t = 100, its score would be (12.12, 11, 10, 100). A better packing for this problem is shown in Figure 3. Assuming a submission time of t = 200, its score would be (11, 11, 10, 200). It is the better layout because its largest bin (the first element of the quadruple) is smaller.

The following observations are worth noting. The problem instance illustrated in Figures 2 and 3 is much smaller than the problem instances that will be used in the contest. A bounding square is different from a (rectangular) bounding box. Rotation of squares is allowed and is sometimes crucial to achieving a good score (though not in this case). Finally, for further appreciation of the complexity of packing squares in squares, consult the paper by Erich Friedman, "Packing Unit Squares in Squares: A Survey and New Results," available at: http://www.stetson.edu/~efriedma/squinsqu/PackingSquares.ps.

Bin 1: 12.12x12.12
Bin 2: 11x11
Bin 3: 10x10

Figure 2: A solution to the problem (2, 6, 6, 6). The yellow, red, blue, and green squares are 2x2, 3x3, 4x4, and 5x5, respectively. This packing's score is (12.12, 11, 10, t), where t is the time of submission.


Bin 1: 11x11
Bin 2: 11x11
Bin 3: 10x10

Figure 3: An alternative solution to the problem (2, 6, 6, 6). It has the better score of (11, 11, 10, t').




Back to Top



Contest Details

The contest will consist of several rounds, with a different problem instance for each round. Performance will be aggregated over all rounds to determine the contest winners. Each round will last 30 minutes, during which all teams will work simultaneously. Problem instances will be announced verbally, so each contestant is responsible for entering the quadruple of numbers accurately into their computer.

Teams may submit a solution at any time during a round. Solutions must be conveyed via a floppy disk or memory stick to the contest referee. The current best score will be posted for all teams and spectators to see, but the packing solutions will not be shown until the end of the round.

A result is a packing for the problem, described in XML. The XML DTD for reporting results is appended to this document. The contest referee will print the packing, verify that it is a valid solution and give it a timestamp, and post the score if it overtakes the current best score. The software that the referee will use is available to everyone on the contest website.

Teams may use any and all UI technologies (e.g., multiuser, multimodal, intelligent assistance, tangible interaction, etc.) in designing and implementing their interfaces. We note in passing one important design consideration: speed matters. Informal playtesting has shown that for many problem instances, people will find packings of the same size. In such cases submission time will be the deciding factor.

Prizes will be awarded in three categories: the best single-user interface, the best multiuser interface, and the best interface designed by an all-student team.

Back to Top



Location

The contest will be held during the 15th Annual ACM Symposium on User Interface Software and Technology (UIST 2001), to be held in Paris, France from October 27-30, 2002. The time and location of the contest will be announced in July 2002.

Back to Top



How to Enter -
[ New July 31st ]

To enter the 2002 UIST Interface-Design Contest, please send an email to trisha_ncsu@yahoo.com and include your name and email. All notifications of contest updates will be sent to the email list. If you are interested in entering the contest, but will not be able to attend the conference, please indicate this in your email. There will be student volunteers available at the contest to participate in your absence.

Back to Top



Downloads

In order to run the verifier program, you need to download two different zip files. The first, XMLParserCode is two jar files provided by Sun's apache project, used to parse XML files. These need to be in your classpath to run the Verifier. The second is the Verifier.zip, which contains our class files for the Verifier program, and a run.bat file. We have also included two sample input files, as well as the XML DTD in a third zip, called InputData.zip.

  • Verifier.zip - [ <= October 14 - new version that prints color !]
  • XMLParserCode.zip
  • InputData.zip- [<= July 15 - new version !]
    Back to Top



    Contact Information

    For more information contact Kathy Ryall (ryall@merl.com).

    Back to Top