Browsing by Author "Lopez-Ortiz, Alejandro"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Adaptive set intersections
    (1998) Demaine, Erik, D.; Lopez-Ortiz, Alejandro; Munro, J., l.
    We introduce a new data structure, corresponding to a fully persistent SET ADT, motivated by the efficient evaluation of boolean queries in text retrieval systems. We then focus on a key operation required by the ADT, namely the problem of efficiently evaluating an intersection expression over a static collection of integer sets. We present an optimal nondeterministic algorithm for computing the shortest proof of nonintersection for disjoint sets in the comparison model. Then we propose an adaptive algorithm for computing such proofs in deterministic fashion. The number of comparisons performed by this algorithm falls within a small multiplicative factor of the theoretical best. This algorithm is generalized to compute the intersection of nondisjoint collections of sets with the same competitive factor.
  • Thumbnail Image
    Item
    An O (n log 2 n / log log n) lower bound for Algorithm W in a synchronous fail-stop (no restart) PRAM
    Lopez-Ortiz, Alejandro
    In [1] Buss et al. propose an algorithm for the Write-All problem for a general fail-stop PRAM. In the same paper it is conjectured that the algorithm performs work O (N log N log log N) for the fail-stop with no restart model. In this work it is shown that, using the adversary proposed by Kanellakis and Shvartsman, the amount of work performed by such algorithm is O (n log[superscript 2] n / log log n).
  • Thumbnail Image
    Item
    The exact cost of exploring streets with a CAB
    (1998) Lopez-Ortiz, Alejandro; Schuierer, Sven
    A fundamental problem in robotics is to compute a path for a robot from its current location to a given target. In this paper we consider the problem of a robot equipped with an on-board vision system searching for a target t in an unknown environment. We assume that the robot is located at a points in a polygon that belongs to the well investigated class of polygons called streets. A street is a simple polygon where s and t are located on the polygon boundary and the part of the polygon boundary from s to t is weakly visible to the part from t to s and vice versa. We are interested in the ratio of the length of the path traveled by the robot to the length of the shortest path from s to t which is called the competitive ratio of the strategy. In this work we present the first exact analysis of the continuous angular bisector (CAB) strategy, which has been considered several times before, and show that it has a competitive ratio of ≃ 1.6837 in the worst case.
  • Thumbnail Image
    Item
    The ultimate strategy to search on m rays?
    (1998) Lopez-Ortiz, Alejandro; Schuierer, Sven
    We consider the problem of searching on m current rays for a target of unknown location. If no upper bound on the distance to the target is known in advance, then the optimal competitive ratio is 1 + 2m[superscript m] / ( m - 1 )[superscript m-1]. We show that if an upper bound of D on the distance to the target is known in advance, then the competitive ratio of any search strategy is at least 1 + 2m[superscript m]/(m -1)[superscript m-1] - 0(1/log[superscript 2] D) which is also optimal-but in a stricter sense. We construct a search strategy that achieves this ratio. Our strategy works equally as well for the unbounded case, and produces a strategy where the point is found at a competitive distance of 1 + 2m[superscript m] f(m -1)[superscript m-1] - 0(1/log[superscript 2] D), for unknown, unbounded D, that is, it is not necessary for our strategy to know an upper bound on the distance D in advance.