HISTORY AND OVERVIEW This bibliography, an ongoing project whose goal is to offer a reasonably complete database of publications in computational geometry, came into existence in 1986 when two lists of publications were merged into one and it was decided to continue from there. One of these lists was a compilation (by Edelsbrunner and van Leeuwen) of papers that was kept up to date until 1982 and that was published in 1983. At that point it contained 871 entries. The other was a more private list (by Guibas and Stolfi) of publications, that contained 913 entries when it was used to get this project started. After that quite some effort was put into cleaning up what we had, adding new publications (with help from Ronse, Smith, and Forrest), and beginning to augment entries with descriptive keywords. A first version was printed in October 1987 (another dated June 1988 was included as an appendix to Alok Aggarwal's MIT lecture notes) and copies were distributed with the intention that people use the bibliography for their work, correct it, add new papers, update manuscripts, reports or conference papers that appeared in journals, and send the corrected versions back for editing. Through its early years, the bibliography was maintained through this paper-based system, first by Herbert Edelsbrunner and later by Joe O'Rourke. In 1990 we changed to an on-line approach to distribution and updating because of two observations. First, that the bibliography's value depends on how directly we in the community can use it in our day-to-day work of researching and writing. Second, that any method requiring updates to be edited one by one, by a single volunteer, cannot scale well beyond some critical rate of publication: the clerical work becomes onerous, and either quality or coverage must suffer. Many hands make light work, and if those hands are editing electronic versions of the same document, version control software can merge their changes with little clerical overhead. Bill Jones has been coordinating the on-line form of the bibliography using such a distributed-maintenance strategy. The current version of the biblio can be retrieved via anonymous ftp as . As with earlier paper versions, you are encouraged to use it actively, make additions and corrections, and send those changes to the coordinator (jones@cs.usask.ca) for integration into a new revision. After unpacking the archive, you should preserve the original biblio source file of geom.bib in some read-only form (called geom.arch, say) and make a writeable copy for your actual changes. At merging time, you should send your changes in the form of a context diff ("diff -c geom.arch geom.bib") between the old and new files. Changes to any other file in the distribution can be reported in the same manner. At the receiving end the patch program uses the diff to reconstitute your changed file, and RCS then combines it with others' contributions. If you have no access to a Unix system, you are updating only a few entries, or your contribution consists entirely of entries that are unknown to this bibliography, you are welcome to send them unadorned. Otherwise, you should please edit geom.bib yourself and send a diff -- there have been over 1800 entries changed in a single release and a one-person clerical bottleneck is as infeasible in electronic form as it was on paper. diff form is particularly important when changing any existing entries, since it ensures subtle corrections will be incorporated rather than being mistaken for duplicates and discarded. Please don't move existing entries around in the file when editing; it makes for extra difficulty in resolving changes from other updates. You will also find an assortment of software tools in the archive, and a softcopy formatting of the bibliography is available in the ftp directory as geom.ps.Z (Postscript, ~350 pages). David Johnson's STOC/FOCS bibliography inspired various aspects of the formatting, including author cross-referencing. However, you should note that we do not attempt special-case processing of authors' names: initials and diacriticals are printed as they were entered. The ftp directory also contains the file o-cgc19.ps.Z, which is the issue of Joe O'Rourke's computational geometry column discussing the bibliography. Another interesting item is , slides from a talk reflecting on our field's origin, growth, and directions, with illustrative data drawn from this bibliography. There are now several servers offering a web search interface on top of biblook, a combination first constructed by Otfried Cheong (n\'e Schwarzkopf). One list can be found through Jeff Erickson's geometry pages at but this has not been updated since 1998. Web search sites currently known are > and the netlib service also offers searches via email; a message like "find chazelle linear polygon" sent to compgeom-request@research.bell-labs.com will send results by return mail. Beware that all of these services may wind up searching an older release of the bibliography. When an entry has been annotated with a URL field, some of the servers will recognize this and allow you to download the network object pointed to, e.g. a Postscript copy of a techreport. (You can find some examples by looking for "ftp" in "any" field.) This and other bibliographies are also web-searchable via the Bell Labs netlib at which also offers an email interface: send a message with a line like find chazelle triangulation polygon in the Subject: or message body to compgeom-request@research.bell-labs.com. The contact for this service is Ken Clarkson, clarkson@research.bell-labs.com. There is a new Project BibRelEx on top of the database geombib. Its intention is to help the user to explore a bibliographic database by visualizing content-based relations such as "cites", "succeeds", "improves with respect to" among its entries. BibRelEx is run by Christian Icking, Rolf Klein, Britta Landgraf, and Hildegard Schmidt, all at FernUniversitaet Hagen, and Anne Brueggemann-Klein, at TU Muenchen. You can get more information on BibRelEx from their web pages at . (Click on the country flags to select German or English text.) Surendar Chandra (surendar@cs.duke.edu), provides geombib to refdbms users on port 4117 from refdbms.cs.duke.edu. You can get more information on refdbms (a distributed bibliographic database that propagates updates to all sites) from . BIBLIOGRAPHERS This bibliography is and always has been a product of the good will of volunteers from our community. An essential idea of this project is that it ought to be a social effort, and that everyone who is using this bibliography should feel willing to contribute his or her share in improving it. The following are the volunteers who have made contributions to this electronic form of the bibliography, whether in getting it up and running, or converted to bibtex, or continuing to improve its coverage, accuracy, and software support. Joel Abbott, Stephen Abrams, Pankaj Agarwal, Ossi Aichholzer, Varol Akman, Pedro Aphalo, Boris Aronov, Ian Ashdown, Franz Aurenhammer, Nelson Beebe, Javier Bernal, Sergei Bespamyatnikh, Project BibRelEx, David Bremner, Erik Brisson, Thomas Chadzelek, Otfried Cheong, Seung-Hak Choi, Karen Daniels, Amitava Datta, Frank Dehne, Olivier Devillers, Luc Devroye, Tamal Dey, Scot Drysdale, Herbert Edelsbrunner, Alon Efrat, Jeff Erickson, Jianhong Feng, Robin Forrest, Paolo Franciosa, Randolph Franklin, Robert Freimer, Bernd Gaertner, Laxmi Gewali, Sherif Ghali, Subir Ghosh, Michael Goodrich, Mic Grigni, Andre Guedes, Sumanta Guha, Leo Guibas, Dan Halperin, Sariel Har-Peled, Martin Held, Michael Houle, Philip Hubbard, Christian Icking, John Johnstone, Bill Jones, Matya Katz, James Klosowski, Nick Korneenko, Marc van Kreveld, Ulrich Kuehn, Rafael Laboissiere, Tim Lambert, Guiseppe Liotta, Jiri Matousek, Michael McAllister, John Milone, Joe Mitchell, Scott Mitchell, Bernard Moret, Rajeev Motwani, T. M. Murali, Rene van Oostrum, Joe O'Rourke, Valerio Pascucci, Maurizio Patrignani, Christine Piatko, Michel Pocchiola, G. Ramkumar, Kathleen Romanik, Guenter Rote, Neil Rowe, Joerg Sack, Stefan Salinger, Malcolm Sambridge, Erik Schoenfelder, Micha Sharir, Chan-Su Shin, Michiel Smid, Diane Souvaine, Roberto Tamassia, Ansel Teng, Ted Tuan, Jan Vahrenhold, Darren Vengroff, Luca Vismara, Jeff Vitter, Dave Watson, Rephael Wenger, Mike Werman, Barbara Wolfers, Derick Wood, Peter Yamamoto, Gabriel Zachmann Being a social effort, the project can continue only so long as it enjoys widespread support. We ask that, if you are using this bibliography, find it helpful, and wish it to carry on, you ``pay forward'' a fraction of the time that it saves you by joining us and contributing updates as described herein. Closing dates for updates, after which a merge and rerelease are done, are the second Mondays of March, July, and November. Contribution reminders and release announcements are sent only through a mailing list; you can join by sending mail to majordomo@cs.usask.ca with a body of "subscribe geombib". (Mail to geombib-request@cs.usask.ca will yield some details about the list and how to join, but no subscription.) Participation by true bibliomaniacs (i.e. those developing other databases or software) is especially welcome -- please let us know so we can discuss possible coordination of efforts. CREATING ENTRIES What goes in? Papers relevant to computational geometry, which for us means the study of the computational complexity of well-defined geometric problems. Thus we are talking algorithms, data structures, analysis of time and storage, lower and upper bounds, but also geometric objects, geometric operations, and combinatorial complexity of geometric structures. We interpret relevance in a rather broad sense, although we prefer that references from cognate areas (such as discrete geometry, solid modeling, image processing, computer graphics, and robotics) emphasize books or survey articles rather than individual papers. In the end, your judgement as a working computational geometer decides what is relevant and worth inclusion. (A pragmatic test: have you cited or would you cite the item in your own papers?) Future maintenance is easiest if you include only papers that are "stable", i.e. published and openly available at least in the form of a numbered techreport, and preferably in a conference proceedings. However, it is okay to include preprints too. If the paper is slated to appear somewhere else, that information can usefully annotate the entry for an existing appearance. Mary-Claire van Leunen's book _A Handbook for Scholars_ (Knopf, New York, 1979) advocates high standards in bibliographic scholarship, particularly in its insistence that nothing short of the original title page can be trusted: "To write a reference, you must have the work you're referring to in front of you.... The temptation to write a reference without having the work before you will be powerful. Resist it. A vague recollection is worthless; a vivid recollection is probably the result of your imagination --- ingenious, no doubt, but of little use to your reader. Don't rely on your memory.... If you must not rely on your own memory, even less should you rely on someone else's. If your only access to a reference is through a secondary source, then you must refer to the secondary source as well as the primary one." You should take this counsel seriously and not make changes lightly. Author, title, and page information from other than the title page of the paper itself is untrustworthy: you might want to do data entry from a proceedings table of contents for speed, but do take time to proofread against title pages for accuracy. Also, be reluctant to "correct" existing entries unless you yourself are working from the title page; instead you can add a marginal % note, as described below. We value the accuracy and relevance of your contributions to the bibliography more highly than their sheer volume. But please bear in mind that there is a minimum overhead of at least an hour to process each diff file in the merging process, making larger updates more efficient than tiny ones. Coordinating your changes with those of other colleagues at your site before sending is greatly appreciated. There is always room for new ideas on how to capture data with greatest accuracy, best efficiency, and least overlap, but at present the following approach seems to work well: 1) use the bibliography as a bibtex database when typesetting references for your own papers, so that adding entries and making corrections can happen as a natural side effect of your own work. 2) during that process, you will likely wind up referring to papers from some conference or journal year that isn't known to have been covered by the bibliography (see the list below). It would be very helpful if you took the time for at least one such paper to check through the whole volume and ensure that all relevant geometry papers have been incorporated in the bibliography. (This doesn't take so long as you might think: by keeping an entry template with repetitive details ready in your editor, within an hour you can enter a full conference of about 50 papers.) 3) please look carefully at entries for papers written by you, or by people at your institution, to ensure their correctness. No one else can do this more accurately or more efficiently. 4) if you are caught up with current events and have time to spare, you can work on something from our open problems list; or you can check back through unexamined years of a journal or conference to ensure that all relevant papers are included, correct, and keywordized. To help with checking coverage, here are data for some conferences and journals that are, or have been, popular in the bibliography, listing a rough estimate of how many relevant articles they publish per year, and for what years bibliography coverage has been verified. Please mention any new territory you have covered when you send your update. 3 ACM Trans. Graph. 82-91: freimer 20 Algorithmica 86-91: freimer 8 Algorithms Review (EC Project ALCOR) 90-: devillers 3 Combinatorica 81-91: freimer 4 Commun. ACM 25 Comput. Geom. Theory Appl. (CGTA) 91-95: devillers 2 Comput. Graph. (SIGGRAPH) 98: held 2 Comput. Vision Graph. Image Process. 30 Discrete Comput. Geom. (DCG) 86-91: freimer 3 IEEE Comput. Graph. Appl. 15 Inform. Process. Lett. (IPL) 25 Internat. J. Comput. Geom. Appl. (IJCGA) 91-95: devillers 4 J. ACM 80?-91: freimer 6 J. Algorithms 80-91: freimer 6 J. Comput. Syst. Sci. 80?-91: freimer 3 Proc. Nth ACM Sympos. Parallel Algorithms Arch. (SPAA) 20 Proc. Nth ACM-SIAM Sympos. Discrete Algorithms (SODA) 90-91: jones; 92: freimer; 93: mitchell∣ 95: agarwal; 96: mitchell; 97: held 9 Proc. Nth Allerton Conf. Commun. Control Comput. 40 Proc. Nth Annu. ACM Sympos. Comput. Geom. (SCG) 85-88: edelsbrunner; 89-90: orourke; 91: agarwal; 92: freimer; 93-94: jones; 95: mitchell; 96-97: efrat; 00: jones+smid 8 Proc. Nth Annu. ACM Sympos. Theory Comput. (STOC) 91: agarwal; STOC/FOCS biblio: freimer; 92: freimer∣ 93-94: mitchell; 95: smid ? Proc. Nth Annu. European Sympos. Algorithms (ESA) 93: milone+mitchell 8 Proc. Nth Annu. IEEE Sympos. Found. Comput. Sci. (FOCS) 90: agarwal; 91: jones; 92: freimer; 93: milone+mitchell; 94: smid; 95: mitchell 12 Proc. Nth Annu. Internat. Sympos. Algorithms Comput. (ISAAC) [LNCS] 90-91: smid 70 Proc. Nth Canad. Conf. Comput. Geom. (CCCG) 89-92: jones; 93: milone+mitchell; 94-95: jones; 96: mitchell; 97: jones 4 Proc. Nth Conf. Found. Softw. Tech. Theoret. Comput. Sci. (FSTTCS) [LNCS] 40 Proc. Graph Drawing 'yy (GD) [LNCS] 94: tamassia; 95-97: patrignani 5 Proc. Nth Internat. Colloq. Automat. Lang. Program. (ICALP) [LNCS] ? Proc. Nth Internat. Sympos. Math. Found. Comput. Sci. (MFCS) [LNCS] 25 Proc. Nth {European,Internat.} Workshop Comput. Geom. (CG'yy) [LNCS] 91: rote; 93: milone+mitchell; 88-00: icking 4 Proc. Nth Internat. Workshop Graph-Theoret. Concepts Comput. Sci. (WG'yy) [LNCS?] 93: milone+mitchell 15 Proc. Nth Scand. Workshop Algorithm Theory (SWAT) [LNCS] 88: smid; 90: freimer; 92: freimer&smid 5 Proc. Nth Sympos. Theoret. Aspects Comput. Sci. (STACS) [LNCS] 89-90: schwarzkopf; 92-93: smid 15 Proc. Nth Workshop Algorithms Data Struct. (WADS) [LNCS] 89: jones; 91: agarwal; 93: milone+mitchell; 95: mitchell 6 SIAM J. Comput. 80?-90: freimer; 91: mitchell 2 SIGACT News 2 Theoret. Comput. Sci. 6 Visual Comput. 85-91: jones; 95: klosowski FORMATTING ENTRIES As of the winter 1992 release, the bibliography has been converted to bibtex. Up to this time the bibliography had (for historical reasons) been more or less in the format of the old "refer" program designed as a citation system for troff. Special thanks to volunteers Jeff Erickson, Robert Freimer, and Peter Yamamoto, who took the initiative of developing quality conversion software to meet our situation. Because of the distributed nature of updates, it seems desirable to have some written guidelines for the format of entries, in order that the final product have a consistent style. The following suggestions are based on common practice where discernible, established authorities where possible, and personal opinion where unavoidable. You will likely find existing entries in disagreement with these guidelines. Either the entry or the guidelines should be fixed. If some entry can't be decently handled by the current guidelines, or you think they're just plain wrong in any case, please let us know about it. In the hope of keeping future input work reasonably simple and error-free, a few lexical conventions were set at the time of bibtex conversion, as follows. Where possible you should use lower case (for simplicity), a leading comma ``, volume = 12'' (to make missing commas obvious), and put all text for a field on a single line (to avoid spending time on prettyprinting). For more prolix fields, such as abstract= or annote= or comments= or note=, wrap at around 75 characters and start subsequent lines with zero or one tabs. Special characters and diacriticals should be entered as specified on p.52 of the TeXbook. The common single-letter ones are described below. \' acute sup{\'e}rieur {\'O}'D{\'u}nlaing [\*' in troff -ms] \` grave probl{\`e}me Bruy{\`e}re [\*` in troff -ms] \^ circumflex m{\^e}me L'H{\^o}pital [\*' in troff -ms] \~ tilde ma{\~n}ana N{\'u}{\~n}ez [\*' in troff -ms] \v hacek h{\'a}{\v c}ek Matou{\v s}ek [\*C in troff -ms] \c cedilla fran{\c c}ais {\'S}wi{\c a}tek [\*, in troff -ms] \" umlaut f{\"u}r G{\"u}ting [\*: in troff -ms] \H Hung. umlaut Erd{\H o}s [R.I.P. 96.09.20] \i dotless i D{\'\i}az where accented \j dotless j where accented Note that diacriticals precede the letter affected. A complication is that in tex, control sequences specified using letters must somehow be separated from the ordinary letters that follow. A simple way is to use spaces as in "Erd\H os", but this will look like two separate words to bibtex. Another is to use braces as in "Erd\H{o}s", but this too is confounded by bibtex, which (1) normally wants to decapitalize text in titles not protected by braces, to support variant capitalization styles, and (2) will interpret an umlaut \" as the end of a quoted string, unless specially protected. Initially it might seem enough to put braces around the whole word when it contains either a fussy diacritical or (in a title field) a capital letter. However, it turns out that, because of how it handles the author field, bibtex dictates the convention to follow. Since adding a feature to recognize and handle accented characters in author fields (for benefit of the alpha bibliography styles), bibtex requires that we "place the entire accented character in braces; in this case either {\"o} or {\"{o}} will do .... furthermore these braces must not themselves be enclosed in braces (other than the ones that might delimit the entire field or the entire entry), and there must be a backslash as the very first character inside the braces". Thus you must use, for example, {\'O}'D{\'u}nlaing, Matou{\v s}ek, G{\"u}ting, and Erd{\H o}s, and we recommend that for consistency you treat all accents this way in whatever bibtex fields they appear. However you will further have to embrace the whole of any capitalized name that appears in a title field. C'est la vie {BibTeXienne}. A few hacks deserve mention. The macros \path or \url, from path.sty and url.sty respectively, help with transparency and linebreaking of network pathnames like \path|http://hamster.cs.uni-sb.de/~eckstein/publications/FB14-95-05.ps.Z|, and should be used whenever they appear in regular text. (path.sty is part of the Eplain package, and is being used when typesetting the url field for geom.ps.) Tex ties like ~ and "\ " should be avoided in regular text, as bibtex undertakes to insert them where appropriate. Mathematical expressions, including numbers in titles, should always be entered in tex notation. Below is a quick naming of parts for entries in the database, with discussions of the conventions that have evolved. More detailed information on entry formats can be found in the bibtex documentation. Entry type: we ignore some of the fine distinctions available in bibtex and map most everything onto the types of article, book, inbook, incollection, inproceedings, mastersthesis, phdthesis, and techreport. Preprints (a.k.a. "Manuscripts") are considered unnumbered techreports for our purposes, since they are often later distributed in that form. If present entries in the bibliography are any guide, you should rarely need other entry types. In particular, note that low-grade items like personal communications should not be included since our intention is to cover only openly available materials. If you need such an entry in your papers' reference lists, please keep it in a supplementary bibliography file until it is published. For example, "\bibliography{mine,mygroup,geom}" specifies a search path of three files bibtex can use to satisfy references. Citation tag: it's easy to come up with citetags that are mnemonic, short, or unique, but not to have all three at the same time. The system we use is a compromise. Our citetags consist of an author part (first letter of surname of each author), a title part (first letter or digit string of each significant word in the title, up to preferably no more than 5 characters), and a year part (last two digits of year of publication), separated by dashes. Connecting words like auf, da, de, der, van, von are considered part of the surname if and only if they are capitalized. Thus "J. O'Rourke, Art Gallery Theorems and Algorithms, 1987" reduces to "o-agta-87". The tricky part of this is how to define "significant" words of the title, particularly when punctuation and mathematical strings are involved. Here are the formal rules, which are intended to produce a commonsense result as often as possible: - ignore these words (most common short English articles, conjunctions, and prepositions): "a" "among" "an" "and" "as" "at" "by" "for" "from" "in" "into" "of" "on" "or" "over" "than" "the" "to" "under" "via" "with" - convert Roman numerals to Arabic, remove diacriticals, braces, and font-changing commands (like \it), remove quotes and apostrophes, convert other punctuation outside math delimiters $...$ to spaces - retain only the first alpha/numeric token within $...$ delimiters - take the first letter, or first digit string, of remaining words - take the first 5 characters so produced For example, "fran{\c c}ais" and "$\log n-1$" are each one word while "$k$th-nearest" is two, and the abbreviation of "{${\rm SEPARATION}^{\rm TM}$} and $(\leq k)$-levels IV: A silly example" is "sll4s". To make the result more intuitive, we break the rules in the following cases: - "\varepsilon" becomes "e" - "on-line" and "online" become "ol" instead of "l" and "o" respectively. - "2d" becomes "2d" instead of "2" (similarly for "1d", "3d" etc) For just under 99% of entries the citetag generated by this procedure will not conflict with that of any existing entry. But if it does, you'll have to find some way to break the tie. In our experience, collisions at this stage have come about only from various forms of the ``same paper'' conflicting with each other, and one of the following tiebreaking rules suffices: - for multipart papers, add the part number, in Arabic, to the title field (c-lbors1-90, c-lbors2-90) - for other variations on a theme, add a letter from a distinguishing word to the title field (s-mmdpsl-90, s-mmdpsp-90) - for alternate publications of a paper, append "a" for article, "i" for incollection or inbook or inproceedings, or "t" for techreport, to the year field (kkt-ptots-90i, kkt-ptots-90t) - otherwise, punt and discriminate using whatever you can (g-gramq-cga-88, g-gramq-edbt-88) If the resulting citetags don't match your favourite descriptor for the reference, you can still use the old familiar version if you declare a mapping between the two in your tex source, such as the following: \newcommand{\smawk}{akmsw-gamsa-87} Entry citetags should be mostly stable once assigned, but may be changed in the direction of correctness, or to resolve conflicts. You needn't bother creating citetags for entries you don't cite: just leave the tag part empty. The merging software will automatically generate citetags for contributed entries lacking them. It also tries to rewrite conference and journal names to standard form, does prettyprinting, and keeps entries in the geom.bib file sorted in order of author, title, and year, all the better to bring various appearances of the same paper together. (This should match the order of the default softcopy.) Fields: we inherit most fields from the bibtex standard styles, as well as common extensions like abstract=, annote=, isbn=, issn=, language=. Fields archive=, cites=, comments=, keywords=, nickname=, precedes=, site=, succeeds=, update=, and url= are our own. Conventions for entering all of these are as follows. Quotes aren't necessary when the field value is entirely digits (true for volume, number, and year, normally). You should use the empty string "" for fields you can't complete just yet (e.g. pages = "" for a conference or journal paper to appear). Some entries use a visible placeholder like "??" to flag significant omissions; if you need to cite them, please make an honest effort to fill the hole rather than immediately changing to "". abstract: verbatim from the original item (optional) - encouraged, at least when concise address: city of publication - use for techreports, theses, or obscure publishers; otherwise discouraged - use only first city if publisher lists several - add two-letter state/province codes for US/Canada cities; for others, add country - give English-language name, with correct diacriticals (e.g. Munich rather than M{\"u}nchen, Saarbr{\"u}cken rather than Saarbruecken) - city/country names to use are those in effect at time of publication (e.g. West and East Germany between 1949 and 3 October 1990, Germany otherwise) - for @inproceedings items, an address without publisher will be presumed by the merging software to be the conference city, and rewritten into the site field annote: explanatory or critical comment on item content (optional) - little used in present entries, but welcomed archive: pointer to copy of item available from repository (optional) - syntax repository:ref - example "XXX:cs.CG/9907024, UMI:AAC86-29439" - please check before inventing further repository names author: - separate multiple author fields with " and ", order same as in reference - author's names in normal order, not reversed - use braces to enclose capitalized or comma-separated elements of a compound surname, e.g. {Van Wyk} or {Lipski, Jr.} - rather than using initials, do enter full given names as used on the title page, and if desired have bibtex abbreviate them later (cf. the abbrv style) - rather than using "others" or "et al.", enter the full list of authors - [van Leunen p.155] by "strict and narrow propriety" we should cite precisely the name which appears on the item, even if it leads to irregularities. While it is reasonable to fix up such typographical glitches (attributable to coauthors, copy editors, and the pressure of deadlines) as you are certain the author would want you to, remaining inconsistencies are the author's worry and not the bibliographer's. - only accents in the style of M{\"u}ller and not, for example, M\"{u}ller or M\"uller will be accepted by bibtex booktitle: title of book or proceedings containing item - for English items, capitalize first word, first word after a colon, and all other words except articles and unstressed conjunctions and prepositions. Otherwise follow capitalization conventions of the native language, if you know them. (According to the MLA Handbook, for French, German, Italian, Latin, and Spanish, capitalization in titles is the same as in normal prose.) There is no need for braces on capitalized words in this field. - abbreviations for some popular conferences are in the authority file. The merging software will recognize modest variations in abbreviation and convert them to standard form, but it cannot work miracles. In particular, please avoid including, via parentheses or otherwise, nicknames like SODA, or material like locations and dates that should appear elsewhere or not at all. The merging software will automatically move into the nickname field trailing strings of the form ([A-Z]+[~ ']*[0-9]*), and this pattern may be extended in future. chapter: chapter or section number, where item is part of a monograph - use entry type of incollection if chapter has its own title, inbook otherwise cites: citations made by item (optional) - give as list using biblio citetags, such as cites = "bs-dcms-76, gjpt-tsp-78, o-agta-87" - needn't be an exhaustive copy of the item's citations, but if used should at least give the significant ones. You can say cites = "bs-dcms-76, ..., ZZZ" if the list is exhaustive. comments: bibliographic marginal notes - supplemental information not a part of the reference proper: notes on a item's source language, or relation to other items, or a UMI order number and page count, or a Computing Reviews or Math Reviews number.... - separate multiple comments with a semicolon edition: of a book - use numbered ordinal, e.g. "2nd" editor: - editors of proceedings not needed for each entry, and discouraged (make a separate entry for the proceedings itself) - otherwise, use guidelines for author institution: publisher of a techreport - include any relevant department, and list in minor-to-major order (e.g. "Inst. Math., Univ. Nancago") isbn: of book (optional) issn: of series (optional) - worthwhile only for obscure or otherwise hard-to-find items - give with hyphens as specified by publisher journal: - abbreviations for some popular journals are in the authority file. The merging software will recognize and convert most variant abbreviations to standard form. - separate journal series are considered separate journals, e.g. journal = "J. Combin. Theory Ser. A" rather than series or volume A keywords: - use to supplement, for searching or descriptive purposes, terms already present in the item's title - separate multiple keyword terms with commas - keywords need only be attached to the newest of a paper's appearances, if identical for all - use those in authority file, by preference - additions to the list of keywords, are expected and welcomed, within reason; send a diff for the authority file at update time language: original language of an entry (if not English) - supported by AMSTex styles, so we might as well month: month of publication - encouraged for techreports and theses, discouraged otherwise - use bibtex standard abbreviations (three letters, lower case, no quotes) nickname: short name of conference, distinct from booktitle - e.g. "ISAAC '94" - best used on an entry for the proceedings itself, where years of publication and conference differ, or where connection between conference and booktitle is obscure; discouraged otherwise note: - use for supplemental information that should appear in a citing paper's reference list; otherwise use comments field - e.g. note = "Errata in 2(1981), 105" or "Special Issue on Networks" - for theses, give techreport type and number, if known, e.g. note = "Report TR-86-103" number: of techreport, work in a series, or issue of journal - essential for true techreports (nolle techreportum sine numeratum) - for journals, necessary iff there exists more than one "page 1" per volume (e.g. proceedings as separately-paginated issue of journal), and discouraged otherwise - use "--" for combined issues, e.g. "3--4" pages: - use double dash "--" in a number range precedes/succeeds: pointer lists for temporal relationships among entries - for example precedes = "oy-nubks-88" points to new & improved paper succeeds = "k-cmgcl-77, k-cmgca-79" is backpointer from it publisher: - see authority file for standard names of some publishers school: granting degree, for thesis - include any relevant department, since this assists inquiries about availability or contents, and list in minor-to-major order (e.g. "Dept. Comput. Sci., Univ. Nancago") series: of books - e.g. "Lecture Notes Comput. Sci." site: city of conference - available for those who prefer to record it, but generally discouraged for individual papers (make a separate entry for the proceedings itself) title: of item - for English non-books, you need only capitalize first word and proper names, and enclose latter capitalized words in braces so that bibtex will leave them alone. You are encouraged to capitalize other words to give the title full uppers & lowers capitalization, as described in booktitle. - omit qualifiers like "(extended abstract)" - [van Leunen p.170] regardless of the style of the original, use colon to separate title from subtitle (edit if necessary): for example change "Serial science. {I}. Definitions" to "Serial science, {I}: Definitions" - otherwise "correct" only what you're certain the author would want you to - enclose math expressions (including numbers) in $ ... $, and express in tex notation; use {$ ... $} if expression contains capitals type: of techreport or thesis - e.g. "Technical Report" or "Manuscript" or "M.{Phil}. Thesis" - for theses, give the actual degree name, and supplement with keywords "master thesis" or "doctoral thesis" accordingly - if the thesis was distributed as a numbered report, then give its type and number in the note= field - capitalized words after the first need braces in this field update: date and bibliographer corresponding to last change - maintained by the merging software; please don't add, change, or delete url: universal resource locator (from the World-Wide Web project) - meant to express all manner of location information in a standard and machine-interpretable form, so that plain text documents can contain hypertext pointers to resources across the network. A web browser like Netscape can retrieve online items, or where older methods are involved you can retrieve by hand. In both cases the URL is a convenient shorthand. The general syntax is scheme://user:password%host:port/pathname, where the user%, :password, and :port parts are optional to specify values unusual for the particular access scheme. (The URL standard calls for user@, but bibtex treats every @ as beginning a new entry, so we'll have to say user% for now.) Examples of the most common uses: ftp://ftp.cs.usask.ca/pub/geometry/geombib.tar.Z telnet://e-math:e-math%e-math.ams.org gopher://naic.nasa.gov:70/11/government-resources/fbi http://info.cern.ch/hypertext/WWW/MarkUp/Tags.html wais://zenon.inria.fr:210/ra-mime-zenon-inria-fr?RR1882 There are also ways to encode items available through news, afs, prospero, rlogin, tn3270, x500, and whois. The Internet standard for URLs is available as: The Harvard bibtex styles recognize the URL field and print it in reference lists. volume: in journal or multivolume book - @article items with a year specified but lacking a volume will have one of "??" inserted by the merging software year: year of publication - qualifiers like "to appear", "submitted to", "in press" for an emerging entry can go in the year= field, or in pages= or note= if the year is already known, or in comments= to guard them from printing. Such entries should be made with caution because they require fixup later, at which time changes in other info such as authors and title (and thus label) tend to be overlooked. Instead you might consider annotating the entry of an existing appearance. '%' lines before entries: marginal comments wrt bibliography maintenance - use to flag entries with errors you can't fix just now ("% wrong volume number"), or to flag truthful data that may look erroneous ("% yes, ``connexion''") - use sparingly; enduring notes should go in comment= field - the string "###" can be used to call attention where you believe something is missing or wrong. Feel free to fix such entries if you have the correct details handy. SAMPLE ENTRIES Report: @techreport{aa-cfi-89 , author = "P. K. Agarwal and B. Aronov" , title = "Counting facets and incidences" , type = "Report" , number = "90-38" , institution = "DIMACS, Rutgers Univ." , address = "New Brunswick, NJ" , year = 1989 , keywords = "combinatorial geometry, combinatorial complexity, hyperplane arrangements, triangle arrangements" , precedes = "aa-cfi-92" } Thesis: @phdthesis{b-gtfga-80 , author = "K. Q. Brown" , title = "Geometric transforms for fast geometric algorithms" , type = "Ph.{D}. Thesis" , school = "Dept. Comput. Sci., Carnegie-Mellon Univ." , address = "Pittsburgh, PA" , year = 1980 , note = "Report CMU-CS-80-101" , keywords = "doctoral thesis, geometric transformations" , comments = "UMI DA8012772, 154 pp." , update = "93.05 jones" } Article in proceedings: @inproceedings{oy-nubkm-88 , author = "M. H. Overmars and C.-K. Yap" , title = "New upper bounds in {Klee}'s measure problem" , booktitle = "Proc. 29th Annu. IEEE Sympos. Found. Comput. Sci." , year = 1988 , pages = "550--556" , keywords = "$d$-dimensional" , comments = "$O(n^{d/2}\log n)$ time, $O(n)$ space" , precedes = "oy-nubkm-91" , succeeds = "k-cmbcl-77" } Article in proceedings, in series: @incollection{m-pla-88 , author = "S. Meiser" , title = "Point location in arrangements" , booktitle = "Computational Geometry and its Applications" , series = "Lecture Notes Comput. Sci." , volume = 333 , publisher = "Springer-Verlag" , year = 1988 , pages = "71--84" , succeeds = "m-seah-88" } Article in proceedings, in journal: % use an "article" type, and put conference name in note field @article{wa-hsrup-77 , author = "K. Weiler and P. Atherton" , title = "Hidden surface removal using polygon area sorting" , journal = "Comput. Graph." , volume = 11 , number = 2 , year = 1977 , pages = "214--222" , note = "Proc. SIGGRAPH '77" } Article in book: % existing entries use "incollection" or "inproceedings" depending on % whether conversion software thought it recognized a proceedings title. % "inbook" is for citing a portion (like a chapter) of a monograph. @incollection{w-cgmp-85 , author = "S. H. Whitesides" , title = "Computational geometry and motion planning" , editor = "G. T. Toussaint" , booktitle = "Computational Geometry" , publisher = "North-Holland" , address = "Amsterdam, Netherlands" , year = 1985 , pages = "377--427" } Article in journal: @article{gs-ngcha-87 , author = "D. Gries and I. Stojmenovi{\'c}" , title = "A note on {Graham}'s convex hull algorithm" , journal = "Inform. Process. Lett." , volume = 25 , year = 1987 , pages = "323--327" , succeeds = "g-eadch-72" } Book: @book{o-agta-87 , author = "J. O'Rourke" , title = "Art Gallery Theorems and Algorithms" , publisher = "Oxford University Press" , address = "New York, NY" , year = 1987 , keywords = "visibility, decomposition, covering, partition, geometric graphs" } Proceedings (it is encouraged to create a separate entry for recording conference minutae like editors, dates, and location): @proceedings{k-p6ccc-94 , title = "Proc. 6th Canad. Conf. Comput. Geom." , editor = "J. Mark Keil" , publisher = "Dept. Comput. Sci., Univ. Saskatchewan" , address = "Saskatoon, SK" , month = aug , year = 1994 , comments = "C\$40 cheque or money order payable to Univ. Saskatchewan, includes postage" , update = "95.01 smid, 94.09 jones" } MISCELLANEOUS COMMENTS and OPEN PROBLEMS The web search gateways available for this and other bibliographies are very convenient for retrieving entries, but at present lack any means of contributing changes or new material, let alone one as effective (for parties at both ends) as our ftp+edit+diff arrangement. Can anyone point out good setups for doing this? The ideal would be something that could retrieve an entry, change it and send back, with the transaction being recorded in a form suitable for automated processing. Johnson's STOC/FOCS index issued in 1991 contains a wealth of information on papers originally published through those conferences. Look to it first if you need supplementary information on such a paper. Thanks to Robert Freimer, who took the time to incorporate the relevant geometry citations from that book into this bibliography. The bibindex and biblook programs now support macro strings (thanks, Jeff), so we can start using them in the biblio. While they save some space, their real advantage is that people can tailor journal and conference abbreviations to their own taste when printing. A set of these macros needs to be designed for the geometry biblio, probably expanding to our current "normal" abbreviations to start, and perhaps eventually offering terse, normal, and full flavours. To minimize the workload for volunteers, these guidelines eschew redundant precision in entries. So do some journals' house styles. However some researchers prefer their references to always include all available pieces of information like number within volume, day and month, and city. If only bibtex could be told when not to print them, both schools of thought could be accommodated together. A convention like optnumber= might work, if it didn't conflict with emacs bibtex.el's interpretation. The standard bibtex styles use a sort order of author (von surname given jr), year, and then title. We use author (surname given von jr), title, and then year. Our author ordering matches library rules better, and using title before year improves the probability that different appearances of the same paper will be grouped together. The standard bibtex styles have some fixed ideas about how things can be published. For instance, SIGGRAPH conference papers through 1992 appeared in a proceedings which itself appeared as an issue of their newsletter; attempts to enter such items as @inproceedings would not print completely and elicited a warning on the grounds that a proceedings cannot have both volume and issue numbers (i.e. be published as a journal/newsletter issue). Patashnik's Bibtexing notes suggest a Procrustean solution of adjusting the entry's data to fit the fields that do print. So we had to treat such entries as journal articles, with conference title in a note field: @article{awg-psg-78 , author = "P. Atherton and K. Weiler and D. P. Greenberg" , title = "Polygon shadow generation" , journal = "Comput. Graph." , volume = "12" , number = "3" , year = "1978" , pages = "275--281" , note = "Proc. SIGGRAPH '78" } From 1993 on the SIGGRAPH proceedings is a series separate from the newsletter and entries are @inproceedings with a booktitle. Perhaps bibtex might better use a general inclusion field ``in = "siggraph78"'' rather than crossref with its hardwired list of permitted situations, and in any case try harder to make sensible output from the fields it finds. Classic bibtex comes with a limit of 750 entries per bibliography, which is far too small for us. If you want to produce your own hardcopy of significant subsets, you probably need to reconfigure your local bibtex and tex programs. Change files to enlarge the critical parameters in bibtex.web and tex.web are available upon request. (These and other ingredients of the current formatting really ought to be cleaned up and released some day.) Simple parameter fiddling breaks down beyond around 4500 entries when the number of field strings overflows web's 32767 limit on simple macro values. It may be possible to change web someday, but meanwhile the workaround is to tell web some low numbers, then patch the generated C code. You can avoid such issues entirely by using the default Postscript softcopy available from the ftp directory. We should remember that bibtex is not being used by everyone, and researchers still using refer would like some means of back-converting from the current format. A makeshift program bibtex2refer is included in the distribution for anyone wishing to use it. If you do change or improve it please let us know so that we can distribute the improvements too. A program "bibview" that is an X tool for manipulating bibtex databases has been published in comp.sources.x/v18i099. Its README says it "supports the user in making new entries, searching for entries and moving entries from one bib to another. It is possible to work with more than one bib simultaneously. bibview is implemented with Xt and Athena Widgets." bibview is available for ftp from (among other places) and comp.sources.x archive sites. Check archie for a location near you. The Math Reviews index can be searched online by telnet to e-math.ams.org, login e-math, password e-math. Search on author name returns MR numbers only. Finally, what can/should be done to improve the keyword system? Its use at present is de facto optional. People seem to think the list has too many categories to keywordize quickly, but too few to keywordize well. Yet such a vitamin supplement to an entry's indexing is invaluable for searching purposes -- it bridges terminology between the author and reader. Consider the following quotation: "... mathematics is the art of giving the same name to different things .... When the language is well chosen, we are astonished to learn that all the proofs made for a certain object apply immediately to many new objects; there is nothing to change, not even the words, since the names have become the same." -- H. Poincare, Science and Method Is there some way in which we can get that supplementation without unfairly complicating things for the entering bibliographer? One idea is to boil the system down to a smaller (and more easily maintained) key *vocabulary* which we would then be free to twist and combine as appropriate for a given entry. (We would in effect be defining a keywordspeak language, according to Orwell.) This would take a fair amount of time and expertise to design well.