Paper Info

Title | ||
---|---|---|

Stabbing horizontal segments with vertical rays |

Abstract | ||
---|---|---|

We consider maintaining a dynamic set S of N horizontal segments in R2 such that, given a vertical ray Q in R2, the segments in S intersecting Q can be reported efficiently. In the external memory model, we give a structure that consumes O(N/B) space, answers a query in O(logB N + K/B) time (where K is the number of reported segments), and can be updated in O(logB N) amortized time per insertion and deletion. With B set to a constant, the structure also works in internal memory, consuming space O(N), answering a query in O(log N + K) time, and supporting an update in O(log N) amortized time. |

Year | DOI | Venue |
---|---|---|

2012 | 10.1145/2261250.2261298 | Symposium on Computational Geometry 2013 |

Keywords | DocType | Citations |

amortized time,consuming space o,intersecting q,consumes o,reported segment,internal memory,n horizontal segment,logb n,external memory model,vertical ray,dynamic set,external memory,data structure | Conference | 1 |

PageRank | References | Authors |

0.35 | 13 | 1 |