In conjunction with Bill Gasarch's call for including as many links as possible in the bibliographies of our papers (and for us to take some other more important steps towards open access; see also here) I've updated a BibTeX style file, abuser.bst, that I've been using in conjunction with pdflatex and the url package hyperref package in order to make hyperlinks in my papers' bibliographies.

Basically, you use this package very much like the standard BibTeX abbrv style, with the following changes:

• For book series, such as LNCS, it is preferable to use number={nnnn} rather than volume={nnnn} to indicate the number of the book within the series; this frees the volume to indicate the volume of a multivolume work (which might exist within a differently numbered series). The formatting is also a little more compact; e.g. series={LNCS}, number={1234} produces "LNCS 1234" rather than "vol. 1234, other information, LNCS".


• url={...} includes the given url within the formatted reference, as a hyperlink for TeX systems that support hyperlinking.


• eprint={...} includes the arxiv paper with the given eprint number, as a hyperlink for TeX systems that support hyperlinking.


• doi={...} includes the given doi, as a hyperlink for TeX systems that support hyperlinking. If you're not familiar with the doi system, it's a way to provide links to the publisher's web site for journal and conference papers that is supposedly more permanent than just using a url (as publishers often change their url schema but are not supposed to change their dois). So this doesn't do anything about the open access issue but does allow easy hyperlinking of online published content. The doi is usually included somewhere on the publisher's web page for an article but can also be looked up using crossref.org.


• There's a note at the top of the file about Dutch names being sorted correctly (that is, "van Kreveld" should be sorted under "K"), but I no longer remember what I did to achieve this.

If you need something other than abbrv, you're on your own, but I hope this is helpful to at least a few other people than myself.

I'm far behind on my reading, so consider this as the first installment in my attempts to catch up.

( Efficient dual pairs of spanning trees )

( Robust de-anonymization of large datasets )

( Being first and ranking journals )

( Hinged dissections exist )

( Tribes of cubic partial cubes )

Via Dave Bacon: CiteULike. Web site for tagging, rating, and sharing recommendations for academic papers, sort of like del.icio.us.

Has a few of my papers, but among all authors only a handful of papers tagged as computational geometry. Doesn't seem to be great at aggregating duplicates; at least, among their somewhat random looking sample of 18 of my papers, one has two entries with different links. Can generate bibtex from its citations; when I tried it from the computational geometry listing the results were only mildly malformed (used @proceedings for one paper when it should have been @inproceedings, and journal instead of booktitle within that entry), much better than Citeseer's.

Rexa, a U.Mass. project for indexing online research in CS and related fields, just became publically available. Similar to CiteSeer, Google Scholar, and Microsoft Academic Search, but with first class objects for people and grants as well as papers, and using machine learning techniques for the duplicate elimination. Free registration required for use (maybe to prevent spammers from harvesting their data?).

( Read more... )

I added a category in my online pub list for hyperbolic geometry. Not a lot there yet: three research papers (including the new squarepants one), commentary on another paper, and a survey talk (with slides and streaming video). But it's convenient to have it all in one place, and it's an area I'd like to do more in — I don't think it's been very thoroughly explored by the computational geometry community.

To keep this from being content-free, here's a research problem I don't know the answer to: does there exist a polynomial time (1+ε) approximation to the TSP for hyperbolic point sets, for any ε>0? Or to other related approximation problems such as the minimum Steiner tree? An obvious approach would be to try something similar to the approximation for a different problem in my squarepants paper: group the points into bounded-diameter subsets, apply known quadtree-based approximation methods to each group, and connect the groups somehow. It's the "connect the groups somehow" part that I don't see how to do...

Suppose we have a random variable X, which may take on n distinct values 0, 1, 2, ... n-1 with probability p_i for taking value i. If we don't care about the ordering of the values, we may as well assume they are sorted in descending order by probability: p_i > p_i+1. The Shannon entropy of this system, E = -Σ p_i log₂ p_i, gives a lower bound on the expected path length of a binary code for X, that is, a binary tree having X's values at its leaves (in any order).

But there is another formula we can use that defines an entropy based on ranks: R = Σ p_ilog₂(i+1).

( Read more... )

ETA: Why I care about this.

I just reloaded Fano, after updating it to OS X 10.4.5. New content includes citations from Graph Drawing 2005 and SODA 2006, and new spaceships from Evan Clark in several CA rules including Amoeba, Day & Night, Holstein, and Stains.

Just updated the web server on Fano. Some minor additions to the bibliographic data there, but nothing very thorough — I haven't been very well motivated to work on that now that Google scholar has become so much more complete and reliable than Citeseer ever was.

The more interesting addition to the server, to me, is The Seal, a new c/6 diagonal spaceship in Life, discovered by Nicolay Beluchenko. It's not easy to add new entries to the list of known Life spaceship velocities; the most recent one prior to this was the much larger and more complicated 17c/45 Caterpillar last December.

I just discovered that the online journal DM&TCS has an RSS feed for newly published papers. I immediately added it to the arxiv ones in the collection of feeds I check regularly. The other online journals I made a quick check of (JGAA, EJC) don't seem to do this, nor could I find such services for individual journals when I checked ACM and SIAM's sites (but maybe I wasn't looking hard enough?). I, for one, would find such feeds a lot more convenient than the email notifications offered by many publishers. I hope others notice and follow the example of DM&TCS.

Needed to find a 30-year-old paper at the library yesterday, from a reference to "C.R. Acad. Sci. Paris". Fortunately, I remembered what C.R. stood for, but couldn't remember offhand whether the next words would be du or de l'... eventually I just entered "Comptes Rendus" in the catalog, and scanned through the seven pages of results to find one that looked right, Comptes Rendus de l'Académie des Sciences. Or rather, many that looked right, because that name belonged to many different series, none of which seemed to match the one in the citation I was searching for. I almost decided that this meant our library didn't have what I wanted and started to prepare an interlibrary loan request, until I realized that the closest matching entry had a pointer to a previous C.R. series that it continued under a different name. Half a dozen name-change backpointers later, I finally found Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences, with the correct series, from which I found the call numbers to locate it in the stacks. Where all the C.R.s were shelved together, under the same call number, so I again had to scan sequentially through them to locate the correct series again.

From which I conclude that there's a lot to be said for on-line full-text journal archives, and services like ACM Portal and Google Scholar that index them, despite their impermanence compared to paper.

Also that precision and usability are to some extent conflicting goals in bibliography. I mean, who cares whether the word "Hebdomadaires" was in the journal name for some years and not for other years, just let me know where I can find my papers.