Browse Prior Art Database

Algorithm for Generation of Adaptive Tiles

IP.com Disclosure Number: IPCOM000033533D
Original Publication Date: 2004-Dec-14
Included in the Prior Art Database: 2004-Dec-14
Document File: 4 page(s) / 32K

Publishing Venue

IBM

Abstract

A method for partitioning the N-dimensional parallelepiped region (e.g., a rectangle in two dimensions) into disjoint sub-parallelepipeds, or tiles, which completely cover it is disclosed. The method takes as input a number of values at different points within the region which represent samples of some parameter which varies continuously within the region. The method can be used to generate tiles within which the range of sample values is less than some specified bound, to partition the original region into a specified maximum number of tiles, and/or to include specified parallelepipeds in the output tile list.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 41% of the total text.

Page 1 of 4

Algorithm for Generation of Adaptive Tiles

The problem solved by this invention is, given a number of sample points in a specified region of N-dimensional space, each with an associated value, to compress the data by putting out a number of "tiles", or N-dimensional rectangles, which fully covers the specified region. Each tile encloses at least one sampling point. Associated with each tile is a value or range of values. A single value might be the mean of the values of all sample points in the tile, or the midpoint of the range of such values. A range of values might be the minimum and maximum value of all the sample points in the tile. The goal is to control both the number of tiles generated and the range of values for each.

One known prior art method is to uniformly subdivide the given region in each dimension, resulting in a fixed number of tiles of fixed size. The drawback of this method is its inability to control the range of values within a tile. This invention uses a recursive algorithm for dividing the given region into two regions if the sample values within the region satisfy the specified bound. The following figure illustrates the method. The numbers are sample values, and the lines indicate the boundaries of the adaptively generated tiles. The circled values are the maximum and minimum in each tile, whose difference determines the value range for the tile.

The pseudo-code for the first embodiment of this invention is shown below:

Procedure TileRegion1( sampleList, region ) {

If( range of values in sampleList is within specified bound) output a single tile for the region;

Else

1

[This page contains 1 picture or other non-text object]

Page 2 of 4

{

Sort sampleList by one of the dimensions of the space (typically the dimension in which the region is widest)

Divide the sorted sampleList in two (typically at the median of the list or the midpoint of the region in the selected dimension. Preferably the division is done between two samples whose coordinate in the sorting dimension differs, so no sample points will fall directly on the boundary between two regions.) Divide the region in two, such that each new sub-region contains all the sample points of one of the new sub-sampleLists.

    Recursively call TileRegion1 on each sub-region/sub-sampleList pair. } }

The algorithm can be extended to limit the number of tiles generated. If a specified tile value range limit can be satisfied with less than the specified number of tiles, the algorithm will generate that smaller number of tiles. The algorithm can also be extended using the scanline algorithms to find tiles which meet the specified bound but might fall across a region midpoint determined by the previous algorithm. Pseudo-code implementing these extensions in a second embodiment of the invention is shown below:

Procedure TileRegion2( sampleList, region ) {

Push the original region and sampleList on a priority queue Q, whose top element is always the element having the lar...