Article

Free access

On range reporting, ray shooting and k-level construction

Author:

Edgar A. RamosAuthors Info & Claims

SCG '99: Proceedings of the fifteenth annual symposium on Computational geometry

Pages 390 - 399

https://doi.org/10.1145/304893.304993

Published: 13 June 1999 Publication History

PDF eReader

References

[1]

P. K. Agarwal, M. de Berg, J. Matou~,ek and O. Schwarzkopf. Constructing levels in arrangements and higher order Voronoi diagrams. SIAM J. Cornput. 27 (1998), 654-667.

Digital Library

Google Scholar

[2]

P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. To appear in Discrete and Computational Geometry: Ten Years Later (B. Chazelle, J. E. Goodman, and R. Pollack, eds.) AMS Press.

Google Scholar

[3]

P. K. Agarwal, J. Matou.~ek and O. Schwarzkopf. Computing many faces in arrangements of lines and segments. SIAM J. Comput. 27 (1998), 491-505.

Digital Library

Google Scholar

[4]

N. M. Amato, M. T. Goodrich and E. A. Ramos. Computing faces in segment and simplex arrangements. STOC'95, 672-682.

Digital Library

Google Scholar

[5]

M. de Berg, K. Dobrindt and O. Schwarzkopf. On lazy randomized incremental construction. Discrete Comput. Geom. 14 (1995), 261-286.

Digital Library

Google Scholar

[6]

H. BrSnnimann. Derandomization of Geometric Algorithms. Ph.D. Thesis. Department of Computer Science, Princeton University. 1995.

Digital Library

Google Scholar

[7]

H. BrSnnimann, B. Chazelle and J. Matou~ek. Product range spaces, sensitive sampling, and derandomization. FOCS'93, 400-409.

Digital Library

Google Scholar

[8]

T. Chan. Fixed-dimensional linear programming queries made easy. SOCG'96, 284-290.

Digital Library

Google Scholar

[9]

T. Chan. Random sampling, halfspace range reporting and construction of (< k)-levels in three dimensions. FOCS'98.

Digital Library

Google Scholar

[10]

B. Chazelle. Cutting hyperplanes for divide-andconquer. Discrete Comput. Geom., 9 (1993), 145- 158.

Digital Library

Google Scholar

[11]

B. Chazelle. An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geom., 10 (1993), 377-409.

Digital Library

Google Scholar

[12]

B. Chazelle and J. Friedman. A deterministic view of random sampling and its use in geometry. Combinatot/ca, 10 (1990), 229-249.

Crossref

Google Scholar

[13]

B. Chazelle and J. Friedman. Point location among hyperplanes and unidirectional ray-shooting. Cornput. Geom. 4 (1994), 53-62.

Digital Library

Google Scholar

[14]

K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4 (1989), 387-421.

Digital Library

Google Scholar

[15]

A. Crauser, P. Ferragina, K. Mehlhorn, U. Meyer and E. A. Ramos. External memory algorithms for some geometric problems. SOCG'98, 259-268.

Digital Library

Google Scholar

[16]

J. Matou~ek. Cutting hyperplane arrangements. Discrete Comput. Geom. 6 (1991), 385-406.

Digital Library

Google Scholar

[17]

J. Matougek. Approximations and optimal geometric divide-and-conquer. J. Comput. Syst. Sci. 50 (1995), 203-208.

Digital Library

Google Scholar

[18]

J. Matou~ek. Efficient partition trees. Discrete Cornput. Geom. 8 (1992), 315-334.

Digital Library

Google Scholar

[19]

J. Matou~ek. Reporting points in halfspaces. Cornput. Geom. 2 (1992), 169-186.

Digital Library

Google Scholar

[20]

J. Matou~ek. On vertical ray shooting in arrangements. Cornput. Geom. 3 (1993), 279-285.

Digital Library

Google Scholar

[21]

J. Matougek and O. Schwarzkopf. On ray shooting in convex polytopes. Discrete Cornput. Geom. 10 (1993), 215-232.

Digital Library

Google Scholar

[22]

K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1993.

Google Scholar

Cited By

View all

Chan TZheng D(2024)Hopcroft’s Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision TreesACM Transactions on Algorithms10.1145/359135720:3(1-27)Online publication date: 21-Jun-2024
https://dl.acm.org/doi/10.1145/3591357
Claverol Mde las Heras Parrilla AHuemer CMartínez-Moraian A(2024)The edge labeling of higher order Voronoi diagramsJournal of Global Optimization10.1007/s10898-024-01386-090:2(515-549)Online publication date: 21-May-2024
https://doi.org/10.1007/s10898-024-01386-0
Chan THar-Peled S(2024)On the Number of Incidences When Avoiding an Induced Biclique in Geometric SettingsDiscrete & Computational Geometry10.1007/s00454-024-00648-8Online publication date: 23-May-2024
https://doi.org/10.1007/s00454-024-00648-8
Show More Cited By

Index Terms

On range reporting, ray shooting and k-level construction
1. Computing methodologies
  1. Computer graphics
    1. Image manipulation
    2. Shape modeling
      1. Parametric curve and surface models
      2. Volumetric models
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Visibility and ray shooting queries in polygonal domains

Given a polygonal domain (or polygon with holes) in the plane, we study the problem of computing the visibility polygon of any query point. As a special case of visibility problems, we also study the ray-shooting problem of finding the first point on the ...
Accelerating ray shooting through aggressive 5D visibility preprocessing
AFRIGRAPH '03: Proceedings of the 2nd international conference on Computer graphics, virtual Reality, visualisation and interaction in Africa

We present a new approach to accelerating general ray shooting. Our technique uses a five-dimensional ray space partition and is based on the classic ray-classification algorithm. Where the original algorithm evaluates intersection candidates at run-...
Ray Shooting Amidst Convex Polygons in 2D

We consider the problem of ray shooting in a two-dimensional scene consisting ofmconvex polygons with a total ofnedges. We present a data structure that requiresO(mnlogm) space and preprocessing time and that answers a ray shooting query inO(log2mlog2n) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '99: Proceedings of the fifteenth annual symposium on Computational geometry

June 1999

432 pages

ISBN:1581130686

DOI:10.1145/304893

Chairman:
Victor Milenkovic
Univ. of Miami, Coral Gables, FL

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SoCG99

Sponsor:

SoCG99: The Symposium on Computational Geometry

June 13 - 16, 1999

Florida, Miami Beach, USA

Acceptance Rates

SCG '99 Paper Acceptance Rate 44 of 103 submissions, 43%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

54
Total Citations
View Citations
568
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)4

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chan TZheng D(2024)Hopcroft’s Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision TreesACM Transactions on Algorithms10.1145/359135720:3(1-27)Online publication date: 21-Jun-2024
https://dl.acm.org/doi/10.1145/3591357
Claverol Mde las Heras Parrilla AHuemer CMartínez-Moraian A(2024)The edge labeling of higher order Voronoi diagramsJournal of Global Optimization10.1007/s10898-024-01386-090:2(515-549)Online publication date: 21-May-2024
https://doi.org/10.1007/s10898-024-01386-0
Chan THar-Peled S(2024)On the Number of Incidences When Avoiding an Induced Biclique in Geometric SettingsDiscrete & Computational Geometry10.1007/s00454-024-00648-8Online publication date: 23-May-2024
https://doi.org/10.1007/s00454-024-00648-8
Asudeh ADas GJagadish HLu SNazi ATao YZhang NZhao J(2022)On Finding Rank Regret RepresentativesACM Transactions on Database Systems10.1145/353105447:3(1-37)Online publication date: 18-Aug-2022
https://dl.acm.org/doi/10.1145/3531054
Liu C(2022)Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance FunctionsSIAM Journal on Computing10.1137/20M138837151:3(723-765)Online publication date: 26-May-2022
https://doi.org/10.1137/20M1388371
Kaplan HMulzer WRoditty LSeiferth PSharir M(2020)Dynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic ApplicationsDiscrete & Computational Geometry10.1007/s00454-020-00243-7Online publication date: 22-Sep-2020
https://doi.org/10.1007/s00454-020-00243-7
Chan T(2020)Dynamic Geometric Data Structures via Shallow CuttingsDiscrete & Computational Geometry10.1007/s00454-020-00229-5Online publication date: 24-Jul-2020
https://doi.org/10.1007/s00454-020-00229-5
Oh EAhn H(2019)Assigning weights to minimize the covering radius in the planeComputational Geometry10.1016/j.comgeo.2018.10.007Online publication date: Mar-2019
https://doi.org/10.1016/j.comgeo.2018.10.007
Bohler CKlein RLiu C(2019)An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi DiagramsAlgorithmica10.1007/s00453-018-00536-781:6(2317-2345)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00453-018-00536-7
Emiris IFisikopoulos V(2018)Practical Polytope Volume ApproximationACM Transactions on Mathematical Software10.1145/319465644:4(1-21)Online publication date: 16-Jun-2018
https://dl.acm.org/doi/10.1145/3194656
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Visibility and ray shooting queries in polygonal domains

Accelerating ray shooting through aggressive 5D visibility preprocessing

Ray Shooting Amidst Convex Polygons in 2D