Seminar by Dr. Rahul Ray
Translating a planar object to maximize point containment and a related problem of finding planarity in terrains
Dr. Rahul Ray
Max-Planck-Institut fuer Informatik (MPII)
Saarbrucken, Germany
Date: Friday, December 5, 2003
Time: 3:45 PM
Venue: CS-101
Abstract
In the first part of the talk, we discuss the problem of computing a translate of a planar object that contains the maximum number of points in a plane. It is known that this problem can be solved in a time that is roughly quadratic in n , where n is number of points in the plane. We show how random-sampling and bucketing techniques can be used to develop a near-linear-time Monte Carlo algorithm that computes a placement of the planar object containing at least $(1-\\eps) \\kappa\^\*$ points in the plane , for given $\\eps\>0$, with high probability, where $\\kappa\^\*$ is number of points covered by an optimal placement of the planar object. We also present a deterministic algorithm that solves the $\\eps$-approximate version of the optimal-placement problem and runs in $O( (n\^{1+\\delta} + n/\\eps)\\log m )$ time, for arbitrary constant $\\delta\>0$, if the planar object is a convex m-gon. In the subsequent part of the talk, we describe an application specific example of finding a planar area in terrains and show how we solve it using some of the theories described in the first part of the talk. We also demonstrate a software called 'Planefinder' developed by us to locate the planar areas in a terrain.