s'authentifier
version française rss feed

inria-00074101, version 1

3-D Vertical Ray Shooting and 2-D Point Enclosure, Range Searching, and Arc Shooting Amidst Convex Fat Objects

Matthew Katz 1

N° RR-2583 (1995)

Résumé : We present a new data structure for a set of $n$ convex simply-shaped fat objects in the plane, and use it to obtain efficient and rather simple solutions to several problems including (i) {\em vertical ray shooting} --- preprocess a set $\K$ of $n$ non-intersecting convex simply-shaped flat objects in 3-space, whose $xy$-projections are fat, for efficient vertical ray shooting queries, (ii) {\em point enclosure} --- preprocess a set $\Cn$ convex simply-shap- ed fat objects in the plane, so that the $k$ objects containing a query point $p$ can be reported efficiently, (iii) {\em bounded-size range searching} --- preprocess a set $\Cn$ convex fat polygons, so that the $k$ objects intersecting a `not-too-large' query polygon can be reported efficiently, and (iv) {\em bounded-size segment shooting} --- preprocess a set $\Cn (iii), so that the first object (if exists) hit by a `not-too-long' oriented query segment can be found efficiently. For the first three problems we construct data structures of size $O(\lambda_s(n) \log^3 n)$, where $s$ is the maximum number of intersections between the boundaries of the ($xy$-projections) of any pair of objects, and $\lambda_s(n)$ is the maximum length of $(n,s)$ Davenport-Schinzel sequences. The data structure for the fourth problem is of size $O(\lambda_s(n) \log^2 n)$. The query time in the first problem is $O(\log^4 n)$, the query time in the second and third problems is $O(\log^3 n + k \log^2 n)$, and the query time in the fourth problem is $O(\log^3 n)$. We also present a simple algorithm for computing a depth order for a set $\K$ as in (i), that is based on the solution to the vertical ray shooting problem. (A depth order for $\K$, if exists, is a linear order of $\K$, such that, if $K_1,K_2 \in \K$ and $K_1$ lies vertically above $K_2$, then $K_1$ precedes $K_2$.) The algorithm is able to determine whether such an order exists, unlike the algorithm of Agarwal~et~al. \cite{AgKS} that might output a false order when a depth order does not exist, and it is often more efficient in practical situations than the latter algorithm.

  • Domaine : Informatique/Autre
  • Mots-clés : COMPUTATIONAL GEOMETRY / DATA STRUCTURES / OUTPUT-SENSITIVE ALGORITHMS / VISIBILITY
  • Référence interne : RR-2583
 
  • inria-00074101, version 1
  • oai:hal.inria.fr:inria-00074101
  • Contributeur : 
  • Soumis le : Mercredi 24 Mai 2006, 14:31:47
  • Dernière modification le : Mercredi 31 Mai 2006, 14:24:28
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...