Editing Konstantin Rybnikov

Title: Konstantin Rybnikov

Main Research Question: Can we develop a method to determine if a given piecewise-linear (PL) surface in three-dimensional space (or higher) is convex?

Methodology:

1. Definition of Local Convexity: Rybnikov uses Bouligand's (1932) notion of local convexity. A surface is considered locally convex at a point if there's a neighborhood around that point that lies on the boundary of a convex n-dimensional body.

2. Introduction of Piecewise-Linear (PL) Surfaces: Rybnikov defines a PL surface as a pair (M, r), where M is a topological manifold with a fixed cell-partition, and r is a continuous realization map from M to Rn that satisfies certain conditions.

3. Main Theorem: Rybnikov's main theorem states that a closed PL-surface immersed in Rn (n ≥ 3) with at least one point of strict convexity, and such that each (n-3)-cell has a point at which the surface is locally convex, is convex.

4. Algorithm for Convexity Verification: Rybnikov presents an algorithm that checks local convexity on each (n-3)-face of the surface. If for all k and every k-face, there's an (n-k-1)-sphere lying in a complementary subspace and centered at some point of an (n-k-2)-face, then the surface is an immersion. The algorithm reports "not convex" if it's not.

Results:

1. The algorithm implies a test for global convexity of PL-surfaces.

2. The complexity of the algorithm depends on the way the surface is given as input data. Assuming general input data, the complexity is O(fn-3, n-2), where fk,l is the number of incidences between cells of dimension k and l.

Implications:

1. The algorithm provides a method to check if a given PL-surface is convex, which is useful in computational geometry.

2. The algorithm's independence on the dimension of the space and its general input data make it easier to implement.

3. The theorem and algorithm contribute to the understanding of local and global convexity in the context of piecewise-linear surfaces.

Link to Article: https://arxiv.org/abs/0309041v2
Authors: 
arXiv ID: 0309041v2

[[Category:Computer Science]]
[[Category:Surface]]
[[Category:Algorithm]]
[[Category:Convex]]
[[Category:Convexity]]
[[Category:N]]