Presentation	1999/10/25 Lovasz's Lemma for the Three-Dimensional K-Level of Concave Surfaces and its Applications Naoki Katoh, Takeshi Tokuyama,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	We show that for any line l in space, there are at most k(k+1) tangent planes through l to the k-level of an arranement of concave surfaces. This is a generalization of Lovasz's lemma, which is a key constituent in the analysis of the complexity of k-level of planes. Our proof is constructive, and finds a family of concave surfaces covering the "laminated at-most-k level". As consequences, (1): we have an O((n-k)^<2/3>n^2) upper bound for the complexity of the k-level of n triangles of space, and (2): we can extend the k-set result in space to the k-set of a system of subsets of n points.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)
Paper #	COMP99-39
Date of Issue

Conference Information
Committee	COMP
Conference Date	1999/10/25(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Lovasz's Lemma for the Three-Dimensional K-Level of Concave Surfaces and its Applications
Sub Title (in English)
Keyword(1)
1st Author's Name	Naoki Katoh
1st Author's Affiliation	Department of Architecture and Architectural Systems, Faculty of Engineering, Kyoto University()
2nd Author's Name	Takeshi Tokuyama
2nd Author's Affiliation	Graduate School of Information Systems, Tohoku University
Date	1999/10/25
Paper #	COMP99-39
Volume (vol)	vol.99
Number (no)	388
Page	pp.pp.-
#Pages	8
Date of Issue