BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/267
DTSTAMP:20230914T125917Z
SUMMARY:Geometric Searching
DESCRIPTION:Speaker: Pritam Bhattacharya\n\nAbstract: \nTo describe searchi
ng in its simplest abstract setting\, suppose we have some accumulated dat
a (called the 'file') and some new data item (called the 'sample'). Then\,
searching consists of relating the sample to the file. As Knuth pointed o
ut\, searching simply means locating the appropriate record (or records) i
n a given collection of records.\n\nAlthough all searching problems shar
e some basic common feature\, the geometric setting gives rise to question
s of a somewhat unique flavour. First of all\, in geometric applications\,
files are primarily not just 'collections'\, as in several other informat
ion processing activities. Rather\, they are frequently representations of
more complex structures\, such as polygons\, polyhedra etc. Even the case
of a collection of segments in the plane appears deceptively unstructured
\, since each segment is associated with its end-point co-ordinates\, whic
h are implicitly related by the metric structure of the plane. Moreover\,
the fact that co-ordinates of points are thought of as real numbers entail
s that a search may not exactly find an item in the file matching the samp
le\, but rather it will locate the latter in relation to the file. This pr
ovides an additional point of contrast between geometric searching and con
ventional searching.\n\nNow\, suppose we have a collection of geometric da
ta\, and we want to know if it possesses a certain property (say convexity
). In the simplest case\, the query will be asked only once\, in which cas
e it would be wasteful to do any preconditioning in the hope of speeding u
p future queries. A one-time query of this type will be referred to as 'si
ngle-shot'. Many times\, however\, queries will be performed repeatedly on
the same file. Such queries will be referred to as 'repetitive-mode' quer
ies. In this case\, it may be worthwhile to arrange the information into a
n organized structure to facilitate searching. This can be accomplished on
ly at some additional expense though. Then\, our analysis must focus on fo
ur separate cost measures\, namely -\n\n1) Query Time\n2) Preprocessing Ti
me\n3) Storage Space\n4) Update Time\n\nIn my talk\, I will try to illustr
ate the various trade-offs among these cost measures through the following
2 problems -\n\nA) RANGE SEARCHING : Given N points in the plane\, how ma
ny lie in a given rectangle with sides parallel to the co-ordinate axes? T
hat is\, how many points (x\,y) satisfy a\n
URL:https://www.tcs.tifr.res.in/web/events/267
DTSTART;TZID=Asia/Kolkata:20120420T160000
DTEND;TZID=Asia/Kolkata:20120420T173000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR