Discrete and Computational Geometry

This volume consists of the refereed proceedings of the Japan Conference on Discrete and Computational Geometry (JCDCG 2004) held at Tokai University in Tokyo, Japan, October, 8-11, 2004, to honor Jan ¿ os Pach on his 50th year. J¿ anos Pach has generously supported the e?orts to promote research in discrete and computational geometry among mathematicians in Asia for many years. The conference was attended by close to 100 participants from 20 countries. Since it was ?rst organized in 1997, the annual JCDCG has attracted a growing international participation. The earlier conferences were held in Tokyo, followed by conferences in Manila, Philippines, and Bandung, Indonesia. The proceedings of JCDCG 1998, 2000, 2002 and IJCCGGT 2003 were published by SpringeraspartoftheseriesLectureNotesinComputerScience(LNCS)volumes 1763, 2098, 2866 and 3330, respectively, while the proceedings of JCDCG 2001 were also published by Springer as a special issue of the journal Graphs and Combinatorics, Vol. 18, No. 4, 2002. The organizers of JCDCG 2004 gratefully acknowledge the sponsorship of Tokai University, the support of the conference secretariat and the partici- tion of the principal speakers: Ferran Hurtado, Hiro Ito, Alberto M¿ arquez, Ji? r¿ ? Matou? sek, Ja ¿nos Pach, Jonathan Shewchuk, William Steiger, Endre Szemer¿ edi, G¿ eza T¿ oth, Godfried Toussaint and Jorge Urrutia.