Computer Science – Computational Geometry
Scientific paper
2008-06-10
Computer Science
Computational Geometry
13 pages, 12 figures
Scientific paper
A surface embedded in space, in such a way that each point has a neighborhood within which the surface is a terrain, projects to an immersed surface in the plane, the boundary of which is a self-intersecting curve. Under what circumstances can we reverse these mappings algorithmically? Shor and van Wyk considered one such problem, determining whether a curve is the boundary of an immersed disk; they showed that the self-overlapping curves defined in this way can be recognized in polynomial time. We show that several related problems are more difficult: it is NP-complete to determine whether an immersed disk is the projection of a surface embedded in space, or whether a curve is the boundary of an immersed surface in the plane that is not constrained to be a disk. However, when a casing is supplied with a self-intersecting curve, describing which component of the curve lies above and which below at each crossing, we may determine in time linear in the number of crossings whether the cased curve forms the projected boundary of a surface in space. As a related result, we show that an immersed surface with a single boundary curve that crosses itself n times has at most 2^{n/2} combinatorially distinct spatial embeddings, and we discuss the existence of fixed-parameter tractable algorithms for related problems.
Eppstein David
Mumford Elena
No associations
LandOfFree
Self-overlapping Curves Revisited does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Self-overlapping Curves Revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Self-overlapping Curves Revisited will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-175494