On visibility and covering by convex sets |
| |
Authors: | Jiří Matoušek Pavel Valtr |
| |
Institution: | (1) Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic |
| |
Abstract: | A setX⊆ℝ
d
isn-convex if among anyn of its points there exist two such that the segment connecting them is contained inX. Perles and Shelah have shown that any closed (n+1)-convex set in the plane is the union of at mostn
6 convex sets. We improve their bound to 18n
3, and show a lower bound of order Ω(n
2). We also show that ifX⊆ℝ2 is ann-convex set such that its complement has λ one-point path-connectivity components, λ<∞, thenX is the union ofO(n
4+n
2λ) convex sets. Two other results onn-convex sets are stated in the introduction (Corollary 1.2 and Proposition 1.4).
Research supported by Charles University grants GAUK 99/158 and 99/159, and by U.S.-Czechoslovak Science and Technology Program
Grant No. 94051. Part of the work by J. Matoušek was done during the author’s visits at Tel Aviv University and The Hebrew
University of Jerusalem. Part of the work by P. Valtr was done during his visit at the University of Cambridge supported by
EC Network DIMANET/PECO Contract No. ERBCIPDCT 94-0623. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|