NDLI: An experimental study of point location in planar arrangements in CGAL

Please wait, while we are loading the content...

An experimental study of point location in planar arrangements in CGAL

Content Provider	ACM Digital Library
Author	Haran, Idit Halperin, Dan
Copyright Year	2009
Abstract	We study the performance in practice of various point-location algorithms implemented in CGAL (the Computational Geometry Algorithms Library), including a newly devised $\textit{landmarks}$ algorithm. Among the other algorithms studied are: a naïve approach, a “walk along a line” strategy, and a trapezoidal decomposition-based search structure. The current implementation addresses general arrangements of planar curves, including arrangements of nonlinear segments (e.g., conic arcs) and allows for degenerate input (for example, more than two curves intersecting in a single point or overlapping curves). The algorithms use exact geometric computation and thus result in the correct point location. In our landmarks algorithm (a.k.a. jump & walk), special points, ““landmarks,” are chosen in a preprocessing stage, their place in the arrangement is found, and they are inserted into a data structure that enables efficient nearest-neighbor search. Given a query point, the nearest landmark is located and a “walk” strategy is applied from the landmark to the query point. We report on various experiments with arrangements composed of line segments or conic arcs. The results indicate that compared to the other algorithms tested, the landmarks approach is the most efficient, when the overall (amortized) cost of a query is taken into account, combining both preprocessing and query time. The simplicity of the algorithm enables an almost straightforward implementation and rather easy maintenance. The generic programming implementation allows versatility both in the selected type of landmarks and in the choice of the nearest-neighbor search structure. The end result is an efficient point-location algorithm that bypasses the alternative CGAL implementations in most practical aspects.
Starting Page	2.3
Ending Page	2.32
Page Count	30
File Format	PDF
ISSN	10846654
e-ISSN	10846654
DOI	10.1145/1412228.1412237
Journal	Journal of Experimental Algorithmics (JEA)
Volume Number	13
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-02-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	CGAL Point location Arrangements Computational geometry Generic programming
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Online Point Location in Planar Arrangements and Its Applications

Computing the width of a three-dimensional point set: an experimental study

A Generic Implementation of dD Combinatorial Maps in CGAL

A Generic Implementation of dD Combinatorial Maps in CGAL

Design of the CGAL Spherical Kernel and application to arrangements of circles on a sphere

Entropy, triangulation, and point location in planar subdivisions

Design of the CGAL Spherical Kernel and application to arrangements of circles on a sphere

Design of the CGAL Spherical Kernel and application to arrangements of circles on a sphere

Arrangements on Parametric Surfaces I: General Framework and Infrastructure

An experimental study of point location in planar arrangements in CGAL

Similar Documents

Online Point Location in Planar Arrangements and Its Applications

Computing the width of a three-dimensional point set: an experimental study

A Generic Implementation of dD Combinatorial Maps in CGAL

A Generic Implementation of dD Combinatorial Maps in CGAL

Design of the CGAL Spherical Kernel and application to arrangements of circles on a sphere

Entropy, triangulation, and point location in planar subdivisions

Design of the CGAL Spherical Kernel and application to arrangements of circles on a sphere

Design of the CGAL Spherical Kernel and application to arrangements of circles on a sphere

Arrangements on Parametric Surfaces I: General Framework and Infrastructure

An experimental study of point location in planar arrangements in CGAL