Abstract
Efficient solutions are given for the problem of preprocessing a set of linear or curved geometric objects (e.g. lines, llne segments, circles, circular arcs, d-balls, d-spheres)such that the ones that are intersected by a curved query object can be reported (or counted) quickly. The problem is considered both in the standard setting (where one is interested in all the objects intersected) and in a generalized setting (where the input objects come aggregated in disjoint groups and one is interested in the disjoint groups that axe intersected). The solutions axe based on geometric transformations, simplex compositions, persistence, and, for the generalized problem, oa a method to progressively eliminate groups that cannot possibly be intersected.
| Original language | English (US) |
|---|---|
| Title of host publication | Algorithm Theory – SWAT 1994 - 4th Scandinavian Workshop on Algorithm Theory, Proceedings |
| Editors | Erik M. Schmidt, Sven Skyum |
| Publisher | Springer Verlag |
| Pages | 183-194 |
| Number of pages | 12 |
| ISBN (Print) | 9783540582182 |
| DOIs | |
| State | Published - 1994 |
| Event | 4th Scandinavian Workshop on Algorithm Theory, SWAT 1994 - Aarhus, Denmark Duration: Jul 6 1994 → Jul 8 1994 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 824 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Other
| Other | 4th Scandinavian Workshop on Algorithm Theory, SWAT 1994 |
|---|---|
| Country/Territory | Denmark |
| City | Aarhus |
| Period | 7/6/94 → 7/8/94 |
Bibliographical note
Funding Information:2Max-Planck-Institut ffw Informatik, D-66123 Saarbr~cken, Germany. Email: -ichielQmpi-sb .rups.de. This author w, m supported by the ESPRIT Basic Research Actions Program, under contract No. 7141 (project ALCOM II).
Funding Information:
Most previous work on these problems assumes that the input objects and the query object are linear or piecewise-linear. To our knowledge, the case where the input and/or the query are curved has been investigated systematically only. in \[AvKO93, KOA90, Sha91, AM92\]. In \[AvKO93\]s, earching on curved objects (e.g., circles, disks, circular arcs, Jordan arcs) with linear query objects (e.g., lines, line segments, halfspaces, rays) is considered. In \[KOAg0\]( resp. \[Sha91\]), the input is a set of disks and the query is a line or line segment (resp. a point), 1Department of Computer Science, Universlty'of Minnesota, Minneapolis, MN 55455, U.S.A. Enudl: {pgupta, j amardan)@cs,u am.e du. The research of these authors was supported in part by NSF grant CCR-92-00270.
Publisher Copyright:
© 1994, Springer Verlag. All rights reserved.