Computational Geometry Ontology Statistics

Total number of respondents: 139 submitted papers + 12 program committee (PC) members, whose answers are shown in blue; green = accepted papers (total=41 or 29%), red = rejected papers.
Clicking will reveal the fraction of answers that were given by authors whose papers were eventually accepted or rejected, respectively. The data was collected from authors by asking them to fill in a form. The figures should be regarded with the usual suspicion that is appropriate for the results of polls and web forms.

Part I

The first part is a poll concerning future SoCG conferences.
If you have submitted several papers, you need to answer these questions only once. (Unless you have a very strong opinion; then you can repeat your answers for each of your submissions.) If you have no strong opinion, you can leave the fields blank.

Submission

How did you like the two-stage electronic submission procedure?

It was confusing.

2 | 50%

It was smooth and convenient.

57 | 30%

It was complicated and cumbersome.

5 | 60%

It was clear and easy.

69 | 30%

I experienced technical problems with the submission process.

2	2 \| 0%

How should the submission at future conferences be handled?

Format of Paper

It would be inconvenient if papers could not be submitted in PDF format.

66 | 30%

It would be inconvenient if papers could not be submitted in PostScript format.

67 | 27%

It would be inconvenient if papers could not be submitted in compressed format.

17 | 31%

It would be inconvenient if I could not use color figures.

30 | 21%

I would prefer to submit papers in the final two-column proceedings format, instead of the current one-column format.

48 | 32%

I would prefer to use my own format for submission if the permitted quantity of text would match the two-column format of the final proceedings version.

19 | 38%

Which of the following alternate submission forms would you find useful?

a URL pointer to a technical report or preprint on my homepage

37 | 20%

a pointer to an arXiv preprint

14 | 38%

All submissions not adhering to the guidelines (e.g. having more than 10 pages, or being 2-column) should be rejected.

I agree.

37 | 20%

I disagree.

86 | 34%

Submissions must contain all proofs, in an appendix if necessary (without length restriction).

I agree.

62 | 34%

I disagree.

62 | 27%

What would you think about double-blind reviewing for SoCG? (The committee and subreferees do not know the authors of the papers.) (This question was added later and only asked of PC members.)

I would favor it.

4	4 \| 100%

I am against it.

5	5 \| 100%

Anything else I would like to say: (Specific remarks about the questions above, comments about the submission process or about the conference itself, suggestions for future conferences)
THESE ARE ONLY THE ANSWERS FROM PC MEMBERS. Answers from authors are given at the end of the next section.

7	7 \| 100%

It's a pity that applied papers still have such a hard time getting in and that a mix of theory and application is considered "strange".

I think blind reviewing is a good thing, i.e. the committee should know the authors names, but not the subreferees.

the last three questions do not have a yes/no answer: for not adhering to guidelines: 2-column format is too much, but i wouldnt disqualify a 10.5 page long normal format. the idea of having all proofs in an appendix is appealing on one hand, but it is unfair to dump a 50 pages paper on a busy PC member. on second thought, perhaps it is always a good idea to require all proofs - will prevent half-baked papers from showing up. the blind refereeing is ok in principle, but it has drawbacks too: we often say that we dont understand the paper, but we trust X. if we didnt know who X was, then...

(the last 3 questions are a little bit "boolean"...)

On rejecting all papers that don't satisfy format guidelines: In principle, I'd like to reject all such papers, but I don't want to be too rigid. For instance, I wouldn't want to reject an 11 page paper, but I would want to reject a 15 page paper. On submissions containing all proofs: I'm in favor of this if "all proofs" is changed to "all interesting and/or important proofs", but this is such a subjective measure that I'm not sure how it could ever be enforced. On double-blind reviewing: I'm somewhat for this, in principle, but it would depend on how cumbersome it would make the reviewing process. I'm also concerned about how effective this would be in practice --- this is a small enough community that one could probably guess the authors for many of the paper based on known interests, the paper's list of references, and idiosyncrasies of individual writing styles.

Double-blind would make it highly inconvenient to use subreferees: You'd always run the risk of asking an author or coauthor, unless you figured out who the authors are - in which case you'd defeat the purpose of double-blind.

I am afraid that confidence levels were so different among PC members. Maybe some nice guideline is required.

Part II

(1) In each category, it is possible to independently make as many selections as you want (or none at all). However, you should try to select those boxes that best describe your situation, and you should not select every box that might possibly apply. For example, an algorithm for line segments will necessarily deal with the endpoints of those line segments, i.e. points, or possibily the algorithm also works for points by treating them as a special case of a degenerate line segment. but in this case you should check only the box for line segments, in the category Objects below.)
(2) If your paper contains several results/algorithms you can answer the questions below for that aspect of your paper which is most characteristic, in your feeling. For example, the main new achievement of your algorithm is a logarithmic query time, as opposed to a polynomial preprocessing time.
Alternatively, if your paper has several contributions of equal importance, you can check the union of the boxes that you would check for each contribution individually. (For example, an algorithm dealing with points on a line (1d), and another algorithm which handles points in 4d. You can check two boxes in the first category Dimension.)

Dimension

5 | 20%

1.5d

2	2 \| 100%

77 | 27%

2.5d (polyhedral terrain)

4 | 25%

37 | 27%

0 | 100%

arbitrary (fixed) dimension

34 | 35%

high (variable) dimensions

11 | 9%

other spaces (for example, metric spaces)

4 | 75%

Objects

points

57 | 33%

lines, planes, hyperplanes, line segments

44 | 25%

polygons, polyhedra

40 | 18%

circles, balls, spheres

23 | 26%

degree-2 curves and surfaces

12 | 25%

higher-degree algebraic curves and surfaces

14 | 7%

objects of arbitrary shape, pseudolines, etc.

15 | 53%

Convexity

convex shapes only

10 | 60%

Geometric Problem

convex hull

12 | 25%

Voronoi diagram

10 | 20%

Delaunay triangulation

15 | 27%

triangulation (other than Delaunay), tilings of space, meshing

17 | 18%

pseudotriangulation

4 | 25%

arrangement

20 | 35%

calculation of distance, area, width etc.

20 | 20%

optimization problem:

•	clustering

8 | 25%

•	shape matching

6 | 17%

•	shape simplification

8 | 13%

•	shortest path

8 | 50%

•	shortest tree, spanner, or other network design problem

8 | 50%

•	other type of optimization problem:

16 | 31%

dilation // packing // length of shortest side of rectangle // Geometric Partition Problems // set cover // Triangle area optimization (MaxMin, MinMax) // extremal configuration under certain measure // simultaneous clusters found in several arrangements // finding local or global minima // power assignment // convex programming // optimal strategies for games // protein folding with maximal H-H contacts // optimal characterization // minimize height of a watchtower //

curve and surface reconstruction

10 | 40%

geometric modeling

17 | 12%

shape analysis (topology or other characteristics)

15 | 33%

range searching

7 | 71%

motion planning, manipulation of objects

13 | 31%

nearest neighbor

11 | 18%

visibility, illumination, art gallery

8 | 38%

graph drawing, graph embedding

9 | 33%

geometric deduction and inference, learning, theorem-proving

4	4 \| 0%

other:

12 | 8%

combinatorial rigidity theory // packing // finding an object // packing // realizability // intersection of curves // deals with aggregates of geometric data // curve generation, traversal, indexing // folding / dissection // structural characterization and finding an efficient algorithm // geometric path, geometric matching // collision detection

Algorithmic Question

construction

81 | 30%

enumeration

16 | 13%

sampling

9 | 22%

geometric primitives (problems of constant size)

6 | 17%

other:

13 | 23%

distance computation // error measure // eigenvectors // robustness // robustness // reconfiguration of trees // computing Betti numbers // set cover // optimization // output-sensitive non-intersection queries (reporting problems) on aggregated data // Handling one-pass, streaming data // approximation // approximation

Progress

Work on the problems addressed in the paper is finished.

19 | 32%

Work on the problems addressed in the paper will continue.

96 | 30%

Work on the problems addressed has started recently.

24 | 21%

The problem has a long history.

40 | 33%

The results reported in this paper are preliminary.

8 | 13%

This is a new problem that has not been considered before.

30 | 23%

This is the first solution to a problem which has been posed as an open problem

23 | 43%

•	publicly, in a lecture or at a workshop/conference

14 | 50%

•	in the literature

13 | 38%

•

privately

7 | 14%

The problem has been considered previously. Compared to previous solutions, the result (algorithm/theorem) is

65 | 28%

•

faster

41 | 29%

•	more general

42 | 26%

•	simpler, easier to implement

33 | 15%

•	easier to describe

17 | 12%

•	easier to understand

14 | 7%

•

better

30 | 30%

•	easier to analyze/prove

9 | 11%

•	more reliable/robust

25 | 12%

•	not better, but different (an alternative approach)

6 | 33%

•

worse

1	1 \| 0%

•	uses less space.

9 | 33%

Algorithmic Problem Setting

classical (static off-line; all data is known in advance)

86 | 22%

data structure (preprocessing and query)

23 | 35%

dynamic or on-line (insertion and deletion)

10 | 30%

kinetic (data in motion)

9 | 44%

data streams

4 | 50%

oracle models, black-box models, information-based complexity

2 | 50%

noisy data, data with errors, imprecise or fuzzy data

7 | 29%

external memory, caching

2	2 \| 100%

parallel computing

2	2 \| 0%

other computational model (e.g. quantum computing, optical computing, special hardware):

3	3 \| 0%

floating point // floating point // commodity graphics hardware

Characteristics of Solution

approximation

42 | 33%

randomized

14 | 36%

heuristic (with no guaranteed (optimal, correct) solution)

8	8 \| 0%

Type of Running Time

finite (undecidable/decidable/computable)

7 | 43%

NP-hard/exponential, NP

6 | 33%

P (polynomial)

27 | 30%

low-order polynomial

45 | 38%

linear

19 | 26%

sublinear

3 | 33%

(poly-)logarithmic or sublogarithmic

9 | 33%

constant

2	2 \| 0%

subconstant

0 | 100%

The running time of the algorithm is not analyzed.

13 | 15%

Combinatorial Geometry

The focus of the paper lies in combinatorial geometry.

26 | 38%

A substantial part of the paper deals with some question(s) of combinatorial geometry.

32 | 28%

Type of Question:

•	geometric complexity of geometric objects or data structures

22 | 32%

•	counting and enumeration

13 | 15%

•	other structural questions for of a set of combinatorial objects, (e.g. connectivity, flipping in triangulations)

21 | 24%

•	lower bounds

11 | 36%

•	upper bounds

21 | 38%

•	pure existence

4 | 50%

•

other:

4 | 25%

robustness // robustness // computational topology // Euler characteristic

Application Area, Motivation

biomolecules

21 | 19%

cartography, GIS

18 | 33%

graphics

31 | 10%

CAD, computer-aided design (and manufacturing, etc.)

33 | 21%

image processing

16 | 13%

robotics

30 | 27%

statistics

10 | 10%

other:

27 | 33%

shape matching // packing // Data mining // simulation // computer games, animation // packing // visualization // manifold learning // Communication networks // Medicine, Radiation Therapy and Surgery // facility location // shape learning with minimal a priori knowledge // wireless // FEM calculation // simulation // network design // information retrieval // graph drawing // graph encoding // querying databases with aggregated data (e.g., VLSI, financial, etc.) // database, scientific computing, mathematics // games // Mesh generation // Data mining // scientific data analysis // sensor networks // moving finite element methods

Type of Contribution

new algorithmic technique

61 | 28%

new proof, new proof technique

38 | 26%

new paradigm

18 | 33%

new problem

29 | 17%

new definition, new concept

30 | 23%

revisits or simplifies some old solution/problem

23 | 17%

none of the above

7 | 57%

Visualization

There is a video demonstrating the result of the paper.

5	5 \| 0%

There is an applet or computer program demonstrating the result of the paper.

22 | 23%

Where is the focus of the paper?

Algorithm

algorithm design and analysis (theoretical level)

72 | 33%

•	The algorithm is only a conceptual tool (for a combinatorial proof or a proof of an existential statement, for example).

6 | 33%

•	The algorithm is implemented, and the program can be used for serious applications.

27 | 19%

•	The algorithm is implemented as a prototype.

33 | 21%

•	The algorithm is not implemented.

37 | 41%

•	The algorithm will never be implemented.

0 | 100%

experimental or empirical comparison

19 | 5%

average-case analysis, probablilistic analysis

3 | 33%

exact computation

27 | 26%

other approaches to robustness, numerical accuracy

12	12 \| 0%

other implementation issues:

4	4 \| 0%

certified topology (certified Delaunay graph) // adaptive approach to exact computation // Algorithm is implemented and is planned to be released for public use in near future // certified topology

software issues

3	3 \| 0%

Mathematics

combinatorial geometry

42 | 29%

geometry of curves and surfaces

28 | 29%

topology

22 | 23%

Mathematical Techniques

linear algebra (beyond elementary analytic geometry)

12 | 17%

algebra

22 | 27%

combinatorics

39 | 26%

graph theory

22 | 32%

probability

15 | 27%

calculus, differential geometry

15 | 20%

topology

26 | 27%

other:

10 | 40%

Mathematical Morphology, Fuzzy set // geometry // approximation theory // complexity theory // geometry // Mathematics for Voronoi and Delaunay geometry // number theory // optimization // transcendental number theory // integral geometry

A few Questions for Statistics

How many authors does the paper have? (see also raw data)

22 | 23%

61 | 31%

35 | 23%

13 | 38%

5 | 60%

2 | 50%

1	1 \| 0%

How many authors are students?

52 | 42%

72 | 21%

14 | 29%

1	1 \| 0%

How many authors work in academia (excluding students)?

8 | 13%

65 | 25%

40 | 33%

20 | 45%

3	3 \| 0%

2 | 50%

1	1 \| 100%

How many authors work in industry?

126 | 29%

13 | 31%

1	1 \| 100%

From which country(ies) are the authors? (see cartograms)

139 | 29%

Final Question about the Paper

The paper is characterized very well by the above classification.

78 | 24%

The paper does not fit at all into this classification.

9 | 11%

Anything else I would like to say: (Comments about the submission process or about the conference itself, suggestions for future conferences)

24 | 33%

Regarding last question in Part I: I do not think it would be practical to impose that papers have ALL PROOFS, given the "extended abstract" nature of the SoCG conference submission. But authors should be ENCOURAGED to provide an arXiv or url link to as-complete-as-possible versions of their papers, to help the committee in making the decision.

The submission process was clear and easy, but the restriction of not being able to change the abstract later makes an early registration less attractive. I wonder if you have statistics about the time between the first registration step and the second. Submission process: I disagree on rejecting papers on formal grounds without looking at proportionality or appropriateness. Not all proofs need to be there, but the important or non-obvious should if the statement might otherwise be questionable or may lead to a rejected paper. Also the page numbers need a limitation, but 11 instead of 10 pages (separate title page ;-) are not the issue. In particular since we have appendices, which I find important. I would appreciate a more realistic page limit oriented at the final proceeding space, either by submitting in this final style or some equivalent larger page budget. For refereeing, a larger page budget but with 11pt and sufficient margins would be more convenient.

The submitted work is a generalization of some earlier works. I had trouble expressing this fact in this questionnaire.

Regarding the two-stage submission procedure: I cannot remember if it was cumbersome. It was two months ago. About the format: as an author, both PS and PDF are fine with me. As a referee I much prefer PDF because the files are smaller and because printing errors are much less frequent than with PS. Questions about criteria for accepting/rejecting submissions: I have strong opinions about it but I have doubts about whether it is appropriate to give such opinions while the PC is still at work.

same reviews apply to our submission on semi-algebraic curves

The submission process was much smoother in comparison to the process in last year's SoCG. As for the length restriction: If the submission is slightly longer than the limit (say the references end only in page 11), this is still OK. However, in case of major deviations, the submission should be rejected. However, I prefer that the submission have the final format used in the proceedings. This way the final version is likely to be more similar to the refereed one.

copied from submission on algebraic curves

Submission process was great. Collecting feedback and statistics is a good idea too.

annoying poll!

This paper presents one aspect of my Ph.D. thesis.

Some aspects of the paper are not characterized particularly well by the above classification. Covering, packing, and independent set are standard optimization problems that can appear in a geometric setting. Here the optimization problem was covering. The full glory of the algorithmic setting was "abstractly geometric", as in the VC dimension. Such a category might be an alternative in the "dimension" category. Nice questionnaire. Issues that might come up at the business meeting might also be considered here, in an advisory way. For example, a poll on conference location would have a different bias than the one at the business meeting. Submission via pointer to arXiv preprint would encourage use of the arXiv server, simplify the job of collecting submissions, and underline the peculiarity of submitting to a conference in order to publicize a paper that is already easily available world-wide.

Some pre-submission details whether emphasis is on certain applied / theory issues would be helpful -- e.g., will there be a biogeometry session?

The proposed algorithm is currently implemented as a prototype. However, we expect that the implementation will be at the stage of serious applications around the time of SoCG conference.

This survey was very annoying.

This survey is even more annoying the second time around.

Part I: I think one answer was missing for: How did you like the two-stage electronic submission procedure? Answer: It was OK (the listed ones were either on one side or the other) A general wish on future submission procedures: that they are as easy as possible, and don't take more than 10 (real) minutes. Part II. I think this survey could be further improved and also made shorter (regarding final question above). A wish about the statistics which will be prepared: to report accurately on the number of algorithms which will be never implemented. I hope the statistics will be made available and distributed to the participants during the symposium (or at least posted on the web).

Please add explanation to the above fields. Some of them are not self explanatory.

This form does not provide ample options. For example: 1. Running time (no option to specify results that are linear/polynomial in one parameter - an important one, while treating other parameters as constant, etc.) 2. # of authors does not account for part time students working in industry (therefore numbers dont add up). 3. Final Question about the paper - only the two extremes are available as options (very well OR does not fit at all).

The above questions is great, but it clearly has many holes for our particular paper. I would be happy to suggest refinements of your categories for this purpose. Thanks, Chee

The paper uses BSP trees, Segment trees, and Sweep Planes heavily. Thus, it could be considered a data structure paper, as well as an algorithms paper.

The offered categories reflect a traditional view of the work done in computational geometry and need some expansion into computational topology.

Quite a few times I would wish there were additional categories.

It would be absurd to _require_ that the submission be formatted differently than the final paper. And a huge waste of time, too.

no author can have more than two papers in one conf submission

Part III: Questions for Program Committee Members

The bidding process

Which of the following features (bugs?) of the bidding process did you find useful?

summaries ("abstracts")

12	12 \| 100%

subject categories (1. Geometric algorithms: design. 2. Geometric algorithms: analysis. 3. Geometric data structures ... 17. Applications)

2	2 \| 100%

looking at papers before the submission deadline

4	4 \| 100%

Five categories for bidding (++,+,~,-,conflict) is too much.

1	1 \| 100%

Five categories for bidding are too few.

0 | 100%

Five categories for bidding are o.k.

11	11 \| 100%

The reviewing process

Specifying a confidence level for the evaluation (range 0-3)

•	This feature can be dropped as far as I am concerned.

1	1 \| 100%

•	It was convenient.

3	3 \| 100%

•	It was important.

8	8 \| 100%

Giving separate grades in different categories (technical strength, presentation, etc.)

•	This feature can be dropped as far as I am concerned.

5	5 \| 100%

•	It was convenient.

5	5 \| 100%

•	It was important.

2	2 \| 100%

What did you think of papers with accompanying video and multimedia submissions?

•	I did not notice any accompanying video and multimedia submissions with the papers I looked at.

6	6 \| 100%

•	I found them useful.

3	3 \| 100%

•	I did not find them useful.

3	3 \| 100%

In general, do you think it is a good idea to encourage papers with accompanying video and multimedia submissions?

•

Yes.

6	6 \| 100%

•

No.

6	6 \| 100%

The discussion process

Normalized scores in addition to original scores

•	This feature can be dropped as far as I am concerned.

3	3 \| 100%

•	They were convenient.

7	7 \| 100%

•	They were important.

2	2 \| 100%

History of status changes

•	This feature can be dropped as far as I am concerned.

2	2 \| 100%

•	It was convenient.

2	2 \| 100%

•	It was important.

8	8 \| 100%

List of paper scores, alphabetical by title

•	This feature can be dropped as far as I am concerned.

5	5 \| 100%

•	They were convenient.

6	6 \| 100%

•	They were important.

1	1 \| 100%

List of paper scores by paper number

•	This feature can be dropped as far as I am concerned.

0 | 100%

•	They were convenient.

6	6 \| 100%

•	They were important.

6	6 \| 100%

List of paper scores, sorted by standard deviation of scores

•	This feature can be dropped as far as I am concerned.

3	3 \| 100%

•	They were convenient.

8	8 \| 100%

•	They were important.

1	1 \| 100%

Any useful/important features that I could think of. (besides having the total count in each category prominently displayed at all times)

2	2 \| 100%

For the bidding process it would be very nice to have a page that lists the abstracts and gives you the opportunity to bid just under each abstract. I had to have two windows open, one with the abstracts, one with the bidding, which was pretty annoying (especially after clicking on the wrong button and losing all bids entered so far ... :-\

Having a clear and standarized way of separating the PC person opinions from subreferees opinions

A discussion phase of three weeks is too long.

1	1 \| 100%

Three weeks of discussion are too short.

0 | 100%

Three weeks of discussion are just right.

11	11 \| 100%