Search

How do we most quickly fold a paper strip (modeled as a line) to obtain a desired mountain-valley pattern of equidistant creases (viewed as a binary string)? Define the folding complexity of a mountain-valley string as the minimum number of simple folds required to construct it. We first show that the folding complexity of a length-n uniform string (all mountains or all valleys), and hence of a length-n pleat (alternating mountain/valley), is O(lg2n). We also show that a lower bound of the complexity of the problems is Ω(lg2n/lg lg n). Next we show that almost all mountain-valley patterns require Ω(n/lg n) folds, which means that the uniform and pleat foldings are relatively easy problems. We also give a general algorithm for folding an arbitrary sequence of length n in O(n/lg n) folds, meeting the lower bound up to a constant factor. © 2011 Springer., SCOPUS: ar.j, info:eu-repo/semantics/published

We study the following geometric hypergraph coloring problem: given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing sufficiently many points contains all colors. We show that if the strip contains at least 2k-1 points, such a coloring can always be found. In dimension d, we show that the same holds provided the strip contains at least k(4ln k+ln d) points. We also consider the dual problem of coloring a given set of axis-aligned strips so that any sufficiently covered point in the plane is covered by k colors. We show that in dimension d the required coverage is at most d(k-1)+1. Lower bounds are also given for all of the above problems. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. From the computational point of view, we show that deciding whether a three-dimensional point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete. This shows a big contrast with the planar case, for which this decision problem is easy. © 2010 Springer-Verlag., SCOPUS: cp.k, info:eu-repo/semantics/published

We study the following geometric hypergraph coloring problem: given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing sufficiently many points contains all colors. We show that if the strip contains at least 2k-1 points, such a coloring can always be found. In dimension d, we show that the same holds provided the strip contains at least k(4 ln k + ln d) points. We also consider the dual problem of coloring a given set of axis-aligned strips so that any sufficiently covered point in the plane is covered by k colors. We show that in dimension d the required coverage is at most d(k-1) + 1. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. From the computational point of view, we show that deciding whether a three-dimensional point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete. This shows a big contrast with the planar case, for which this decision problem is easy. © 2011 Springer., Special issue of selected papers from the 7th Japan Conference on Computational Geometry and Graphs (JCCGG09), SCOPUS: ar.j, info:eu-repo/semantics/published

We study the following geometric hypergraph coloring problem: given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing sufficiently many points contains all colors. We show that if the strip contains at least 2k-1 points, such a coloring can always be found. In dimension d, we show that the same holds provided the strip contains at least k(4ln k+ln d) points. We also consider the dual problem of coloring a given set of axis-aligned strips so that any sufficiently covered point in the plane is covered by k colors. We show that in dimension d the required coverage is at most d(k-1)+1. Lower bounds are also given for all of the above problems. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. From the computational point of view, we show that deciding whether a three-dimensional point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete. This shows a big contrast with the planar case, for which this decision problem is easy. © 2010 Springer-Verlag., SCOPUS: cp.k, info:eu-repo/semantics/published

We study the following geometric hypergraph coloring problem: given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing sufficiently many points contains all colors. We show that if the strip contains at least 2k-1 points, such a coloring can always be found. In dimension d, we show that the same holds provided the strip contains at least k(4 ln k + ln d) points. We also consider the dual problem of coloring a given set of axis-aligned strips so that any sufficiently covered point in the plane is covered by k colors. We show that in dimension d the required coverage is at most d(k-1) + 1. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. From the computational point of view, we show that deciding whether a three-dimensional point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete. This shows a big contrast with the planar case, for which this decision problem is easy. © 2011 Springer., Special issue of selected papers from the 7th Japan Conference on Computational Geometry and Graphs (JCCGG09), SCOPUS: ar.j, info:eu-repo/semantics/published

arXiv:0904.2115, info:eu-repo/semantics/published

Given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing enough points contains all colors. The goal is to bound the necessary size of such a strip, as a function of k. We show that if the strip size is at least 2k-1, such a coloring can always be found. We prove that the size of the strip is also bounded in any fixed number of dimensions. In contrast to the planar case, we show that deciding whether a 3D point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete.We also consider the problem of coloring a given set of axis-aligned strips, so that any sufficiently covered point in the plane is covered by k colors. We show that in d dimensions the required coverage is at most d(k-1)+1.Lower bounds are given for the two problems. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. Finally, we study a variant where strips are replaced by wedges., arXiv:0904.2115, info:eu-repo/semantics/published

info:eu-repo/semantics/published

SCOPUS: cp.k, info:eu-repo/semantics/published

info:eu-repo/semantics/published

info:eu-repo/semantics/published

Given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing enough points contains all colors. The goal is to bound the necessary size of such a strip, as a function of k. We show that if the strip size is at least 2k-1, such a coloring can always be found. We prove that the size of the strip is also bounded in any fixed number of dimensions. In contrast to the planar case, we show that deciding whether a 3D point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete.We also consider the problem of coloring a given set of axis-aligned strips, so that any sufficiently covered point in the plane is covered by k colors. We show that in d dimensions the required coverage is at most d(k-1)+1.Lower bounds are given for the two problems. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. Finally, we study a variant where strips are replaced by wedges., arXiv:0904.2115, info:eu-repo/semantics/published

arXiv:0904.2115, info:eu-repo/semantics/published

info:eu-repo/semantics/published

SCOPUS: cp.k, info:eu-repo/semantics/published