As you all might know, in an event sure to get someone a Nobel Peace Prize, the Symposium on Computational Geometry (SoCG) and the Symposium on the Theory of Computing (STOC) will "sympose" together in Boston this year.
As part of this peace offensive designed to unite points and graphs, the combinatorial and the geometric, the Laplacian and the Hilbertian, (someone please stop me now...), there will be a day of overlap between the two conferences. The intention is to have a day of workshops on topics of interest to both communities, as well as two invited talks (by Timothy Chan and Santosh Vempala).
I'm one of the co-organizers of this joint day of workshops (together with Yusu Wang, Chandra Chekuri and Alex Andoni). And I strongly encourage you to consider putting together a proposal for a workshop/tutorial/other event that brings together folks from these communities.
For more details, please visit the workshops page. The deadline for submitting proposals is Feb 22, 2016. Proposals do not need to be very long - they merely need to answer specific questions as detailed in the CFP.
This is a great opportunity to expose the communities to topics that they might not ordinarily bump into, but could enjoy and benefit from. I'm very excited to see what ideas get tossed around, and am looking forward to the event. Kudos to the STOC and SoCG steering committees for making this happen.
Showing posts with label socg. Show all posts
Showing posts with label socg. Show all posts
Thursday, January 07, 2016
Monday, June 09, 2014
A declaration of independence (kind of), and technology-induced disintermediation
Musings on the SoCG move to declare independence of the ACM.
It's a little odd to be sitting in Denmark while high quality rød pølse (with remoulade!) is being made across the world in Kyoto. There's an abysmal lack of blogging/tweeting/facebooking/instagramming/snapchatting/can-I-stop-now-ing from the conference.
Of course following in the lines of the complexity conference, we're attempting to declare our own independence from theEEVVIIL SKELETOR AND HIS MINIONS ACM. Jeff Erickson, our esteeemed grand poobah steering committee chair has put out a series of posts outlining the issues at hand, the history of the matter, and the current status of discussions with SIGACT and ACM. Please visit http://makingsocg.wordpress.com to read, discuss and/or heckle as you see fit.
It might be obvious, but this new wave of devolution is being driven largely by technology - most importantly the existence of LIPIcs. Having a platform for open-access publication with minimal costs exposes as false the claims of institutional providers that they alone can provide the support needed for conferences. In fact, there are a number of related claims that appear to be not true in practice (or at least are not as obviously true as once thought).
* We need the imprimatur of an institutional provider as a signalling mechanism for quality. While it might be too soon to tell if dropping affiliation with established institutions (IEEE or ACM) will affect how publications in a venue will be perceived, there's a lot of confidence in the communities that their long-established reputation will outweigh any loss of prestige.
* Institutional providers provide quality editorial and archival services necessary for a serious venue. I think juxtaposing 'quality' and 'editorial' together with Sheridan Printing might cause my two remaining readers to die of hysterical laughter. But the archival issue is a good one. LIPIcs appears to be funded solidly by the German government for a while, and will take a fixed fee from a conference for publication (capped at 750 €). But the Arxiv was struggling for a while. Should we view the ACM and IEEE as "more likely to last" than any other entity ?
* Institutional providers provide the backing and clout needed for conference organization, hotel bookings and so on. This is another good example of a time-money tradeoff. Organizations like SIAM actually do take over the management of the conference: while the results are not always optimal, there is a clear reduction in hassle for the conference organizers. But organizations like the ACM don't take things over in the same way (and from what I can tell, neither does IEEE). I'm surprised though that there aren't yet lean-and-mean event planning providers that we can just pay money to and make our planning problems go away.
* Institutional providers have the financial wherewithal to manage cycles in revenue streams for a conference. This is another real issue. Conferences that have gone independent have eventually managed to maintain a steady income stream, but theory conferencs are smaller and poorer: it remains to be seen whether we can generate the kind of endowment needed to insulate the community against the natural variation in revenue from year to year.
What's disappointing is that none of this had to play out this way.
It's a little odd to be sitting in Denmark while high quality rød pølse (with remoulade!) is being made across the world in Kyoto. There's an abysmal lack of blogging/tweeting/facebooking/instagramming/snapchatting/can-I-stop-now-ing from the conference.
Of course following in the lines of the complexity conference, we're attempting to declare our own independence from the
It might be obvious, but this new wave of devolution is being driven largely by technology - most importantly the existence of LIPIcs. Having a platform for open-access publication with minimal costs exposes as false the claims of institutional providers that they alone can provide the support needed for conferences. In fact, there are a number of related claims that appear to be not true in practice (or at least are not as obviously true as once thought).
* We need the imprimatur of an institutional provider as a signalling mechanism for quality. While it might be too soon to tell if dropping affiliation with established institutions (IEEE or ACM) will affect how publications in a venue will be perceived, there's a lot of confidence in the communities that their long-established reputation will outweigh any loss of prestige.
* Institutional providers provide quality editorial and archival services necessary for a serious venue. I think juxtaposing 'quality' and 'editorial' together with Sheridan Printing might cause my two remaining readers to die of hysterical laughter. But the archival issue is a good one. LIPIcs appears to be funded solidly by the German government for a while, and will take a fixed fee from a conference for publication (capped at 750 €). But the Arxiv was struggling for a while. Should we view the ACM and IEEE as "more likely to last" than any other entity ?
* Institutional providers provide the backing and clout needed for conference organization, hotel bookings and so on. This is another good example of a time-money tradeoff. Organizations like SIAM actually do take over the management of the conference: while the results are not always optimal, there is a clear reduction in hassle for the conference organizers. But organizations like the ACM don't take things over in the same way (and from what I can tell, neither does IEEE). I'm surprised though that there aren't yet lean-and-mean event planning providers that we can just pay money to and make our planning problems go away.
* Institutional providers have the financial wherewithal to manage cycles in revenue streams for a conference. This is another real issue. Conferences that have gone independent have eventually managed to maintain a steady income stream, but theory conferencs are smaller and poorer: it remains to be seen whether we can generate the kind of endowment needed to insulate the community against the natural variation in revenue from year to year.
What's disappointing is that none of this had to play out this way.
- Take LIPICs for example: they clearly marked out their scope -- indexing, archiving functions and hosting -- while staying away from the more content-driven aspects of the process (editing, proofing etc). This makes a lot of sense, given that everyone who publishes knows how to use LaTeX and style files, but might still not be able to make a web page. Why couldn't the ACM have realized this and provided a slimmed-down publishing service ?
- Why do we go to Microsoft (or Easychair, or hotCRP, or Shai Halevi's software) for our conference submission servers ? If the ACM had provided a service of this kind (or even provided hosting for hotCRP/Shai's software), we'd be happily using it right now, and it could have then tied nicely into Regonline, that ACM already partners with.
- A lot of the current angst seems to have tone as a root cause: a certain feeling about the provider's attitude towards the conference. This is again something that could have been recognized and addressed before things got to this stage.
While it's exciting to be part of the "academic spring" (?), people tend to forget that in all revolutions someone gets hurt, and often things don't get better for a long time. I'm intrigued by our attempt to move towards independence though, and the people involved have thought this through very carefully.
Thursday, December 22, 2011
CGWeek !!!
If you're on the compgeom mailing list, you probably know this already, but if not, read on:
There's an increased interest in expanding the nature and scope of events at SoCG beyond the conference proper. To this end, Joe Mitchell put together a committee titled "CG:APT" (CG: applications, practice and theory) to chalk out a strategy and solicit contributions.
The call for contributions is now out, and the main nugget is this:
Proposals are invited for workshops/minisymposia, or other types of events on topics related to all aspects of computational geometry and its applications. Typical events may feature some number of invited speakers and possibly some number of contributed presentations. Events may feature other forms of communications/presentations too, e.g., via software demos, panel discussions, industry forum, tutorials, posters, videos, implementation challenge, artwork, etc. CG:APT events will have no formal proceedings; optionally, the organizers may coordinate with journals to publish special issues or arrange for other dissemination (e.g., via arXiv, webpages, printed booklets, etc).In other words, anything goes ! (this is an experiment, after all). Topics are essentially anything that might be of interest geometrically in a broad sense (i.e not limited to what might appear at the conference itself).
I'd strongly encourage people to consider putting together a proposal for an event. The procedure is really simple, and only needs a two page proposal containing:
- Title/theme of the workshop/minisymposium/event
- Organizer(s) (name, email)
- Brief scientific summary and discussion of merits (to CG) of the proposed topic.
- A description of the proposed format and agenda
- Proposed duration: include both minimum and ideal; we anticipate durations of approximately a half day (afternoon), with the possibility that some meritorious events could extend across two half-days.
- Procedures for selecting participants and presenters
- Intended audience
- Potential invited speakers/panelists
- Plans for dissemination (e.g., journal special issues)
- Past experience of the organizer(s) relevant to the event
There are many people out there who grumble about how insular the CG community is. Now's your chance to walk into the lion's den (at Chapel Hill) and tell it off :).
Thursday, December 08, 2011
SoCG and ACM: The Results Show
From Mark de Berg:
The bottom row of the table [below] gives the number of votes for each of the three optionsIt will be interesting to see how this plays out.
A. I prefer to stay with ACM.B. If involvement of ACM can be restricted to publishing the proceedings, at low cost for SoCG, then I prefer to stay with ACM; otherwise I prefer to leave ACM.C. I prefer to leave ACM, and organize SoCG as an independent conference with proceedings published in LIPIcs.and it also gives a breakdown of the votes by the number of SoCG’s that the voter attended in the last 10 years.
Based on the result of the Poll, the Steering Committee decided to start negotiating with ACM to see if they can offer SoCG an arrangement in which involvement of ACM is limited primarily to publishing the proceedings, with the possible option for greater involvement if the local organizers request/require it.
Monday, November 21, 2011
On getting rid of ACM affiliation...
As I mentioned earlier, the SoCG steering committee is running a poll on whether to separate SoCG from ACM and run it as an independent symposium with proceedings published by the Dagstuhl LIPIcs series.
At the time I had considered writing a post expressing my own thoughts on the matter, and then promptly forgot about it. The poll is still open (although probably many of you have voted already) and so I thought (with some external nudging :)) that I'd state my position here (one that I summarized in brief for the poll).
If you'd rather not read any more, here's the summary:
At the time I had considered writing a post expressing my own thoughts on the matter, and then promptly forgot about it. The poll is still open (although probably many of you have voted already) and so I thought (with some external nudging :)) that I'd state my position here (one that I summarized in brief for the poll).
If you'd rather not read any more, here's the summary:
I think it's a bad idea.
And here's why
I understand the rationale behind this: it can be a little difficult to work with ACM. ACM does take a contingency fee that increases registration. The cost of proceedings is a significant fraction of the total budget, and the timelines can be a little tricky to work with. These and more are outlined in the poll document, and you can read all the points being made there.
But that's not why I think this is a bad idea (and I do have specific objections to the claims above). I think it's a bad idea because ACM is not just a conference organizing, proceedings publishing enterprise that has bad taste in style files. It's also the home of SIGACT.
For better or worse, SIGACT is the flagship representative body for theoretical computer science in the US. General theory activities like the Theory Matters wiki and the SIGACT committee for the advancement of theoretical computer science were jump-started by SIGACT. Association with SIGACT means that the work you do is 'theoryCS (A)' in some shape of form.
If you're doing geometry in the US, then affiliation with SIGACT is not a bad thing. It means that you're part of the larger theory community. It means that when the theory community makes pitches to the NSF to get more funding for theory research, you're included. It also helps because there aren't other communities (SIGGRAPH?) ready to absorb geometry into their fold.
While de-linking from ACM doesn't mean that we turn in our 'theory badges', it doesn't help the already fraught relationship between computational geometry and the larger theory community. And while the relationship with ACM is not crucial to the survival of the geometry community in the US, being part of a larger theory community that speaks the same language is crucial.
p.s The center of mass in CG is closer to Europe than many might realize. I understand that our European colleagues could care less about US funding and community issues, which is fair for them. But this matter affects US-resident folks more than ACM's surcharges affect the European researchers, and our community isn't so big that we can withstand shocks to one side of it.
Friday, November 04, 2011
SoCG and ACM: Relationship status - Complicated.
Mark de Berg (secretary of the SoCG steering committee), sent out an email to the compgeom mailing list that starts:
Since its start 27 years ago, SoCG has always been affiliated to ACM. This means that the proceedings are published by ACM, and that the symposium is organized “sponsored by ACM” (more precisely, sponsored by ACM SIGACT & ACM SIGGRAPH) or “in cooperation with ACM”. The latter happened only a couple of times, namely when SoCG was in Korea in 2007 and when it was in Denmark in 2009. Being affiliated to ACM has certain advantages, but also certain disadvantages, as detailed below. Hence, at the business meeting of this year’s SoCG in Paris, an alternative was discussed: organizing SoCG as an independent symposium, with the proceedings being published by Dagstuhl in their LIPIcs series (see below). A straw poll was taken, and the vast majority of the participants wanted the Steering Committee to investigate this issue further, which we do through this opinion poll. We hope you want to participate in this important poll.
If you have an interest in how the relationship between SoCG and the ACM continues (or doesn't), I'd strongly encourage you to participate in the poll. The poll documents
Wednesday, October 12, 2011
SoCG 2012 CFP
It's out: !! Please also note the new workshop CG:APT (highlighted) that will attempt to expand the scope of the conference and bring in more applied work.I'm looking forward to hearing more about it.
The Twenty-Eighth Annual Symposium on Computational Geometry will be held in University of North Carolina, Chapel Hill. We invite submissions of high-quality papers that describe original research on issues related to computational problems arising from geometric considerations. We also invite submissions of original videos and multimedia on these same themes. This year, SoCG will be collocated with a workshop, Computational Geometry: Applications, Practice, and Theory (CG:APT), whose call for submissions (due Feb 27) will be distributed separately.
The topics of the SoCG 2012 Symposium reflect the rich diversity of research interests in computational geometry. They are intended to highlight both the depth and scope of computational geometry, and to invite fruitful interactions with other disciplines. Topics of interest include, but are not limited to:
Important Dates
November 22, 2011: Paper titles and abstracts (at most 300 words) due (23:59, Honolulu time)
December 2, 2011: Paper submissions due (23:59, Honolulu time)
February 17, 2012: Notification of acceptance/rejection of papers
February 27, 2012 : Submissions of videos and multimedia due (23:59, Honolulu Time)
March 8, 2012: Notification of acceptance/rejection of video/multimedia
March 22, 2012: Camera-ready versions due for papers and video/multimedia abstracts
April 26, 2012: Final versions of video/multimedia due
June 17-20, 2012 (tentative): Symposium in Chapel Hill, North Carolina
We invite submissions of high-quality papers describing original research on geometric algorithms and data structures, their mathematical foundations and correctness, their implementation, and their applications.
Final versions of accepted papers will be published by ACM in the symposium proceedings. Proceedings will be distributed to symposium participants and will also be available from ACM for purchase and through the ACM digital library. An author of each accepted paper will be expected to attend the Symposium and give a presentation (approximately 20 minutes) of the paper. Authors of a selection of papers from the conference will be invited to submit extended versions of their papers to a special issue of one or more journals. This year we also plan to confer two Best Paper Awards, and a Best Student Presentation Award. The Student Presentation award will be based on the quality of the presentation of a paper by a student during the conference.
Paper Submission
All submissions should be made electronically; see the EasyChair SoCG2012 web page https://www.easychair.org/conferences/?conf=socg2012 for detailed submission instructions (to be available shortly). If electronic submission is not feasible, please contact the program committee chairs, Tamal Dey and Sue Whitesides, well in advance of the submission deadlines.
Submission Guidelines
Papers should be submitted in the form of an extended abstract, which begins with the title and abstract page that contains the title of the paper, each author's name, affiliation, and e-mail address followed by a short abstract. The main body of the extended abstract should begin with a precise statement of the problem considered, a succinct summary of the results obtained (emphasizing the significance, novelty, and potential impact of the research), and a clear comparison with related work. The remainder of the extended abstract should provide sufficient detail to allow the program committee to evaluate the validity, quality, and relevance of the contribution. Clarity of presentation is very important; the whole extended abstract should be written carefully, taking into consideration that it will be read and evaluated by both experts and non-experts, often under tight time constraints.
Submissions should be typeset in single column format, using 11-point or larger font, with at least 1 inch/2.54 cm margins and single line spacing. Excluding the title page and bibliography, the extended abstract must not exceed 10 pages. Submissions deviating from these guidelines risk rejection without consideration of their merits.
All necessary details to verify the results must be provided. If they cannot fit within the 10-page limit, a clearly marked appendix containing omitted details should be included. Appendices are not counted in the 10 page limit, so while they may serve as a reference, they will be read by the program committee members at their discretion. The paper excluding the appendix should clearly describe the results and the approach to achieve them, and give sufficient confidence for their validity. The appendix should then give all the necessary details to verify correctness.
Anticipating the usual high overall quality of submissions, the program committee intends to interpret the scope of the conference broadly, and will seriously consider all papers that are of significant interest to our research community.
Authors must submit the title and an abstract (at most 300 words) of their papers by November 22, 2011. This pre-submission will be used to help make program committee reading assignments. Extended abstracts must be received by December 2, 2011 (23:59, Honolulu time). There will be no extension of these deadlines; late submissions will not be considered. Authors will be notified of acceptance or rejection by February 17, 2012. The final proceedings papers must be formatted in accordance with ACM proceedings guidelines; LaTeX style files will be made available to authors of accepted papers.
Concurrent submission of the same (or essentially the same) abstract to SoCG and to another conference with published proceedings is not allowed. An extended abstract of a paper that is under journal review, or scheduled for publication in a journal after June 2012, may be submitted, when it is clear that the extended abstract differs substantially from the journal version. In such cases, the authors must include the journal version in an appendix that clearly identifies the status of the journal submission.
Program Committee
Video and multimedia presentations are sought for the 21st Annual Video and Multimedia Review of Computational Geometry, to accompany the 28th Annual Symposium on Computational Geometry. This review showcases the use of visualization in computational geometry for exposition and education, for visual exploration of geometry in research, and as an interface and a debugging tool in software development. Algorithm animations, visual explanations of structural theorems, descriptions of applications of computational geometry, and demonstrations of software systems are all appropriate.
Three to five minutes is ideal for most presentations; eight minutes is the upper limit. Accepted video and multimedia presentations will have an abstract in the published conference proceedings; video/multimedia authors will have an opportunity to present their work at the Symposium during a dedicated video session. Accepted presentations will be available online in various formats in a web proceedings. See http://www.computational-geometry.org/ for examples of previous years' proceedings.
Submissions of video clips in QuickTime or MPEG-4 compressed formats (e.g., XviD or DivX version 6) are encouraged. We also encourage submissions of Macromedia Flash, Java applets, and limited forms of other multimedia or software. These formats must come with a script that will allow them to be distributed in both interactive and canned Quicktime or MPEG video formats. In case of doubt, please email the Video and Multimedia Program chair.
Each submission should include a one or two-page description of the material shown in the presentation, and where applicable, the techniques used in the implementation. The final two-page descriptions must be formatted according to the guidelines for proceedings. LaTeX style files will be provided to authors of accepted presentations.
Submissions should be deposited online where they are accessible through the web or via FTP. Send email to the Video/Multimedia committee chair, Christian Knauer by 23:59 Honolulu Time, Monday, February 27, 2012, with the following information: the names and institutions of the authors, the email address of the corresponding author, and instructions for downloading the submission. For ease of sharing and viewing, we encourage (but do not require) that each submission be uploaded to YouTube, and that the corresponding URL be included with the submission.
We explicitly encourage video/multimedia submissions that support papers submitted to the Symposium. Submitted papers and associated video/multimedia submissions will be treated entirely separately by the respective committees: acceptance or rejection of one will not influence acceptance or rejection of the other.
Authors will be notified of acceptance or rejection, and given reviewers' comments by March 8, 2012. For each accepted submission, the final version of the 2-page textual description will be due by March 22, 2012 (electronically) for inclusion in the proceedings. Final versions of accepted video/multimedia presentations will be due April 26, 2012 in the best format available.
Important Dates
Feb. 27, 2012: Video and Multimedia submissions due
Mar. 8, 2012: Notification for Video/MM submissions (23:59 Honolulu time)
Mar. 22, 2012: Camera-ready video/MM abstracts due
Apr. 26, 2012: Final versions of video/MM presentations due
Video and Multimedia Presentation Program Committee
SOCG 2012 Local Arrangements
Jack Snoeyink, Chair
28th Annual Symposium on Computational Geometry (SoCG 2012)
June 17-20, 2012 (tentative)
University of North Carolina, Chapel Hill
In cooperation with ACM SIGACT and SIGGRAPH
The Twenty-Eighth Annual Symposium on Computational Geometry will be held in University of North Carolina, Chapel Hill. We invite submissions of high-quality papers that describe original research on issues related to computational problems arising from geometric considerations. We also invite submissions of original videos and multimedia on these same themes. This year, SoCG will be collocated with a workshop, Computational Geometry: Applications, Practice, and Theory (CG:APT), whose call for submissions (due Feb 27) will be distributed separately.
The topics of the SoCG 2012 Symposium reflect the rich diversity of research interests in computational geometry. They are intended to highlight both the depth and scope of computational geometry, and to invite fruitful interactions with other disciplines. Topics of interest include, but are not limited to:
- design, analysis, and implementation of geometric algorithms and data structures; lower bounds on the computational complexity of geometric problems;
- mathematical, numerical, algebraic, and experimental issues arising in geometric algorithms and heuristics; discrete and combinatorial geometry; computational topology;
- novel applications of computational geometry in computer graphics, geometric modeling, computer-aided design and manufacturing, scientific computing, geographic information systems, database systems, robotics, computational biology, machine learning, sensor networks, biomedical imaging, combinatorial optimization, statistical analysis, discrete differential geometry, theoretical computer science, graph drawing, pure mathematics, and other fields; novel problems in computational geometry arising from these fields.
November 22, 2011: Paper titles and abstracts (at most 300 words) due (23:59, Honolulu time)
December 2, 2011: Paper submissions due (23:59, Honolulu time)
February 17, 2012: Notification of acceptance/rejection of papers
February 27, 2012 : Submissions of videos and multimedia due (23:59, Honolulu Time)
March 8, 2012: Notification of acceptance/rejection of video/multimedia
March 22, 2012: Camera-ready versions due for papers and video/multimedia abstracts
April 26, 2012: Final versions of video/multimedia due
June 17-20, 2012 (tentative): Symposium in Chapel Hill, North Carolina
Call for Papers
We invite submissions of high-quality papers describing original research on geometric algorithms and data structures, their mathematical foundations and correctness, their implementation, and their applications.
Final versions of accepted papers will be published by ACM in the symposium proceedings. Proceedings will be distributed to symposium participants and will also be available from ACM for purchase and through the ACM digital library. An author of each accepted paper will be expected to attend the Symposium and give a presentation (approximately 20 minutes) of the paper. Authors of a selection of papers from the conference will be invited to submit extended versions of their papers to a special issue of one or more journals. This year we also plan to confer two Best Paper Awards, and a Best Student Presentation Award. The Student Presentation award will be based on the quality of the presentation of a paper by a student during the conference.
Paper Submission
All submissions should be made electronically; see the EasyChair SoCG2012 web page https://www.easychair.org/conferences/?conf=socg2012 for detailed submission instructions (to be available shortly). If electronic submission is not feasible, please contact the program committee chairs, Tamal Dey and Sue Whitesides, well in advance of the submission deadlines.
Submission Guidelines
Papers should be submitted in the form of an extended abstract, which begins with the title and abstract page that contains the title of the paper, each author's name, affiliation, and e-mail address followed by a short abstract. The main body of the extended abstract should begin with a precise statement of the problem considered, a succinct summary of the results obtained (emphasizing the significance, novelty, and potential impact of the research), and a clear comparison with related work. The remainder of the extended abstract should provide sufficient detail to allow the program committee to evaluate the validity, quality, and relevance of the contribution. Clarity of presentation is very important; the whole extended abstract should be written carefully, taking into consideration that it will be read and evaluated by both experts and non-experts, often under tight time constraints.
Submissions should be typeset in single column format, using 11-point or larger font, with at least 1 inch/2.54 cm margins and single line spacing. Excluding the title page and bibliography, the extended abstract must not exceed 10 pages. Submissions deviating from these guidelines risk rejection without consideration of their merits.
All necessary details to verify the results must be provided. If they cannot fit within the 10-page limit, a clearly marked appendix containing omitted details should be included. Appendices are not counted in the 10 page limit, so while they may serve as a reference, they will be read by the program committee members at their discretion. The paper excluding the appendix should clearly describe the results and the approach to achieve them, and give sufficient confidence for their validity. The appendix should then give all the necessary details to verify correctness.
Anticipating the usual high overall quality of submissions, the program committee intends to interpret the scope of the conference broadly, and will seriously consider all papers that are of significant interest to our research community.
Authors must submit the title and an abstract (at most 300 words) of their papers by November 22, 2011. This pre-submission will be used to help make program committee reading assignments. Extended abstracts must be received by December 2, 2011 (23:59, Honolulu time). There will be no extension of these deadlines; late submissions will not be considered. Authors will be notified of acceptance or rejection by February 17, 2012. The final proceedings papers must be formatted in accordance with ACM proceedings guidelines; LaTeX style files will be made available to authors of accepted papers.
Concurrent submission of the same (or essentially the same) abstract to SoCG and to another conference with published proceedings is not allowed. An extended abstract of a paper that is under journal review, or scheduled for publication in a journal after June 2012, may be submitted, when it is clear that the extended abstract differs substantially from the journal version. In such cases, the authors must include the journal version in an appendix that clearly identifies the status of the journal submission.
Program Committee
- Pankaj Agarwal(Duke University)
- Dominique Attali (Gipsa-Lab, Grenoble)
- Gill Barequet (Technion-Israel Institute of Technology)
- Mark de Berg (Technische Universiteit, Eindhoven)
- Danny Chen (University of Notre Dame)
- Tamal Dey (The Ohio State University) (co-chair)
- Vida Dujmović (Carleton University)
- David Eppstein (University of California, Irvine)
- Leonidas Guibas (Stanford University)
- Sylvain Lazard (INRIA, Nancy Grand Est)
- Dinesh Manocha (The University of North Carolina at Chapel Hill)
- Steve Oudot (INRIA Saclay)
- Konrad Polthier (Freie Universität Berlin)
- Edgar Ramos (Universidad Nacional de Colombia, Medellín)
- Jian Sun (Tsinghua University)
- Takeshi Tokuyama (Tohoku University)
- Yusu Wang (The Ohio State University)
- Max Wardetzky (University of Göttingen)
- Sue Whitesides (University of Victoria, British Columbia) (co-chair)
Call for Video and Multimedia Presentations
Video and multimedia presentations are sought for the 21st Annual Video and Multimedia Review of Computational Geometry, to accompany the 28th Annual Symposium on Computational Geometry. This review showcases the use of visualization in computational geometry for exposition and education, for visual exploration of geometry in research, and as an interface and a debugging tool in software development. Algorithm animations, visual explanations of structural theorems, descriptions of applications of computational geometry, and demonstrations of software systems are all appropriate.
Three to five minutes is ideal for most presentations; eight minutes is the upper limit. Accepted video and multimedia presentations will have an abstract in the published conference proceedings; video/multimedia authors will have an opportunity to present their work at the Symposium during a dedicated video session. Accepted presentations will be available online in various formats in a web proceedings. See http://www.computational-geometry.org/ for examples of previous years' proceedings.
Submissions of video clips in QuickTime or MPEG-4 compressed formats (e.g., XviD or DivX version 6) are encouraged. We also encourage submissions of Macromedia Flash, Java applets, and limited forms of other multimedia or software. These formats must come with a script that will allow them to be distributed in both interactive and canned Quicktime or MPEG video formats. In case of doubt, please email the Video and Multimedia Program chair.
Each submission should include a one or two-page description of the material shown in the presentation, and where applicable, the techniques used in the implementation. The final two-page descriptions must be formatted according to the guidelines for proceedings. LaTeX style files will be provided to authors of accepted presentations.
Submission
Submissions should be deposited online where they are accessible through the web or via FTP. Send email to the Video/Multimedia committee chair, Christian Knauer by 23:59 Honolulu Time, Monday, February 27, 2012, with the following information: the names and institutions of the authors, the email address of the corresponding author, and instructions for downloading the submission. For ease of sharing and viewing, we encourage (but do not require) that each submission be uploaded to YouTube, and that the corresponding URL be included with the submission.
We explicitly encourage video/multimedia submissions that support papers submitted to the Symposium. Submitted papers and associated video/multimedia submissions will be treated entirely separately by the respective committees: acceptance or rejection of one will not influence acceptance or rejection of the other.
Authors will be notified of acceptance or rejection, and given reviewers' comments by March 8, 2012. For each accepted submission, the final version of the 2-page textual description will be due by March 22, 2012 (electronically) for inclusion in the proceedings. Final versions of accepted video/multimedia presentations will be due April 26, 2012 in the best format available.
Important Dates
Feb. 27, 2012: Video and Multimedia submissions due
Mar. 8, 2012: Notification for Video/MM submissions (23:59 Honolulu time)
Mar. 22, 2012: Camera-ready video/MM abstracts due
Apr. 26, 2012: Final versions of video/MM presentations due
Video and Multimedia Presentation Program Committee
- Helmut Alt -Freie Universität Berlin
- Sandor Fekete - TU Braunschweig
- Panos Giannopoulos - Universität Bayreuth
- Xavier Goaoc - INRIA Nancy Grand Est
- Rolf Klein - Universität Bonn
- Christian Knauer (chair) - Universität Bayreuth
- Joseph S. B. Mitchell - SUNY Stony Brook
- Bettina Speckmann - TU Eindhoven
- Fabian Stehn - Universität Bayreuth
- Alexander Wolff - Universität Würzburg
SOCG 2012 Local Arrangements
Jack Snoeyink, Chair
Sunday, March 13, 2011
SoCG 2011: New Venue and hotel recommendations
I had mentioned a few days ago that the SoCG 2011 venue was set to change. The new venue has been announced: it's at UICP, right near the Eiffel tower (which I might add, looks like a snapshot of a negatively curved mesh). There are hotel recommendations as well, but it sounds as if even if you made reservations at a hotel near the previous location, it won't be too much trouble to get around. Aah, the joys of efficient public transport.
In any case, do those registrations now, and get those hotel rooms booked. As a former organizer, I know how nerve-wracking it can be while you wait for the registration count to climb towards respectability :).
In any case, do those registrations now, and get those hotel rooms booked. As a former organizer, I know how nerve-wracking it can be while you wait for the registration count to climb towards respectability :).
Tuesday, February 22, 2011
If you're making plans for SoCG 2011...
Don't. Yet.
Important notice: in order to solve some logistical issues and to reduce the costs, the exact location of the conference is likely to change within the next two weeks. The final location (still downtown Paris) will be specified here by March 8th at the latest. Please accept our apologies for the inconvenience, and feel free to contact us if you have any questions or concerns.Although if you don't need to find a hotel right next to the conference venue, this will not affect you.
Tuesday, February 08, 2011
SoCG Videos Call
You drew all those snazzy diagrams using your fancy Mac drawing program. Now it's time to make some videos:
Video and multimedia presentations are sought for the 20th Annual Video and Multimedia Review of Computational Geometry, to accompany the 27th Annual Symposium on Computational Geometry in Paris, France. This review showcases the use of visualization in computational geometry for exposition and education, for visual exploration of geometry in research, and as an interface and a debugging tool in software development. Algorithm animations, visual explanations of structural theorems, descriptions of applications of computational geometry, and demonstrations of software systems are all appropriate.
Three to five minutes is ideal for most presentations; eight minutes is the upper limit. Accepted video and multimedia presentations will have an abstract in the published conference proceedings; video/multimedia authors will have an opportunity to present their work at the Symposium during a dedicated video session. Accepted presentations will be available online in various formats in a web proceedings. See http://www.computational-geometry.org/ for examples of previous years' proceedings.
Send email to the Video/Multimedia committee chair, Jonathan Shewchuk, jrs@cs.berkeley.edu by 23:59 Pacific Standard Time, Friday, February 18, 2011, with the following information: the names and institutions of the authors, the email address of the corresponding author, and instructions for downloading the submission.
Tuesday, October 19, 2010
SoCG deadline, and a new NSF rule
SoCG CFP is out:
In unrelated news, the NSF appears to have a new policy for 'data management' and will require a new supplementary document to this effect. Note that since it's a mandatory document, it will affect theory proposals as well:
- Titles/abstracts: Nov 22
- Papers: Dec 1
- Notification: Feb 14
- June 13-15, conference.
Anticipating the usual high overall quality of submissions, the programMy optimistic side is excited by this, and I really hope we can see more papers on diverse topics. My pessimistic side is grumping "yes, that means any papers that aren't mine". sigh...
committee intends to accept more papers than was typical in previous years. Also, we intend to interpret the scope of the conference broadly, and will accept all papers of high quality that are of significant interest to our research community. The conference venue in Paris is attractive and allows a bigger conference than previous years.
In unrelated news, the NSF appears to have a new policy for 'data management' and will require a new supplementary document to this effect. Note that since it's a mandatory document, it will affect theory proposals as well:
Plans for data management and sharing of the products of research. Proposals must include a supplementary document of no more than two pages labeled “Data Management Plan.” This supplement should describe how the proposal will conform to NSF policy on the dissemination and sharing of research results (see AAG Chapter VI.D.4), and may include:
* The types of data, samples, physical collections, software, curriculum materials, and other materials to be produced in the course of the project
* The standards to be used for data and metadata format and content (where existing standards are absent or deemed inadequate, this should be documented along with any proposed solutions or remedies)
* Policies for access and sharing including provisions for appropriate protection of privacy, confidentiality, security, intellectual property, or other rights or requirements
* Policies and provisions for re-use, re-distribution, and the production of derivatives
* Plans for archiving data, samples, and other research products, and for preservation of access to them
Wednesday, May 12, 2010
SoCG 2010: Come one, come all :)
There's about a month left to go for SoCG, and I just returned from a walk through at Snowbird. Surprisingly, it was still snowing - the ski season has wound down though. Most of the snow will disappear by early June - we're seeing the last confused weather oscillations right now before the steady increase in temperature.
We went up there to check out the layout of the room(s) for the conference - the main conference room is nice and large, and the parallel session room is pretty big as well, there'll be wireless access throughout (with a code), and there's a coffee place right next to the rooms. There are nice balconies all around, and of course you can wander around outside as well.
Registrations have been trickling in, a little slower than my (increasingly) gray hair would like. If you haven't yet registered, consider this a gentle reminder :). It helps to have accurate numbers when estimating food quantities and number of proceedings etc.
See you all in a month !
We went up there to check out the layout of the room(s) for the conference - the main conference room is nice and large, and the parallel session room is pretty big as well, there'll be wireless access throughout (with a code), and there's a coffee place right next to the rooms. There are nice balconies all around, and of course you can wander around outside as well.
Registrations have been trickling in, a little slower than my (increasingly) gray hair would like. If you haven't yet registered, consider this a gentle reminder :). It helps to have accurate numbers when estimating food quantities and number of proceedings etc.
See you all in a month !
Saturday, May 01, 2010
SoCG 2010 Early Registration Deadine
SoCG 2010 Early Registration deadline coming up tomorrow night. Make sure you register so you don't pay the full price. Also make sure to lock down your hotel reservations.
Friday, June 19, 2009
SoCG 2009: Local search, geometric approximations and PTASs
I planned on this post coming a lot sooner after the last three, but got caught up in my own version of a Danish flu. sigh....
So let's get greedy. In the last post, I talked about new developments in the epsilon-net route to approximating covering/hitting problems. The problem with these approaches though (as Saurabh Ray pointed out) is that they (at best) get you to "some" constant. They don't get you down to a specific constant (unless you can really optimize the net-construction) and they certainly don't give you a PTAS.
So what's a poor approximator to do if their livelihood depends on getting a 1+epsilon-approximation ? Two papers at SoCG 2009 answer this question independently using essentially the same idea, and there's already a third paper that applies this idea as well. You know what they say: "three applications doth a general technique make" (or at least they should say it !), and the technique is so neat that I thought I'd spend some time outlining the basic principle.
But first, a detour. What follows is my own take on the underlying argument, and I'm the only one responsible for all the inaccuracies in interpretation and exposition. Consider the problem of computing a maximum cardinality matching in a bipartite graph. As we all know, this can solved using a max-flow algorithm. A well-known "spin" on this result is the following:
Mustafa and Ray apply this idea to get a PTAS for hitting set problems. Specifically, they show that for r-admissible regions in the plane and for halfspaces in R^3, the hitting set problem admits a PTAS that runs in time O(mn^(1/eps^2)) (m: number of regions, n: number of points). A collection of regions in the plane is r-admissible if any pair intersect in at most r points, and the differences are connected (these are often called non-piercing collections for that reason).
Chan and Har-Peled use the idea to get a PTAS for max-independent-set problems for pseudo-disks in the plane (which are 2-admissible). Their running time is similar.
Both papers run the following algorithm, parametrized by a number b. Take any feasible solution, and call it L. Now check all sets that differ from L in at most b places and see if any of them can be used to improve the quality of L by at least one unit. If so, make the swap and repeat. This process will terminate in at most n steps, and at each stage, you need to do a search over at most n^b sets. We'll call such a solution "b-local"
The idea that roughly governs both analyses is this: Consider the solution you're currently at (let's call it red) and the optimal solution (color it blue). Think of building a bipartite graph (this works slightly differently for the different problems) which contains the red and blue objects as vertices, and connects two (differently colored) objects by an edge if there's a range that contains both (for the hitting set problem) or if they intersect (for the MIS) (call this a 'locality property' as Mustafa and Ray do) Then they show some things:
An upcoming paper by Gibson, Kanade, Krohn and Varadarajan applies the same idea for the 1.5D terrain guarding problem (one of the few nontrivial art gallery problems that has yielded to approximation attacks). They produce a planar graph that satisfies the locality property, and then apply the rest of the local search machinery as before. What's neat is that the machinery really does apply just as before: "all they have to do" (and I'm not trying to minimizing the effort here, just pointing out the smoothness of the technique) is construct the planar graph.
Some thoughts:
So let's get greedy. In the last post, I talked about new developments in the epsilon-net route to approximating covering/hitting problems. The problem with these approaches though (as Saurabh Ray pointed out) is that they (at best) get you to "some" constant. They don't get you down to a specific constant (unless you can really optimize the net-construction) and they certainly don't give you a PTAS.
So what's a poor approximator to do if their livelihood depends on getting a 1+epsilon-approximation ? Two papers at SoCG 2009 answer this question independently using essentially the same idea, and there's already a third paper that applies this idea as well. You know what they say: "three applications doth a general technique make" (or at least they should say it !), and the technique is so neat that I thought I'd spend some time outlining the basic principle.
But first, a detour. What follows is my own take on the underlying argument, and I'm the only one responsible for all the inaccuracies in interpretation and exposition. Consider the problem of computing a maximum cardinality matching in a bipartite graph. As we all know, this can solved using a max-flow algorithm. A well-known "spin" on this result is the following:
Suppose we construct a max flow F_k using augmenting paths of length at most 2k+1. Then OPT <= (1 + 1/(k+1)) F_kOr in other words, F_k is a 1 + 1/(k+1) approximation to the true answer. The proof is fairly easy: consider any augmenting path of length at least 2k+3 that could increase the total matching size. Because we've tried all augmenting paths of length 2k+1, it must be that this path alternates between OPT (red) and algorithm (blue) edges, starting and ending in a red edge. In other words, if X is the number of blue edges along this path, then 2X+1= 2k+3, and X = k+1. This means that the number of optimal edges is at most (1 + 1/(k+1)) times the number of algorithm edges. Note that all augmenting paths must be disjoint, so some algebra yields the above result.
Another way of viewing the above fact about alternation is that if we think of the edges as vertices of a bipartite graph, (colored as the edges were), then each red set is adjacent to a reasonable number of blue vertices (in fact if this were not the case, the analysis would break). The edge-disjointness then allows us to scale things up to the entire graph
Notice that the process of generating longer and longer augmenting paths can be viewed as a local search operation. Starting from a given path, we modify it by constructing an alternating path using the current edges.In other words, we're able to make claims about local search yielding optimal solutions because we can control the way OPT interacts with the results of the algorithm, with the interaction parametrized by the "degree of locality".
Now let's return to the papers, keeping this in mind.
Mustafa and Ray apply this idea to get a PTAS for hitting set problems. Specifically, they show that for r-admissible regions in the plane and for halfspaces in R^3, the hitting set problem admits a PTAS that runs in time O(mn^(1/eps^2)) (m: number of regions, n: number of points). A collection of regions in the plane is r-admissible if any pair intersect in at most r points, and the differences are connected (these are often called non-piercing collections for that reason).
Chan and Har-Peled use the idea to get a PTAS for max-independent-set problems for pseudo-disks in the plane (which are 2-admissible). Their running time is similar.
Both papers run the following algorithm, parametrized by a number b. Take any feasible solution, and call it L. Now check all sets that differ from L in at most b places and see if any of them can be used to improve the quality of L by at least one unit. If so, make the swap and repeat. This process will terminate in at most n steps, and at each stage, you need to do a search over at most n^b sets. We'll call such a solution "b-local"
The idea that roughly governs both analyses is this: Consider the solution you're currently at (let's call it red) and the optimal solution (color it blue). Think of building a bipartite graph (this works slightly differently for the different problems) which contains the red and blue objects as vertices, and connects two (differently colored) objects by an edge if there's a range that contains both (for the hitting set problem) or if they intersect (for the MIS) (call this a 'locality property' as Mustafa and Ray do) Then they show some things:
- This graph is planar
- It "expands": neighborhoods of blue sets of size at most b are large
- As a consequence of 1,2, the size of the blue set is upper bounded by (1+1/sqrt(b))(size of red set)
An upcoming paper by Gibson, Kanade, Krohn and Varadarajan applies the same idea for the 1.5D terrain guarding problem (one of the few nontrivial art gallery problems that has yielded to approximation attacks). They produce a planar graph that satisfies the locality property, and then apply the rest of the local search machinery as before. What's neat is that the machinery really does apply just as before: "all they have to do" (and I'm not trying to minimizing the effort here, just pointing out the smoothness of the technique) is construct the planar graph.
Some thoughts:
- There's some room for improvement in the running time perhaps, at least down to a linear dependence on 1/epsilon in the exponent. We can't get a poly dependence because of strong-NP-completeness
- I don't think the weighted versions of these problems would fall to the same "trick": indeed the Chan-Har-Peled paper considers a neat LP-based approach for the weighted MIS.
Saturday, June 13, 2009
SoCG 2009: Epsilon-nets and covering/hitting problems.
The 30,000 horsepower engine of approximation algorithms is linear programming. The fact that an LP gives you a bound on the cost of an NP-hard problem has been the major force behind ever more sophisticated methods for proving approximation guarantees.
Ironically enough, given the geometric nature of an LP, this engine has not been particularly useful for geometric approximation problems. The high level reason (somewhat over-simplified) is that it is generally hard to encode specifics about geometry in a linear program. What this means is that (for example) if you want to solve a geometric covering problem and can't encode the geometry in your LP, you're stuck with the log n approximation that combinatorial set cover gives you, inspite of the fact that there are numerous examples of problems where throwing geometry in actually improves the approximation bound considerably.
To put it mildly, this is a pain in the neck. It basically means that you have to design methods that work for a specific problem, and there are only a few general purpose techniques available, many of them outlined in this survey.
But if your problem can be framed as a covering/hitting problem, then there's a general body of work that has provided better and better results, (and for an added bonus, actually has an LP-formulation). The story dates back to a paper on iterative reweighting by Clarkson, and actually goes back even earlier if you jump to the ML literature: Arora, Hazan and Kale have a nice survey on this general approach.
But I digress: the paper by Bronnimann and Goodrich put the technique in the language we're familiar with today: in short,
Given a range space that admits epsilon-nets of size (1/epsilon)f(1/epsilon), you can solve the hitting set problem to an approximation of f(OPT).
In particular, range spaces that admit epsilon-nets of size 1/epsilon admit constant-factor approximations for the hitting set problem. This led to a "formula" for approximating these problems: find an epsilon-net of an appropriate size, and declare victory. There's been much work on constructing epsilon-nets since then, partly motivated by this.
Another angle to this story was put forward by Clarkson and Varadarajan in their 2005 SoCG paper: the brief summary from that paper was:
Given a range space in which you can bound the complexity of the union of a random subcollection of size r by rf(r), you can find an epsilon net of size (1/epsilon)f(1/epsilon).
This approach gave another tool for finding good approximations for covering problems (and in particular gave a nice constant factor approximation for a thorny guarding problem).
At SoCG 2009, Kasturi Varadarajan presented an improved bound along these lines: his main result improves the transfer complexity: modulo some technical details,
Given a range space in which you can bound the complexity of the union of a random subcollection of size r by rf(r), you can find an epsilon net of size (1/epsilon)log f(1/epsilon).
Although this doesn't improve results in the constant factor regime, where f() is a constant, it makes a significant difference when f() is non-constant.
The interesting story here is that Kasturi's result was simultaneous with another paper by Aronov, Ezra, and Sharir that just appeared in STOC 2009. They get the same bound without the technical details that limit his result, however their methods are quite different.
Returning to LPs, what I failed to mention is that the epsilon-net construction technique used by Bronnimann and Goodrich can be seen as a byproduct of an LP-algorithm, as was shown by Even, Rawitz and Shahar, and Philip Long before that (thanks, Sariel)
SoCG 2009: A neat lower bound example
I've had a number of posts queued up to write (for those who ask me "how do you get the time?", the answer is sometimes, "I don't !"). This SoCG was full of really interesting papers, and even collections of papers that together moved our understanding forward in very nontrivial ways. Definitely read David E's post from earlier today.
Gabriel Nivasch has been doing some great work on lower bound constructions. He recently had a paper on analysing upper and lower bounds for Davenport-Schinzel sequences (got a best student paper award at SODA 2009), and the kind of tight bounds he gets are very impressive (upto terms involving powers of alpha(n) in the exponent). Here, he presented joint work with Boris Bukh and Jiri MatousekMicha Sharir on a new lower bound for weak epsilon-nets.
A central construction here, that might be useful for other lower bound constructions is a very fast growing exponential grid. Roughly speaking, if we think of how it would map to a "regular grid", then the point (i1, i2, ....) on the [0..m] grid maps to the point whose jth coordinate is x_j = 2^{i_j * [m^{j-1} + m^{j-2} + ... + 1]d}. So things start getting really jumpy as the coordinates go up. A couple of observations do the heavy lifting for this grid:
Gabriel Nivasch has been doing some great work on lower bound constructions. He recently had a paper on analysing upper and lower bounds for Davenport-Schinzel sequences (got a best student paper award at SODA 2009), and the kind of tight bounds he gets are very impressive (upto terms involving powers of alpha(n) in the exponent). Here, he presented joint work with Boris Bukh and Jiri Matousek
A central construction here, that might be useful for other lower bound constructions is a very fast growing exponential grid. Roughly speaking, if we think of how it would map to a "regular grid", then the point (i1, i2, ....) on the [0..m] grid maps to the point whose jth coordinate is x_j = 2^{i_j * [m^{j-1} + m^{j-2} + ... + 1]d}. So things start getting really jumpy as the coordinates go up. A couple of observations do the heavy lifting for this grid:
- A straight line segment between two points in the stretched grid maps to a collection of d line segments in the "regular" grid: d-1 that goes almost straight up from the first (say lower) point, and another that goes across the final dimension (it's easier to think of this recursively)
- Convex sets in the stretched grid correspond to so-called "stair-convex sets" in the regular grid
- A diagonal in the stretched grid maps to a curve that doesn't touch many points in the regular grid.
Basically, the grid construction allows them to reason about lower bounds by going back to the regular grid. They use these ideas to prove the lower bound for weak epsilon-nets, but also for some incidence problems (using the third property). It seems to me that this construction might prove useful for other lower bounds in the future as well.
Coming up next: max flows, local search and a plethora of PTASs (try saying that fast)...
Sunday, June 07, 2009
SoCG 2009: Day 0
At least in my mind, things have been somewhat overshadowed by the sad news of yesterday, thus preventing me (thankfully) from writing the more frivolous posts that I might have penned.
Today was the 25th anniversary celebration for SoCG (1985-2009), and we had four speakers to do a retrospective on the field.
David Dobkin was first, talking about how some of the first geometric algorithms came to be. He interspersed many fun facts about the early days of SoCG:
It was interesting to see that even way back then, there was serious intersection between numerical algorithms, the graphics and vision folks, and the nascent geometry area. Some things haven't really changed. It also explains (for me) why there is somewhere deep down a sense that CG doesn't wholly situate within the larger algorithms community, but has a core identity that's slightly different.
One point that David made was very interesting. He talked about how Michael Shamos essentially created a problem book from scratch, listing basic problems in the new area of computational geometry, and methodically solving them one by one. He then asserted that it was the creation of this problem book that played a major role in the unification of the area. I think that makes a lot of sense. It's not so much that a list of problems got created. It's not too hard to do that. What I think was the critical factor was the listing of problems within-reach, that encouraged more people to start thinking about them. Muthu is very good at doing this with any field he jumps into, and I think he's able to jumpstart a lot of research for this exact reason. It's not easy to do: the problems have to be core to the area, but still not that difficult to solve.
Micha Sharir went next with a talk on the evolution of work in arrangements. I've always felt that work on arrangements seems to have reached the point of diminishing returns after some point: that new results were mildly interesting, but didn't necessarily hook into algorithm design in a nontrivial way. I still have somewhat of the same opinion after the talk, but it was good to see the evolution of the problems into higher dimensional surface arrangement questions.
Emo Welzl gave a nice overview of the exciting years between 1987-1992 when randomization began to bloom into a powerful tool for doing geometry. Of course, the very first randomized algorithm was a geometric one (Rabin's closest pair algorithm), but the really powerful methods came into being really with Clarkson's work, and the eps-net work of Haussler and Welzl. It was amusing that almost every single paper mentioned in Emo's talk was written or co-written by Ken: just goes to show his profound influence on the field both for new techniques, as well as new results.
For me, another great influence was Raimund Seidel's amazingly lucid exposition of backwards analysis: there's something to be said for crystal-clear writing and the impact it can have.
The final talk was by Kurt Mehlhorn, on the history that led to the development of LEDA and CGAL. I must confess that I've always felt rather intimidated by CGAL and LEDA: there's something about the phrase "traits class" that strikes fear into my heart. But Kurt's talk was immensely enjoyable: he gave several simple examples of inputs where floating point implementations of geometric algorithms fail spectacularly, and really reinforced the importance of precise implementations, something (if I may add) the rest of the algorithms community often can avoid if they're dealing with graphs or numeric data. I REALLY need to weave CGAL into the next incarnation of my geometry class: must be less lazy, must be less lazy, .....
Notes from the conference: I was fervently hoping that the organizers would lower expectation for next year, but no such luck :(. Impeccable organization, food, and free beer. Sigh......
I'll be tweeting occasionally from the conference. If you're reading this at the conference and want to do the same, please the hashtag #socg so all tweets can be collected in one place.
Today was the 25th anniversary celebration for SoCG (1985-2009), and we had four speakers to do a retrospective on the field.
David Dobkin was first, talking about how some of the first geometric algorithms came to be. He interspersed many fun facts about the early days of SoCG:
- One of the reasons CG is tied to the STOC/FOCS community is because when Michael Shamos first asked him where to publish a geometry paper, STOC was the first conference that came to mind.
- The Preparata-Shamos book only came about because (after Shamos left for law school) Ron Graham brokered a deal for Franco Preparata to write a book based on Shamos' thesis.
- SoCG was almost called the Symposium on Computer Geometry (ugh).
It was interesting to see that even way back then, there was serious intersection between numerical algorithms, the graphics and vision folks, and the nascent geometry area. Some things haven't really changed. It also explains (for me) why there is somewhere deep down a sense that CG doesn't wholly situate within the larger algorithms community, but has a core identity that's slightly different.
One point that David made was very interesting. He talked about how Michael Shamos essentially created a problem book from scratch, listing basic problems in the new area of computational geometry, and methodically solving them one by one. He then asserted that it was the creation of this problem book that played a major role in the unification of the area. I think that makes a lot of sense. It's not so much that a list of problems got created. It's not too hard to do that. What I think was the critical factor was the listing of problems within-reach, that encouraged more people to start thinking about them. Muthu is very good at doing this with any field he jumps into, and I think he's able to jumpstart a lot of research for this exact reason. It's not easy to do: the problems have to be core to the area, but still not that difficult to solve.
Micha Sharir went next with a talk on the evolution of work in arrangements. I've always felt that work on arrangements seems to have reached the point of diminishing returns after some point: that new results were mildly interesting, but didn't necessarily hook into algorithm design in a nontrivial way. I still have somewhat of the same opinion after the talk, but it was good to see the evolution of the problems into higher dimensional surface arrangement questions.
Emo Welzl gave a nice overview of the exciting years between 1987-1992 when randomization began to bloom into a powerful tool for doing geometry. Of course, the very first randomized algorithm was a geometric one (Rabin's closest pair algorithm), but the really powerful methods came into being really with Clarkson's work, and the eps-net work of Haussler and Welzl. It was amusing that almost every single paper mentioned in Emo's talk was written or co-written by Ken: just goes to show his profound influence on the field both for new techniques, as well as new results.
For me, another great influence was Raimund Seidel's amazingly lucid exposition of backwards analysis: there's something to be said for crystal-clear writing and the impact it can have.
The final talk was by Kurt Mehlhorn, on the history that led to the development of LEDA and CGAL. I must confess that I've always felt rather intimidated by CGAL and LEDA: there's something about the phrase "traits class" that strikes fear into my heart. But Kurt's talk was immensely enjoyable: he gave several simple examples of inputs where floating point implementations of geometric algorithms fail spectacularly, and really reinforced the importance of precise implementations, something (if I may add) the rest of the algorithms community often can avoid if they're dealing with graphs or numeric data. I REALLY need to weave CGAL into the next incarnation of my geometry class: must be less lazy, must be less lazy, .....
Notes from the conference: I was fervently hoping that the organizers would lower expectation for next year, but no such luck :(. Impeccable organization, food, and free beer. Sigh......
I'll be tweeting occasionally from the conference. If you're reading this at the conference and want to do the same, please the hashtag #socg so all tweets can be collected in one place.
Wednesday, April 01, 2009
CG Steering Comittee Elections
Via Marc van Kreveld comes the announcement of CG Steering Committee elections. The way it works is that people send nominations to Marc before Apr 14. He screens them, checks if the nominated individuals are willing to serve, and then starts an election on May 1 for 5 candidates to run the committee for the next three years. Deadline for voting is May 14.
The curent committee is:
and Marc's email address is marc at cs dot uu dot nl.
The curent committee is:
- Pankaj Agarwal
- Jeff Erickson
- Marc van Kreveld (secretary)
- Joe Mitchell
- Guenter Rote (chair)
and Marc's email address is marc at cs dot uu dot nl.
Friday, September 26, 2008
Announcements
- Sanjeev Khanna reminds us that FOCS early registration deadline is Oct 3, 2008. Get your cheesesteak on !
- CFP for the 2009 sausage convention (with beer!!): Deadline is Nov 24 (abstracts), Dec 1 (papers)
Thursday, June 12, 2008
SoCG 2008: Invited Talks
A Discrete Laplace-Beltrami Operator
Alexander Bobenko gave the first invited talk at the conference. As with Mathieu Desbrun's talk from a few years ago, this talk was on the area of 'discrete differential geometry', particularly focusing on a discrete Laplace-Beltrami operator, and how to compute Delaunay triangulations on polyhedral surfaces.
The general principle behind efforts in discrete differential geometry is quite apropos for a CS audience. Rather than doing a 'numerical discretization' of differential geometry to enable computations, the idea is to discretize the entire theory, so that the continuous theory emerges as the limit of the discrete theory.
This goes against the flow of much of what we often see in discrete computer science, where the idea is to relax to an underlying continuous domain in order to learn things about discrete structures. It also makes a lot of sense, because if successful, it gives a 'native' version of differential geometry that's naturally robust without having to worry about the level of discretization etc.
The slides are quite readable on their own, and I'd recommend that anyone who's interested take a look. In summary the idea is this. Given a function on a manifold, you can write down an energy operator (called the Dirichlet energy) such that the gradient of this energy is the Laplace-Beltrami operator on the manifold.
If you do this for piecewise linear functions defined on a simplicial surface in 3-space, then you get an expression for the Laplacian: however, this expression is not intrinsic (it depends on the embedding of the surface in 3-space). In the world of differential geometry, being intrinsic is the whole point, so this is not a happy state of affairs.
It turns out that if you use a triangulation of the surface constructed by using an 'intrinsic Delaunay triangulation' (more on that in a second), and then define an interpolation for a function on the vertices in the usual manner, then the resulting energy function is minimal, and the Laplacian you get *is* intrinsic. An intrinsic Delaunay triangulation is constructed much like you'd construct a regular Delaunay triangulation, with the caveat being that you might have to use geodesics on the surface as "edges" of the triangles, and some triangles might end up being degenerate (so it's not a "normal" triangulation).
But in any case, doing this allows you to work with a well-defined Laplace operator on a discrete structure, and the second part of the talk showed how you can construct discrete minimal surfaces using such an operator.
Geometry is Everywhere (part XLVII)
Ken Clarkson gave the second invited talk, which was a romp through the world of metric spaces and the various notions of dimensions used to describe them. Ken doesn't yet have talk slides online, but somewhere in the union of this, this and this is much of the talk material. The main premise was to weave together different notions of dimension for a metric space, and how they can be used to do geometry in the abstract. If I'm not giving more details, it's because the talk covered so much ground that it's hard to know where even to start. It was wildly entertaining though, and there was a general clamor afterwards for Ken to write a book on this topic (which I hope he does).
And the "47" ? A cryptic shoutout to Pomona College alumni: if you're one, you probably understand the reference.
Subscribe to:
Posts (Atom)