The following questions concern your submitted paper which is given at the top of this page.Instructions (in case of doubt):(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

 1d 1.5d 2d 2.5d (polyhedral terrain) 3d 4d arbitrary (fixed) dimension high (variable) dimensions other spaces (for example, metric spaces)

## Objects

 points lines, planes, hyperplanes, line segments polygons, polyhedra circles, balls, spheres degree-2 curves and surfaces higher-degree algebraic curves and surfaces objects of arbitrary shape, pseudolines, etc. Convexity convex shapes only

## Geometric Problem

convex hull
Voronoi diagram
Delaunay triangulation
triangulation (other than Delaunay), tilings of space, meshing
pseudotriangulation
arrangement
calculation of distance, area, width etc.
optimization problem:
 • clustering
 • shape matching
 • shape simplification
 • shortest path
 • shortest tree, spanner, or other network design problem
 • other type of optimization problem:
curve and surface reconstruction
geometric modeling
shape analysis (topology or other characteristics)
range searching
motion planning, manipulation of objects
nearest neighbor
visibility, illumination, art gallery
graph drawing, graph embedding
geometric deduction and inference, learning, theorem-proving
other:

## Algorithmic Question

 construction enumeration sampling geometric primitives (problems of constant size) other:

## Progress

Work on the problems addressed in the paper is finished.
Work on the problems addressed in the paper will continue.
Work on the problems addressed has started recently.
The problem has a long history.
The results reported in this paper are preliminary.

This is a new problem that has not been considered before.
This is the first solution to a problem which has been posed as an open problem
 • publicly, in a lecture or at a workshop/conference
 • in the literature
 • privately
The problem has been considered previously. Compared to previous solutions, the result (algorithm/theorem) is
 • faster
 • more general
 • simpler, easier to implement
 • easier to describe
 • easier to understand
 • better
 • easier to analyze/prove
 • more reliable/robust
 • not better, but different (an alternative approach)
 • worse
 • uses less space.

## Algorithmic Problem Setting

 classical (static off-line; all data is known in advance) data structure (preprocessing and query) dynamic or on-line (insertion and deletion) kinetic (data in motion) data streams oracle models, black-box models, information-based complexity noisy data, data with errors, imprecise or fuzzy data external memory, caching parallel computing other computational model (e.g. quantum computing, optical computing, special hardware):

## Characteristics of Solution

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

## Type of Running Time

 finite (undecidable/decidable/computable) NP-hard/exponential, NP P (polynomial) low-order polynomial linear sublinear (poly-)logarithmic or sublogarithmic constant subconstant The running time of the algorithm is not analyzed.

## Combinatorial Geometry

The focus of the paper lies in combinatorial geometry.
A substantial part of the paper deals with some question(s) of combinatorial geometry.
Type of Question:
 • geometric complexity of geometric objects or data structures
 • counting and enumeration
 • other structural questions for of a set of combinatorial objects, (e.g. connectivity, flipping in triangulations)
 • lower bounds
 • upper bounds
 • pure existence
 • other:

## Application Area, Motivation

 biomolecules cartography, GIS graphics CAD, computer-aided design (and manufacturing, etc.) image processing robotics statistics other:

## Type of Contribution

 new algorithmic technique new proof, new proof technique new paradigm new problem new definition, new concept revisits or simplifies some old solution/problem none of the above

## Visualization

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

## Where is the focus of your paper

Algorithm
algorithm design and analysis (theoretical level)
 • The algorithm is only a conceptual tool (for a combinatorial proof or a proof of an existential statement, for example).
 • The algorithm is implemented, and the program can be used for serious applications.
 • The algorithm is implemented as a prototype.
 • The algorithm is not implemented.
 • The algorithm will never be implemented.
experimental or empirical comparison
average-case analysis, probablilistic analysis
exact computation
other approaches to robustness, numerical accuracy
other implementation issues:
software issues
Mathematics
combinatorial geometry
geometry of curves and surfaces
topology
other geometric questions
Applications
applications outside geometry

## Mathematical Techniques

 linear algebra (beyond elementary analytic geometry) algebra combinatorics graph theory probability calculus, differential geometry topology other:

## A few Questions for Statistics

 How many authors does the paper have? How many authors are students? How many authors work in academia (excluding students)? How many authors work in industry? From which country(ies) are the authors?

## Final Question about the Paper

 The paper is characterized very well by the above classification. The paper does not fit at all into this classification. Anything else I would like to say: (Comments about the submission process or about the conference itself, suggestions for future conferences)