Parabola separation queries and their application to stone throwing

Otfried Cheong 1 Hazel Everett 2 Hyo-Sil Kim 1 Sylvain Lazard 2 René Schott 3
1 KAIST - Department of Electrical Engineering [Korea Advanced Institute of Science and Technology]
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 IECN - Institut Élie Cartan de Nancy
Abstract : Given two sets $A$ and $B$ of $m$ non-crossing line segments in the plane, we show how to compute in $O(m \log m)$ time a data structure that uses $O(m)$ storage and supports the following query in $O(\log m)$ time: Given a parabola $\p: y = ax^{2} + bx + c$, does $\p$ separate $A$ and $B$? This structure can be used to build a data structure that stores a simple polygon and allows ray-shooting queries along parabolic trajectories with vertical main axis. For a polygon of complexity~$n$, we can answer such ``stone-throwing'' queries in $O(\log^{2} n)$ time, using $O(n \log n)$ storage and $O(n \log^{2} n)$ preprocessing time. This matches the best known bound for circular ray shooting in simple polygons.
keyword : Ray shooting simple polygon parabola separation queries parabolic arc
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 2007, 17 (4), pp.349-360. 〈10.1142/S0218195907002379〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00434090
Contributeur : Sylvain Lazard <>
Soumis le : vendredi 20 novembre 2009 - 16:57:00
Dernière modification le : jeudi 11 janvier 2018 - 06:20:14
Document(s) archivé(s) le : jeudi 17 juin 2010 - 19:05:15

Fichier

ijcga-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | IECN | LORIA | UNIV-LORRAINE

Citation

Otfried Cheong, Hazel Everett, Hyo-Sil Kim, Sylvain Lazard, René Schott. Parabola separation queries and their application to stone throwing. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2007, 17 (4), pp.349-360. 〈10.1142/S0218195907002379〉. 〈inria-00434090〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

396

Téléchargements de fichiers

155

Contact


archive-ouverte@inria.fr