This list is also available as a BibTeX file.

You may notice that author and title information is missing from many of the papers listed below. You can help correct this by submitting this information online using the "Correct" link after each paper.

CCCG 1996 Papers

1

Table of contents.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 348-352, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_toc.pdf.

2

Roberto Tamassia.
Robust proximity queries in implicit voronoi diagrams.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 1-1, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0000.pdf.
Correct.

3

V. Martynchik, N. Metelski, and D. Wood.
$\mathcal{O}$-convexity: Computing hulls, approximations, and orientation sets.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 2-7, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0001.pdf.
Correct.

4

Prosenjit Gupta, Ravi Janardan, and Michiel Smid.
Efficient algorithms for couting and reporting pairwise intersections between convex polygons.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 8-13, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0002.pdf.
Correct.

5

Jean-Daniel Boissonat and Sylvain Lazard.
Convex hulls of bounded curvature.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 14-19, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0003.pdf.
Correct.

6

Michael Segal and Klara Kedem.
Enclosing $k$ points in the smallest axis parallel rectangle.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 20-25, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0004.pdf.
Correct.

7

J. Bhadury and R. Chandrasekaran.
Finding the set of all minimal nested convex polygons.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 26-31, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0005.pdf.
Correct.

8

Gill Barequet and Barbara Wolfers.
Optimizing a corridor between two polygons with an application to polyhedral interpolation.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 32-37, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0006.pdf.
Correct.

9

Thomas Auer and Martin Held.
Heuristics for the generation of random polygons.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 38-43, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0007.pdf.
Correct.

10

L. Jackson and S. K. Wismath.
Orthogonal polygon reconstruction.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 44-49, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0008.pdf.
Correct.

11

Dong Wang and John A. Goldak.
Correcting topological defects of tessellations.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 50-55, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0009.pdf.
Correct.

12

David Avis and Chin Ming Kong.
Generating rooted triangulations with minimum degree four.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 56-61, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0010.pdf.
Correct.

13

Cao, Wang, Ying, Feng, and Xue.
On stable line segments in triangulations andranik mirzaian an and.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 62-67, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0011.pdf.
Correct.

14

Prosenjit Bose, Luc Devroye, and William Evans.
Diamondsarenotaminimumweighttriangulatio n' befriend.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 68-73, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0012.pdf.
Correct.

15

Hazel Everett, Ferran Hurtado, and Marc Noy.
Stabbing information of a simple polygon.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 74-79, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0013.pdf.
Correct.

16

Nina Amenta.
$k$-transversals of parallel convex sets.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 80-86, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0014.pdf.
Correct.

17

Franck Nielsen.
Fast stabbing of boxes in high dimensions.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 87-92, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0015.pdf.
Correct.

18

Subhas C. Nandy, Krishnendu Mukhopadhyaya, and Bhargar B. Bhattacharya.
Shooter location problems.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 93-98, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0016.pdf.
Correct.

19

Chandrajit L. Bajaj.
Computational geometry for interrogative dualization.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 99-100, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0017.pdf.
Correct.

20

Sergei N. Bespamyatnikh.
An optimal algorithm for dynamic post office problem and related problems.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 101-106, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0018.pdf.
Correct.

21

Toshiyuki Imai.
A topology oriented algorithm for the voronoi diagram of polygons.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 107-112, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0019.pdf.
Correct.

22

Ngoc-Minh Le.
On non smooth convex distance functions.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 113-118, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0020.pdf.
Correct.

23

Stephan Olariu, Ivan Stojmenovic, and Albert Y. Zomaya.
Time-optimal proximity graph computations on enhanced meshes.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 119-124, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0021.pdf.
Correct.

24

Susan, Vladimir, and Lumelskyt.
Deforming curves in the plane for feathered robot motion planning hetty.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 125-130, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0022.pdf.
Correct.

25

Thomas Chazelle, Jens Epstein, and Elmar Schomer.
Heuristic motion planning with movable obstacles.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 131-136, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0023.pdf.
Correct.

26

Frank Follert.
Viewing a set of spheres while moving on a linear flightpath.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 137-142, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0024.pdf.
Correct.

27

Prosenjit Bose, William Evans, and David Kirkpatrick.
Approximating shortest paths in arrangements of lines.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 143-148, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0025.pdf.
Correct.

28

K. Krithivasan, A. Rema, Stefan, Schirra, and P. I. Vijaykumar.
Velocity planning for a robot moving along the shortest straightened path among moving obstacles.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 149-154, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0026.pdf.
Correct.

29

Danny Z. Chen, Gautam Das, and Michiel Smid.
Lower bounds for computing geometric spanners and approximate shortest paths.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 155-160, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0027.pdf.
Correct.

30

Naixun, Pei, Sue, and Whitesides.
On the reachable regions of chains and.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 161-166, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0028.pdf.
Correct.

31

Thomas, Chazelle, Jens, Epstein, Elmar, and Schomer.
Heuristic motion planning with many degrees of freedom.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 167-172, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0029.pdf.
Correct.

32

Jean, Daniel, Boissonnat, Jurek, Czyzowicz, Olivier, Devillers Jorge, and Urrutia.
Computing largest circles separating two sets of segments.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 173-178, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0030.pdf.
Correct.

33

Hanspeter Bieri and Peter-Michael Schmidt.
On the permutations generated by rotational sweeps of planar point sets.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 179-184, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0031.pdf.
Correct.

34

Jurek Czyzowicz, Evangelos Kranakis, and Danny Krizanc.
Maximallengthcommonnonintersectingpaths.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 185-189, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0032.pdf.
Correct.

35

Paola, Magillo, Leila, and De Floriani.
Maintaining multiple levels of detailing the overlay of hierarchical subdivisions.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 190-195, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0033.pdf.
Correct.

36

Karen, Daniels, Victor, and J. Milenkovic.
Distance based subdivision for translational lp containment.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 196-201, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0034.pdf.
Correct.

37

E. Puppo.
Variable resolution terrain surfaces.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 202-210, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0035.pdf.
Correct.

38

Eugene Fink and Derick Wood.
Generalizing halfspaces.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 211-216, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0036.pdf.
Correct.

39

Prosenjit, Bose, David, Kirkpatrick, and Zaiqing.
Efficient algorithms for guarding or illuminating the surface of a polyhedral terrain lit.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 217-222, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0037.pdf.
Correct.

40

Aldo Laurentini.
The surveillance of the walls of an art gallery aldo laurentian.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 223-233, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0038.pdf.
Correct.

41

I. Thomas and C. Shermer.
On rectangle visibility graphs ii external visibility and complexity.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 234-239, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0039.pdf.
Correct.

42

Danny and Z. Chi.
Maintaining visibility of a polygon withal moving point of view en t ovidiu daescut.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 240-245, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0040.pdf.
Correct.

43

Yosser Atassi.
Visibility graph of a set of line segments a dynamicsequential algorithm and its parallel version yosser atassi.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 246-251, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0041.pdf.
Correct.

44

Sergei and N. Bespamyatnikh.
Dynamic algorithms for approximate neighbor searching ( extended abstract ).
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 252-257, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0042.pdf.
Correct.

45

Eugene and Derick.
Three dimensional restricted orientation convexity 1 fink 2 wood.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 258-263, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0043.pdf.
Correct.

46

Elmar, Schomer, Jurgen, Sellen, Marek, Chee, and Yap.
Efficient algorithms for the smallest enclosing cylinder problem eichmann.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 264-269, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0044.pdf.
Correct.

47

Binhai and Zhu.
On the q ( n 4 / 3 ) weak lower bounds for some 3 d geometric problems.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 270-275, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0045.pdf.
Correct.

48

Prabhakar and Raghavan.
Computational geometry impact potential a businessman industrial perspective.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 276-282, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0046.pdf.
Correct.

49

polygons. Jurek, Czyzowicz, Ivan Thomas, and Szymacha.
On a problem of immobilizing stu ol menovic 2.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 283-288, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0047.pdf.
Correct.

50

Antonio and Hernandez Barrera.
Finding an on 2 log n ) algorithm is sometimes hard.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 289-294, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0048.pdf.
Correct.

51

Therese and C. Biedl.
Improved orthogonal drawings of 3 graphs.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 295-299, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0049.pdf.
Correct.

52

Leizhen Cai.
Algorithms on polygonal embeddings of graphs leizhen.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 300-305, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0050.pdf.
Correct.

53

Therese C. Biedl.
Optimal orthogonal drawings of connected plane graphs.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 306-311, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0051.pdf.
Correct.

54

Castagna, de Jorge, and Urrutia.
Straight line embeddings of planar graphs on point sets netzahualcoyotl department of applied mathematics universidad nacional autonoma mexican department of computer science university of ottawa.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 312-318, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0052.pdf.
Correct.

55

Robin, Y. Flatland, Charles, and V. Stewart.
Extending rectangular range reporting with query sensitive analysis and.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 319-324, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0053.pdf.
Correct.

56

de Berg, Prosenjit, Bose, Katrin, Dorit, Marc, van Kreveld, Overmars, de Thomas, Roos, Jack, Snoeyink, Sid, and yU.
The complexity of rivers in triangulated terrains mark mark markov groot 1.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 325-330, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0054.pdf.
Correct.

57

Mark de Berg, Henk Meijer, Mark Overmars, and Gordon Wilfong.
Computing the singularity tolerance mark mark.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 331-336, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0055.pdf.
Correct.

58

Jay Bagga, Laxmi Gewali, and David Glasser.
The complexity of illuminating polygons by $\alpha$-flood-lights.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 337-342, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0056.pdf.
Correct.

59

Author index.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 343-344, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0057.pdf.
Correct.

60

No Author Given.
Preface.
In Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages 345-345, 1996.
URL http://www.cccg.ca/proceedings/1996/cccg1996_0058.pdf.
Correct.