Nanotechnology scientists at the University of Connecticut and the University of Michigan have introduced a new version of the well-known ‘packing problem’ dubbed as the ‘filling problem.’
The research team devised the new problem when they tried to identify a method for representing many-sided shapes for computer simulations of nanoparticles. The filling problem finds the optimal way to fill an object’s inside with a specific shape, such as filling the inside of a triangle with different-sized discs. Contrary to the conventional packing problem, the filling problem does allow the overlap of the discs. It does not allow the discs to extend beyond the boundaries of the triangle, which is unlike the ‘covering problem.’
According to the researchers, the new problem holds potential in the advancement of microelectronics, securing of wireless networks, treatment of cancer and demolitions. Sharon Glotzer, one of the researchers, stated that in addition to exposing the problem, the nanotechnology team also presented a solution in two dimensions.
The immediate applications of this solution are cancer treatment utilizing fewer radiation shots or accelerating silicon chip production for microprocessors. Carolyn Phillips, one of the researchers, informed that finding the skeleton of a shape is crucial to solutions in any size.
For instance, the skeleton of a pentagon resembles a line-sketch of a star fish. The centers of the discs must be on one these lines to achieve the optimal filling. According to the research team, intersections between these lines of the skeleton are key points, which are called as ‘traps.’
The pentagon has only one trap at its center. However, more intricate shapes can have several traps and in majority of the optimal solutions, a disc is centered on every trap. Based on the count of discs to be allowed, other discs in the design move around and modify size, but the discs centered on the traps remain the same.
In a paper reported in the journal, Physical Review Letters, the research team discussed the rules to determine the discs’ optimal size and spacing to fill a pattern. The team plans to devise an algorithm to determine the optimal pattern to fill an object.
Source: http://www.umich.edu/