Posted by: Janine | August 19, 2011

Computational Geometry

Less is more. More’s less.
Some is more than emptiness.
Count them, more or less.

Hayim Shaul

Tel-Aviv University

Title: Range Searching: Emptiness, Reporting and Approximate Counting
Given a set of points in high dimensional space, we show how to preprocess them into a data structure such that given a range in space we can determine quickly whether this range is empty. We extending and improve the results of Matousek (1992), whose result was only for hyper planes, and Matousek & Agarwal (1994) who counted the points (with worse time bounds).
Our result has many applications such as, ray shooting on fat triangles being faster than on thin triangles (Less is more. More is less), various emptiness problems (Some is more than emptiness) and approximate counting data structures (Count them, more or less)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Categories

%d bloggers like this: